Javascript 递归函数。将数据存储在数组中时出现错误结果

Question

在尝试使用堆算法获取所有排列时，我遇到了将结果存储在数组中的问题。

生成的结果是(来自console.log(arr);)
[“1”、“2”、“3”]
[“2”、“1”、“3”]
[“3”、“1”、“2”]
[“1”、“3”、“2”]
[“2”、“3”、“1”]
[“3”、“2”、“1”]

但只有最后一个值存储在 arr 中，并且以某种方式存储的数组是这样的(来自 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"]*/

这是怎么回事？很想了解。谢谢

Answer 1

将 allPermutations.push(arr) 替换为 allPermutations.push(arr.slice())。

问题是，您一直在推送同一个数组，然后更改该数组。当你推送一个数组时，你不会推送它的副本:你推送一个引用。只有一个数组，以及对它的六个引用；当你读出它们时，它们读起来都是一样的，因为它们都是同一个数组。

.slice() 将为您提供一个包含相同元素的新数组；这样，您会在结果中得到六个新数组，而不是同一数组的六次提及。

来 self 之前的一个几乎但不完全重复的答案，我喜欢这个比喻:

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.