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
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments