CODEWITHSUNDEEP
javascriptalgorithm
Kane
Kane

Reputation: 924

Strange behaviour of for loop in Heap's algorithm in JavaScript

I'm trying to implement Heap's algorithm to find different permutations of a string and found a strange behaviour with a for loop, here's the code

function permAlone(str) {

  var strArr = str.split(''),
  permutations = [];

  function swap(strArr, x, y) {
    var tmp = strArr[x];
    strArr[x] = strArr[y];
    strArr[y] = tmp;
  }

  function generate(n) {
    if (n === 1) {
        permutations.push(strArr.join());
    } else {
        for (var i = 0; i != n; i++) {
        generate(n - 1);
        swap(n % 2 ? 0 : i, n - 1);        
      }
    }
  }

  generate(strArr.length);

  return permutations;
}

console.log(permAlone('aab'));

In the for loop within the generate function, if I put i = 0 the output of the script is ['a,a,b', 'a,a,b'] but if I put var i = 0 the output is ['a,a,b', 'a,a,b', 'a,a,b', 'a,a,b', 'a,a,b', 'a,a,b'].

I understand that var i would create a local variable for the loop, but don't understand in this case why it would change how the loop functions as there is no i variable declared anywhere else in the script.

Thanks any help appreciated.

Upvotes: 0

Views: 50

Answers (1)

nnnnnn
nnnnnn

Reputation: 150080

The reason the behaviour changes if you have a global i variable is that you have multiple recursive calls to generate() all trying to control their own partially complete for loops with the same variable, and all setting i back to 0 when they start.

Picture what happens on the second iteration of the for loop: i is 1 because it has just been incremented, but then immediately a recursive call to generate() starts its own loop and sets i back to 0 again.

If you create a local variable with var then each for loop in each recursive call is independent of all the others.

Try stepping through the code with the debugger, or try adding the following as the first line inside the for loop and watch what happens to the variables when the code runs:

 console.log('n:' + n + '; i: '+i);

Upvotes: 2

Related Questions