How does this recursive array permutation function work under the hood?

Question

This function generates the permutations of an array. I've taken pen to paper and put breakpoints in dev tools and painstakingly stepped through each function call, but I'm still not understanding how this is working.

Specifically, the for loop. Once the do It function has spliced out all of the numbers in the array it pushes a sliced copy of the temp array into the answer array. It then splices item into the argument array, pops that same item from the temp array and returns the answer for the first iteration of the for loop. So after looping through the array once, the answer = [1,2,3] the temp = [1,2] and the arr =[3].

This is where I get lost. It seems to jump back to the splice and splice 2 back into the arr. In devTools I put a watch on i, item, temp and arr. It says that i somehow becomes 1 even though there is only one item in the arr after we've spliced 3 back into it. If the length is 1 and the for loop specifies it should stop running at arr.length, how does it somehow jump back down to splice 2 back into the array?

I'm sorry if I'm wording this incoherently. I've spent many hours today going over this.

Tdlr. Run this function. Put a breakpoint at the for loop in the do It function. Once the array is empty and we return the answer, how does it splice two items back into the original arr.

function permute(arr) {
    var temp = [];
    var answer = [];

    function logResult() {
      answer.push(
        // make a copy of temp using .slice()
        // so we can continue to work with temp
        temp.slice()
      );
    }

    function doIt() {
      var i;
      var len;
      var item;

      for (i = 0, len = arr.length; i < len; i++) {
        // remove the item at index i
        item = arr.splice(i, 1)[0];
        // add that item to the array we're building up
        temp.push(item);
        if (arr.length) {
          // if there's still anything left in the array,
          // recurse over what's left
          doIt();
        } else {
          // otherwise, log the result and move on
          logResult();
        }
        // restore the item we removed at index i
        // and remove it from our temp array
        arr.splice(i, 0, item);
        temp.pop();  
      }
      return answer;
    }
  return doIt();
};

console.log(permute([1,2,3]));

thank you!

Answer 1

In general, I trace these not with breakpoints, but with print statements. When I enter a function, I print the function name and parameter values. When I leave, I print the name and exit (return and status) values. In this case, I'd do the same inside the loop. Now, let's take a look at this in more English-like pseudo-code

for each array element in turn: remove that element from arr and append it to item if we've emptied arr log item as the next permutation else recur with one fewer element in arr and one more in item

// When we reach this point, we've exhausted all the permutations that
//   begin with the original state of **item**.
// Back up one element
take the chosen element from **item** and re-append it to **arr**.
// Go to the next loop iteration, which will move to the next element.

As you work through this, remember that you have multiple calls to doIt on the run-time stack: the first walks through all 3 possible choices for item[0]; the second walks through the 2 possible choices for item[1], and the third takes the remaining element, logs the permutation, and backs up to the second call. Each call instance maintains its local values of i, len, and item.

To your specific question, when that first trio of calls identifies [1, 2, 3] as a solution, the state looks like this:

Stack:

1. doIt, i=0, len=1, item=3
2. doIt, i=0, len=2, item=2

3. doIt, i=0, len=3, item=1

   • arr=[3], temp=[1,2]

We now return to the previous call, #2 above, popping call #3 off the stack. In this call, we've just returned from the #3 doIt call. We jump to the restore point, splice 2 back onto arr, and iterate to the top of the loop.

Increment i to 1, select the value 3 from arr, leaving temp=[1,3] and arr=2. Recur to doIt, another call #3 ...

... which selects the remaining 2, records the solution [1, 3, 2], puts the 2 back into arr, and returns to call #2.

Call #2 splices 3 back onto arr, iterates, increments i to 2, and nhas now exhausted its for loop. It splices 1 back onto arr and returns to call #1.

We now have temp=[], arr=[1, 2, 3], and only our original doIt call on the stack. It advances to the next loop iteration (i=1), selects 2 for temp, and we start on the answers that begin with 2.

Is that enough tracing for you to get the idea?