Recursive function that generates the permutations of a string

Question

//====================================================
function getPermutations(str){
    //Enclosed data to be used by the internal recursive function permutate():
    var permutations = [],  //generated permutations stored here
        nextWord = [],      //next word builds up in here     
        chars = []          //collection for each recursion level
    ;
    //---------------------
    //split words or numbers into an array of characters
    if (typeof str === 'string') chars = str.split(''); 
    else if (typeof str === 'number') {
      str = str + ""; //convert number to string
      chars = str.split('');//convert string into char array
    }
    //============TWO Declaratives========
    permutate(chars);
    return permutations;
    //===========UNDER THE HOOD===========
    function permutate(chars){ //recursive: generates the permutations
        if(chars.length === 0)permutations.push(nextWord.join(''));            
        for (var i=0; i < chars.length; i++){
            chars.push(chars.shift());  //rotate the characters
            nextWord.push(chars[0]);    //use the first char in the array            
            permutate(chars.slice(1));  //Recurse: array-less-one-char
            nextWord.pop();             //clear for nextWord (multiple pops)
        }
    }
    //--------------------------------
}//==============END of getPermutations(str)=============

How is nextWord.pop() getting called multiple times? Won't permutate(chars.slice(1)); not let nextWord.pop() execute since it will take you back to the top of the permutate function?

Also, when chars becomes empty from calling slice on it permutate(chars.slice(1)); who is populating chars once again? Is chars being populated by nextWord.pop(); since pop is returning the value to the permutate function?

Stepping through this code in chrome debugger it wasnt clear.

Answer 1

function permutate(left, used, result) { 
    // If there are no more characters left to permute 
    if (0 == left.length) { 
       result.push(used); 
    } 

    // Iterate over all characters in the 'left' string
    for (var i = 0; i < left.length; ++i) { 
       // Read the character we are going to work with in this iteration 
       var iObject = left[i]; 

       // Create a new_left string that contains all the characters 
       // of the 'left' string without the one we are going to use now 
       var new_left = ''; 
       for (j = 0; j < left.length; ++j) { 
          if (j != so.i) new_left += so.left[j]; 
       } 

       // Create a new_used string that has all the characters of 'used'  
       // plus the one we are going to use now 
       var new_used = so.used + iObject; 

       // Call permute with new_left and new_used strings 
       permutate(new_left, new_used, result); 
    } 
} 

To run the function on some string you need to call it like this:

permutate('abcd', '', []);

For those who doesn't get this because of the recursion involved I found a page that illustrates the algorithm flow using interactive animations.

http://learntocode.guru/code/generate-permutations-recursively-string

Just click play and observe the variables change while the permutation function keeps calling itself. Also observe when a new permutation has been found and when it's added to the resulting permutations array.

Answer 2

Recursive call permutate is inside a loop and each time it is executed it is put on the call stack. The nextWord.pop is called multiple times to finish executing each of the recursive calls on the stack. You can visualize the recursion with this tool http://visualgo.net/recursion.html. If you have a tool such as Webstorm, you can run it in the debugger to see that there are three permutate() calls in the stack when the first time nextWord.pop is called.

Answer 3

Calling permutate will not reset you at the top of permutate. (as was mentioned by joe) It will simply wait for this child call to complete and then continue executing the method.

I think your recursive permutate could be simplified:

// suppose input = "abc"
permutate(chars) {
  if(chars.length === 2) return [chars, chars[0] + chars[1]};
  var arr = permutate(chars.slice(1)) // returns ["bc", "cb"]
  var out = []    
  for (var i=0; i < arr.length; i++) {
    for (var j = 0; j < chars.length - 1; ++j) {
      out.push(arr[i].split(0,j) + chars[0] +  arr[i].split(j)) // "a" gets inserted at every possible position in each string
    }
  }
  // result here is ["abc", "bac", "bca", "acb", "cab", "cba"]
  return out
}

Answer 4

chars.slice(1) is the character array chars starting at position 1, i.e. the second character, so calling permutate(chars.slice(1)); recurses with 1 fewer characters.

Eventually, chars.slice(1) will return zero characters, at which point permutations.push(nextWord.join('')); is executed and for (var i=0; i < chars.length; i++) will not execute the loop block inside because its terminating condition i < chars.length will already be false when the initial value of i is 0 and chars.length is also zero.

So the terminating condition of this recursive function is when it runs out of characters in the current word.

When the the permutate function finally returns, nextWord.pop() is called once for each time permutate was called.

Answer 5

It would execute after premutate() returns. But I guess that's obvious from looking at the code. I think your question is how can premutate ever reutrn? The answer to that is to look at the for loop.

Since we're calling premutate() with one fewer character every time. It makes sense that at some point one of our calls to premutate() will be called with an empty array:

premutate([]); // happens when chars.slice(1) gives us an empty array

Now, let's see what happens when that happens:

function permutate(chars){

    // The following gets executed:
    if(chars.length === 0)permutations.push(nextWord.join(''));

    // This for loop is skipped because 0 < 0 is false
    for (var i=0; i < chars.length; i++){/*...*/}

    // we return because we skipped the for loop
}

Now that the base-case have returned, all the other calls to premutate() also returns:

function permutate(chars){
    if(chars.length === 0)permutations.push(nextWord.join(''));
    for (var i=0; i < chars.length; i++){
        chars.push(chars.shift());
        nextWord.push(chars[0]);
        permutate(chars.slice(1));  // This have returned..
        nextWord.pop();             // so execute this line
    }

    // and return so that other calls to us can also execute pop()
}