9

I've been staring at this answer to this question forever, even writing down variables and whatnot through each iteration. I simply just don't get the process here. When I throw in console logs I see that permute is called input.length - 1 times before it ever gets to this line input.splice(i, 0, ch);.

It's hard to phrase the question when I am lost completely, but I guess some curiosities are:

  • each time permute is called, it is a new instance of that function with it's own closure, right?
  • therefore variables' changes that are within the function won't affect variables in other calls?
  • does the function return permArr for each time it's called?
  • and I suppose that doesn't necessarily affect the return of the first call? (my instinct tells me that the first time return happens, the function stops running).

Thanks for the insights.

var permArr = [], usedChars = []; function permute(input) { var i, ch; for (i = 0; i < input.length; i++) { ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } permute(input); input.splice(i, 0, ch); usedChars.pop(); } return permArr };

Permutations in JavaScript?

Improve this question
1

4 Answers 4

Reset to default
23

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!

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

HI Rick. Thanks for the detailed explanation. I wanted to ask - 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]. How did ch become 2 here?
A year later... But I think the reason ch became 2 is that when we "back up", since we call the function recursively, each call holds their own variables. So When you call permute(input), it adds a character to ch, but when it's done that 4 times, and it starts backing up, each time you return permArr, it goes back to the previous call. So if the last call is ch=1, then the call before that would be ch=2, and the call before that would be ch=3, and the call before that would be ch=4. Please correct me if I'm wrong.
"input.splice(i, 0, ch); // 4. add the original element to the beginning" are you sure about that? does it not rather mean "at index i, remove 0 elements and insert ch shifting the rest one position to the right" - at the same index i?? it sure should, otherwise the algorithm would be wrong.
3

The code is a bit hard to follow, because it's a mix of looping and recursion. It uses a global variable (usedChars) that is changed and restored during each call.

"each time permute is called, it is a new instance of that function with it's own closure right? therefore variables changes that are within the function won't affect variables in other calls?"

Well, yes and no. Each function call has its own scope, but as there are no variables that needs catching, there is no closure. The local variables i and ch and the parameter input are local to the scope, so each call has their own set of those variables. Any other variables are global, so they are shared between all calls.

The variable usedChars is changed in the code, and that change is visible to the code when the function does the recursive call, and then the variable is changed back to the previous state for the next iteration. When the function exists, the variable has the value that it had when the function was entered.

"does the function return permArr for each time it's called?"

Yes, but when the function calls itself, the return value is ignored. It's only when the array is returned from the outermost call that it is used.

Improve this answer

Comments

1

In order to understand unknown code, it always helps me to try to comment it myself and possibly change some variable names to reflect their intent better. Here is how I read that (old) example. Note that I took the liberty to rename usedChars to tempArr and to remove the return statement, because the recursion never uses the return value.

let permArr = []; let tempArr = []; /** * Finds all permutations of the given input string and adds them * to global array 'permArr'. * Uses a global array 'tempArr' for building new permutations. * @param {string} input */ function permute( /* string */ input) { // Convert input string into an array of characters. const chars = input.split(""); for (let i = 0; i < chars.length; i++) { // Get i-th character and remove it from array. // Note: the 'splice' method returns an array of length 1. const ch = chars.splice(i, 1)[0]; // Append character to new permutation. tempArr.push(ch); // When there are no characters remaining... if (chars.length === 0) { // ... have found a new permutation. // Append it to output array. permArr.push( tempArr.join("") ); } // Recurse with shortened input string. permute(chars.join("")); // Clean up for next iteration: // - remove character from new permutation. tempArr.pop(); // - put character back into input string. chars.splice(i, 0, ch); } }; permute("abc"); console.log( permArr ); /* [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ] */ // Reset output array. permArr = []; permute("1234"); console.log( permArr ); /* [ '1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132', '4213', '4231', '4312', '4321' ] */

By the way, this code - while certainly correct - does show potential for tuning.

The code above directly reflects the traditional proof that the total number of permutations of N elements equals factorial(N). The proof usually runs by induction like this:

(Induction step): Take each of the given N elements and write it into the first position of a new array, which gives you N possibilities. Now use the induction hypothesis and for each of those N cases append all factorial(N-1) permutations of the remaining N-1 elements, which results in a total of N * factorial(N-1) permutations. And this equals factorial(N). QED.

Improve this answer

Comments

0

It implements the same algorithm under the "shrinking domain" paradigm as I have also implemented in this answer of mine (the code in that answer is in Common Lisp and uses linked lists for efficiency, but the answer also includes lots of discussion and some pseudocode).

The variable usedChars should really be called permutation:

GLOBAL: resultArray, permutation interface_function(input): resultArray = [] permutation = [] call work_function(input) // here resultArray contains copies of // all the permutations of input work_function(input): if input is empty: // innermost level: process permutation // permutation is ready else: for each index in input: pluck ch out from input at index add ch at the permutation's end call work_function(input) // with the shrunk input pop ch out of permutation's end insert ch back into input at same index // restore input!

The loops with recursion create n nested loops computational structure at run time, with real work done at the innermost loop on the deepest invocation level. Each time one element is plucked away from input in a given for loop, and is placed at the end of the permutation:

for each index in input: ch1, input1 = pull_from(input, index) // input1 is input with elt at index pulled away // so, 1 elt shorter than input for each index in input1: ch2, input2 = pull_from(input1, index) // input2 is input1 with elt at index pulled away // so, 1 elt shorter than input1 for each index in input2: ........ ........ input_n is empty: permutation = [ch1, ch2, ch3, ..., ch_n] process permutation

At the deepest level permutation is ready and its copy is added into the overall result array that will hold all permutations in the end.

The result is not returned, but is being built up in the innermost loop level, working in "inversion of control" paradigm. Instead of calling an explicitly user-supplied "callback", the result array permArr is directly pushed into, adding one more element (which is a freshly allocated copy of the current permutation) into it when it is ready, at the deepest invocation:

 if (input.length == 0) { permArr.push(usedChars.slice()); }

The function could return any value. It is used for its side effect which is to build the array holding all the permutations. It could just print them right there instead without building the gigantic result array if all it needs to do is to print them.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.