为什么我的置换算法为所有置换都提供相同的结果? [英] Why is my permutation algorithm giving me the same result for all permutations?

问题描述

这是我第一次不得不问自己一个关于SO的问题.我总是能找到解决大多数问题的答案，但是这次我被一些堆的置换算法所困扰.我一直在尝试解决这一挑战并没有成功，所以我来找你们，他们的编程知识比我还强.

This is the first time I have to ask a question myself on SO. I always find answers to solve most of my problems but this time I'm stuck with some heap's permutation algorithm. I've been trying to solve this challenge for a while without success so I come to you guys who have a better programming knowledge than me.

我写了一些Javascript代码来递归地找到一个值的所有可能排列:数组或字符串.当我用console.log()排列后的值时，我的代码似乎运行良好，但是当我将它们推入另一个数组时，所有这些值都得到相同的值.我很困惑.也许我在做些愚蠢的事.任何帮助将不胜感激，谢谢高级人员.

I wrote some Javascript code to recursively find every possible permutation of a value: either an array or a string. My code seems to work perfectly when I console.log() the permuted values but when I push them to another array I get the same value for all of them. I'm confused. Maybe I'm doing something stupid, who knows. Any help would be appreciated, thanks in advanced guys.

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

My code contains two separate functions: one does the swapping of the elements and the other one recursively find the possible permutation.

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);
        }
    }
};

推荐答案

这是简单的(堆)引用与(堆栈)值问题.原因很简单:所有递归调用中的arr都引用内存中的同一数组.因此，当您调用newArr.push(arr)时，对同一对象的另一个引用将添加到结果列表中.当您执行swap时，您将newArr的所有元素都交换为指向相同数组的元素.另请参见在JavaScript中按值复制数组，以获取可能的解决方法. (基本上使用 Array.slice 创建独立副本的方法).

This is simple (heap) reference vs. (stack) value question. The reason is quite simple: arr in all recursive calls references the same array in memory. Thus when you call newArr.push(arr) another reference to the same object is added to the result list. And when you do swap, you swap elements for all elements of newArr as they point to the same array. See also Copying array by value in JavaScript for a possible workaround. (Basically use Array.slice method to create an independent copy).

这篇关于为什么我的置换算法为所有置换都提供相同的结果?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！