javascript - 为什么我的排列算法对所有排列给出相同的结果？

Question

我受困于某些堆的置换算法。我编写了一些 JavaScript 代码来递归地查找值的所有可能排列:数组或字符串。当我 console.log() 置换值时，我的代码似乎可以完美运行，但是当我将它们推送到另一个数组时，我得到的所有值都相同。我很困惑。

我的代码包含两个独立的函数:一个执行元素的交换，另一个递归地寻找可能的排列:

arr = ["a", "b", "c"];
newArr = [];

// swap mechanism here
function swap(arr, pos1, pos2) {
    var temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
};

function perm(arr, nArr, n) {
    n = n || arr.length; 
    if (n === 1) {
        console.log(arr); // console.log() works great
        newArr.push(arr); // pushing the permuted values does not
    }
    else {
        for(var i = 1; i <= n; i += 1) {
            perm(arr, nArr, n - 1);
            if (n % 2) {
                var j = 1;
            }
            else {
                var j = i;
            }
            swap(arr, j - 1, n - 1);
        }
    }
};

Answer 1

这是一个简单的(堆)引用与(堆栈)值问题。原因很简单:所有递归调用中的 arr 都引用内存中的同一个数组。因此，当您调用 newArr.push(arr) 时，对同一对象的另一个引用将添加到结果列表中。当您执行 swap 时，您会为 newArr 的所有元素交换元素，因为它们指向同一个数组。另见 Copying array by value in JavaScript一个可能的解决方法。 (基本上都是用Array.slice的方法来创建一个独立的副本)。