Javascript Recursive function. Wrong results while storing data in array

Question

While trying to get all permutations using Heap's algorithm, I met trouble storing the results in array.

The result generated is (from console.log(arr);)
["1", "2", "3"]
["2", "1", "3"]
["3", "1", "2"]
["1", "3", "2"]
["2", "3", "1"]
["3", "2", "1"]

but only the last value is stored in the arr, and the array stored somehow is this (from console.log(JSON.stringify(allPermutations)); )
["3", "2", "1"]
["3", "2", "1"]
["3", "2", "1"]
["3", "2", "1"]
["3", "2", "1"]
["3", "2", "1"]

var allPermutations = [];

function swap(arr,index1,index2){
    var dummy = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = dummy;
    return arr;
}

function generate(n,arr){
    if(n==1){
        console.log(arr);
            //result:
            //["1", "2", "3"]
            //["2", "1", "3"]
            //["3", "1", "2"]
            //["1", "3", "2"]
            //["2", "3", "1"]
            //["3", "2", "1"]
        allPermutations.push(arr);
    }else{
        for(var i=0;i<n-1;i++){
            generate(n-1,arr);
            if( n%2 ==0){
                arr = swap(arr,i,n-1);
            }else{
                arr = swap(arr,0,n-1);
            }
        }
        generate(n - 1, arr);
    }
}

generate(3,['1','2','3']);

console.log(JSON.stringify(allPermutations));
/*result:
["3","2","1"]
["3","2","1"]
["3","2","1"]
["3","2","1"]
["3","2","1"]
["3","2","1"]*/

What's wrong with this? Would love to understand. Thanks

You keep passing the same array to the next function call, so it changes, and arrays are passed by "reference" (not really, but close enough) so the pushed array keeps changing as well. — adeneo
– adeneo, Commented Mar 22, 2016 at 2:22

Amadan · Accepted Answer · 2016-03-22 02:25:37Z

3

Replace allPermutations.push(arr) with allPermutations.push(arr.slice()).

The problem is, you keep pushing the same array, then changing that array. When you push an array, you don't push a copy of it: you push a reference. There is only one array, and six references to it; when you read them out, they all read the same, because they are all the same array.

.slice() will give you a new array with the same elements; this way, you get six new arrays into your result, instead of six mentions of the same array.

From one of my earlier answers that is almost-but-not-quite a duplicate, a metaphor I like for this:

As a metaphor, imagine a theatre director in casting. He turns to an actor, says "You... you'll be Romeo.". Then he looks at the same actor, says "You... you'll be Mercutio. Here, Mercutio, take this sword. Romeo... who told you to get a sword?!?" completely failing to realise that, if Romeo and Mercutio are the same person, if one of them picks up a sword, the other does it too.

edited Mar 22, 2016 at 2:25

answered Mar 22, 2016 at 2:20

Amadan

200k23 gold badges252 silver badges321 bronze badges

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

1 Comment

Jacob Goh Over a year ago

wow. That's it! Thanks for your awesome explanation. will accept your answer once the time limit has passed.

Oriol · Accepted Answer · 2016-03-22 02:22:00Z

That's because arrays are objects, and objects are passed by value, but that value is a reference.

Then, your code keeps pushing the same arr reference to allPermutations. But the values in that reference are modified later.

Instead, you should push a copy of the array. You can copy it with .slice().

var allPermutations = [];
function swap(arr, index1, index2) {
  var dummy = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = dummy;
  return arr;
}
function generate(n, arr) {
  if (n == 1) {
    allPermutations.push(arr.slice());
  } else {
    for (var i = 0; i < n - 1; i++) {
      generate(n - 1, arr);
      if (n % 2 == 0) {
        arr = swap(arr, i, n - 1);
      } else {
        arr = swap(arr, 0, n - 1);
      }
    }
    generate(n - 1, arr);
  }
}
generate(3, ['1', '2', '3']);
document.write(JSON.stringify(allPermutations));

Collectives™ on Stack Overflow

Javascript Recursive function. Wrong results while storing data in array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related