Heap's Algorithm Permutation JavaScript and Recursions' Stack?

Question

I have an assignment to count repeated strings base on a Heap's Algorithm Permutation.The first thing I want to do is output the swapped strings, I found this code from jake's answer Can someone please help me understand recursion within this code in a loop? The output of this function are swapped strings.

function permAlone(string) {

var arr = string.split(''),   // Turns the input string into a letter array.
          permutations = []; // results

function swap(a, b) {  
debugger; // This function will simply swap positions a and b inside the input array.
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

function gen(n) {   
  debugger;
  if (n === 1) {  
  var x =arr.join('');
  permutations.push(x);  
  } else {
  for (var i = 0; i != n; i++) { // how does this loop executes within the call stack?  
    gen(n - 1);
    debugger;
    swap(n % 2 ? 0 : i, n - 1); // i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here
  }   
 }
}
 gen(arr.length);
 return permutations;
}
permAlone('xyz'); // output -> ["xyz","yxz","zxy","xzy","yzx","zyx"]

I have been experimenting it on debugger but still can't get what's happening.

Answer 1

I'm not sure what you mean by

understand recursion within this code in a loop

If you mean you want to see the algorithm in a loop form rather than a recursion version you can see them one by side in pseudocode in the wikipedia page here.

For your questions within the code:

how does this loop executes within the call stack?

You are right to refer to the call stack, and this is a general question regarding recursion. If you don't understand how recursion works with the stack you can refer to this really nice and simple video that demonstrates recursive calls using factorial calculation in java (start around min 4:00).

The line you look at is no different than any other line in the recursive function. We start by defining i and assigning the value 0 to it. We continue to check if it satisfies the condition of the for loop. If it does we step into the loop and execute the first line inside the loop which is the recursive call. Inside the recursive call we have a new stack frame which has no knowledge of the i variable we defined before executing the recursive call, because it is a local variable. So when we get to the loop in the new call we define a new variable i, assigning it 0 at first and incrementing it as the loop repeats in this stack frame/call instance. When this call finishes we delete the stack frame and resume to the previous stack frame (the one we started with) where i=0 still, and we continue to the next line. All the calls have access to the arr and permutations variables since the function is defined in the same scope as the variables (inside the function permAlone) so within each call - no matter what the stack frame we are in, the changes made to those are made to the same instances. That's why every push done to permutations adds to the existing results and will be there when the function returns the variable at the end.

i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here

Indexes are not swapped here. It is merely a call for the swap function with the correct indices.

swap(n % 2 ? 0 : i, n - 1);

is just

swap(a, b);

with

a = n% 2 ? 0 : i;
b = n - 1;

If the a part is what confuses you, then this is a use of the ternary operator for conditional value. That is, it's symbols used to form an expression that is evaluated differently according to the circumstances. The use is by

<<i>boolean epression</i>> ? <<i>value-if-true</i>> : <<i>value-if-false</i>>

to evaluate the above, first <boolean expression> is evaluated. If it's value it true then the whole expression is evaluated as <value-if-true>. Otherwise, the whole expression is evaluated as <value-if-false>.

In the code itself, for a, n % 2 is the boolean expression - js divides n by 2 and takes the remainder. The remainder is either 1 or 0. js implicitly converts those to true and false respectively. So if n is odd we get

a = 0

and if it's even we get

a = i

as the algorithm requires.