I'll give this a shot.
Overview
You start with two arrays that will have global scope: permArray will eventually hold all of the permutation arrays, and usedChars is a worker array used build each individual permutation array through all of the recursive calls. It's important to note that these are the only two variables that are accessible in the scope of every function created. All other variables have local scope to their own function call.
Then there is the recursive function which accepts an array as input and returns an array of array with all possible permutations of the input array. Now, in this particular function the recursive call is inside a loop. This is interesting because the terminating condition is actually more complicated than your basic recursive function--the recursive calls terminate when you pass in an empty input array and the for loop skips over the next recursive call.
Summary
Consider a four element array input. At a high level, the function is going to loop over the four elements of this array, pull out each element, and compute the permutation of that smaller array of three elements. With all of those three element permutations, it will append the original element pulled out to the beginning and add each of those four element arrays to permArray.
But, in order to find the permutation of the smaller three element arrays, we pull out each element, compute the permutation of that smaller array of two elements, add the element pulled out to the beginning of each of those permutations, and return each of those three element arrays up the recursion call stack so the original fourth element can be added to the beginning and counted as a permutation.
But, in order to find the permutation of the smaller two element arrays, we pull out each element, compute the permutation of that smaller array of one element, add the element pulled out the the beginning of each of those permutations, and return each of those two element arrays up the recursion call stack so the original third element can be added to the beginning of that permutation and returned up the stack.
But, in order to find the permutation of the smaller one element array, we pull out the element and compute the permutation of that empty array, which just returns, and we in turn just return our one element back up the stack so the original second element can be added to the beginning of that permutation and returned up the stack.
Details
Let's note some of the steps in this function:
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) { // loop over all elements
ch = input.splice(i, 1)[0]; //1. pull out each element in turn
usedChars.push(ch); // push this element
if (input.length == 0) { //2. if input is empty, we pushed every element
permArr.push(usedChars.slice()); // so add it as a permutation
}
permute(input); //3. compute the permutation of the smaller array
input.splice(i, 0, ch); //4. add the original element to the beginning
// making input the same size as when we started
// but in a different order
usedChars.pop(); //5. remove the element we pushed
}
return permArr //return, but this only matters in the last call
};
Let's trace through the details using the array [4,3,2,1].
When it's first passed in, we'll take out the 4, push it to usedChars, remove it from input, and call permute on [3,2,1]. In this call, we'll push 3 to usedChars, remove it from input, and call permute on [2,1]. Then we push 2 to usedChars, remove it from input, and callpermuteon [1]. Then we push 1 tousedChars, and remove it frominput`.
This leaves us four calls deep and at step (2) with:
ch=1
input=[]
usedChars=[4,3,2,1]
At step (2), we're going to push our first permutation [4,3,2,1] to permArr. Then, moving on, since input is now empty the recursive call in (3) will simply return and in (4) we will simply add 1 back into input and remove 1 from usedChars--and this call returns.
So, at this point, we have started backing up our recursive calls and sit at step (4) with:
ch=2
input=[1]
usedChars=[4,3,2]
Step (4) will perform the critical step of the algorithm: the moving action. It takes ch=2 and adds it to the beginning of input and removes it from usedChars. This means that after step (5), we have:
ch=2
input=[2,1]
usedChars=[4,3]
Now take a look at where we are. We pushed [4,3,2,1] as a permutation, then backed up and swapped 2 and 1, and now we're going to go back into recursive calls to build [4,3,1,2] and add it as a permutation. After that we will back out some more, move around some more elements, and go back into the permutations and add them.
Getting back into it, after step (5) is executed we loop. That means we will push 1 to usedChars and make a recursive call with input=[2]. That call will push 2 into usedChars creating a the full array [4,3,1,2] and causing it to be added to permArray.
So, you're going to cycle up and down through the recursive calls building up a permutation, backing back out, rebuilding a different permutation, and backing out until you've looped over every possible combination.
I hope this helps!
