Javascript 递归排列生成器

Question

我正在尝试在 Javascript 中实现递归排列生成器，但我似乎无法让它通过所有递归分支（请参阅下面的结果）。

我知道我遗漏了一些重要的东西，有人可以帮助我了解哪里出了问题吗？

    var permute = function(input){
        var permutation = function (arr, position){
            if(position >= arr.length-1){
                results.push(arr);
            }else{
                var tempSwap="";
                for(i=position;i<arr.length;i++){
                    tempSwap = arr[position];
                    arr.splice(position,1,arr[i]);
                    arr.splice(i,1,tempSwap);
                    permutation(arr,(position+1));
            }
            return;
        }
    };

    permutation(input,0);
};

var results=[];
permute(['a','b','c']);
console.log(results);

结果： [ [ 'a', 'c', 'b' ], [ 'a', 'c', 'b' ] ]

Answer 1

有两个错误：您在同一个数组上工作而没有制作副本，并且您的循环计数器 i 是一个全局变量。固定码：

 var permute = function(input){
        var permutation = function (arr, position){
            if(position == arr.length-1){ // >= was redundant and confusing
                results.push(arr);
            }else{
                for(var i=position;i<arr.length;i++){ // use local i
                    var tempSwap = arr[position];
                    arr.splice(position,1,arr[i]);
                    arr.splice(i,1,tempSwap);
                    permutation(arr.slice(),(position+1)); // you need a copy here
            }
            return;
        }
    };

    permutation(input,0);
};

var results=[];
permute(['a','b','c']);
console.log(results.join(' ')); // a,b,c a,c,b b,a,c b,c,a c,a,b c,b,a

https://jsfiddle.net/sagqkchL/1/

不复制导致所有结果数组看起来都一样。全局变量导致仅产生 2 个结果。

Answer 2

I know I'm missing important

您的 i 变量是 implictly global。用 var 声明它，你的基本问题就会消失。

此外，如评论中所述，您没有复制 input 数组，因此您总是在修改同一个对象（并以 result[0] == result[1] == … 结尾）；你太早结束了你的递归一级（基本情况是你已经结束了，而不是之前）；您还应该在 permute 函数中创建 results 数组。

function permute(input){
    function permutation(arr, position){
        if(position >= arr.length) {
            results.push(arr);
        } else {
            permutation(arr, position+1); // nothing is swapped, no need to copy anything
                                          // you can also omit this line and start i=position
            for (var i=position+1; i<arr.length; i++) {
                var tmp = arr.slice();
                tmp[position] = arr[i];
                tmp[i] = arr[position];
                permutation(tmp, position+1);
            }
        }
    };
    var results = [];
    permutation(input, 0);
    return results;
};

console.log(permute(['a','b','c'])); // [["a","b","c"],["a","c","b"],["b","a","c"],["b","c","a"],["c","b","a"],["c","a","b"]]

Javascript 递归排列生成器

Javascript recursive permutation generator

javascript

recursion

permutation