Exploring Decision Trees

Permutation problems can be solved by using decision trees. The depth of the decision tree represents the number of possible outcomes. The breadth of the decision tree represents the ordering by which decisions are made. In programming, we can represent decision trees by using the recursive backtracking algorithm.

Recursive Backtracking Algorithm

function recurse(depth) {
  //some basecase here
  for (var i = 0;i < breadth.length;i++) {
    applyValue(breadth[i]);
    recurse(breadth[i], depth++);
    removeValue(breadth[i]);
  }
}

This code represents generalization of the recursive backtracking algorithm. This algorithm can be used to model decision trees. The depth of the tree can be represented by the depth of the recursive stack. The breadth of the tree can be represented by the number of iterations performed by the for loop within each recursive stackframe. The actual decision making process can be represented by the code within the for loop.

Solving Permutation Problems using the Recursive Backtracking Algorithm

Lets explore using the recursive backtracking algorithm to solve a permutation problem. This is an algorithm I created for finding all possible anagrams of any given word:

function anagrams(originalString) {
  var resultStorage = {};
  
  (function recurse(buildUpString, originalString) {
    if (originalString === '') {
      resultStorage[buildUpString] = 1;
      return;
    }
    for (var i = 0;i < originalString.length;i++) {
      recurse(buildUpString + originalString[i], originalString.substring(0, i) + originalString.substring(i + 1));
    }
  })('', originalString);
  
  return Object.keys(resultStorage);
};

var anagrams = anagrams('abc');
console.log(anagrams); // [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]

This solution follows the structure of the recursive backtracking algorithm shown previously. As you can see it has a for loop within a recursive function. Within the for loop there is code which controls how the final result is generated. The code within the for loop appears as though it does not resemble the 3 lines of code from within the for loop of the recursive backtracking algorithm, but in actuality this one line of code is performing the behavior of all three of the lines of code from within the recursive backtracking algorithm's for loop. The one line of code within the for loop of the anagrams algorithms perform the behavior of each one implicitly.

The anagrams solution contains 3 variables which are essential to its structure as a decision tree. Algorithm's which represent decision tree often have some form of these variables.

1. resultStorage

resultStorage is the variable which accumulates all the values of the buildUpString variable that have passed the success base case. if we are using a pure recursive solution then this variable will not exist. In such a case, each branch of the decision tree would just return it's own results to the previous branch. All results would accumulate together as each stackframe returned.

2. buildUpString

The buildUpVariable initially starts off empty and accumulates more values as the depth of the decision tree increases. When the final level of decision tree is hit, which can be represented in code as hitting a base case, we add the value of the buildUpString to resultStorage, then traverse back up the decision tree by returning from stack frames.

3. originalString

The originalString variable represents the initial value passed into the decision tree which is the basis for what all possible permutations can be.

Bringing it all together

On every recursive call, the buildUpString gets bigger, and the originalString gets smaller. When originalString has length 0, we add the value of buildUpString to resultStorage.

Returning from recursive stack frames removes values from the buildUpString in the order they were added to it. In essence, returning takes the values away from the buildUpString and puts them back into originalString. This process represents our traversal back up the decision tree.