通过Heap算法和神秘逗号进行排列

Question

我花了一整天时间（最后）在实践中围绕一个排列算法绕过周五的入学申请。 Heap的算法对我来说似乎最简单和优雅。

这是一个例子：http://en.wikipedia.org/wiki/Heap%27s_algorithm

 function permutationArr(num) { 
    var str = num.toString();
    var arr = str.split('');
    var permutations = [];   
    function getPerm(arr,n){   
        var localArr = arr.slice(0);
        var i;
        var swap;
        var temp; 
        if(n==1){
            permutations.push(localArr.toString());
            return;
        }
        for(i=0;i<n;i++){
            getPerm(localArr,n-1);    
            swap = (n%2 ? i: 0);
            temp = localArr[swap];
            localArr[swap] = localArr[n-1];
            localArr[n-1] = temp;    
        }
    }    
    getPerm(arr,arr.length);
    console.log(permutations);
    return;    
}    
permutationArr(1234);     

最终排列数组的日志如下：

 ["1,2,3,4", "1,3,2,4", "4,2,3,1", "4,3,2,1", "4,1,3,2", "4,3,1,2", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2", "1,2,3,4,", "1,3,2,4,", "4,2,3,1,", "4,3,2,1,", "4,1,3,2,", "4,3,1,2,", "1,,3,4,2", "1,3,,4,2", "4,,3,1,2", "4,3,,1,2", "4,1,3,,2", "4,3,1,,2"]

它获得了前12个排列，然后一个'，'被神秘地添加，并且前12个排列被重复。我很难过。

编辑：上面是更新的代码考虑到评论说的帮助。仍然只有一半的排列。

Answer 1

问题，除了使用你应该使用n的索引n - 1之外，你假设数组必须在调用之间复制（即不可变行为）。

该算法假定数组在每个递归步骤中始终相同，因此，由于JavaScript处理范围的方式，您可以大大简化代码：

function permutationArr(num) 
{ 
  var arr = (num + '').split(''),
  permutations = [];   

  function swap(a, b)
  {
    var tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
  }

  function generate(n) {
    if (n == 1) {
      permutations.push(arr.join());
    } else {
      for (var i = 0; i != n; ++i) {
        generate(n - 1);
        swap(n % 2 ? 0 : i, n - 1);
      }
    }
  }

  generate(arr.length);
  return permutations;
}    

console.log(permutationArr(1234)); 

Output

["1,2,3,4", "2,1,3,4", "3,1,2,4", "1,3,2,4", "2,3,1,4", "3,2,1,4", "4,2,3,1",
 "2,4,3,1", "3,4,2,1", "4,3,2,1", "2,3,4,1", "3,2,4,1", "4,1,3,2", "1,4,3,2", 
 "3,4,1,2", "4,3,1,2", "1,3,4,2", "3,1,4,2", "4,1,2,3", "1,4,2,3", "2,4,1,3", 
 "4,2,1,3", "1,2,4,3", "2,1,4,3"]

Answer 2

自2018年1月以来更新的答案：接受的答案绝对正确，但从那时起js已经发展。随之而来的是一些新功能，其中2个可以帮助这个答案。

Array destructuring：

let [a, b] = [1, 2]; // a=1, b=2

Generators：

function *foo {
  yield 1;
  yield 2;
  yield 3;
}
const bar = foo();
bar.next(); // 1
bar.next(); // 2
bar.next(); // 3

有了这个，我们可以像这样实现Heap's algorithm：

function *heaps(arr, n) {
  if (n === undefined) n = arr.length;
  if (n <= 1) yield arr;
  else {
    for (let i = 0; i < n - 1; i++) {
      yield *heaps(arr, n-1);
      if (n % 2 === 0) [arr[n-1], arr[i]] = [arr[i], arr[n-1]];
      else             [arr[n-1], arr[0]] = [arr[0], arr[n-1]];
    }
    yield *heaps(arr, n-1);
  }
}


for (let a of heaps([1, 2, 3, 4])) {
  console.log(`[${a.join(', ')}]`);
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

我正在分享这个答案，因为我想展示一下旧javascript中的一小部分功能是如何简洁明了的。编写在最古老的javascript引擎和端口中运行的代码有时可以轻松地运行到其他语言（例如C）。在这种情况下使用回调很有效，因为它使该函数可用于更广泛的用途，例如减少大量在创建时将排列设置为唯一集。

非常短的变量名称可以使算法更清晰。

function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t }
function perm(arr, n, cb) {
    if (n === 1) {
        cb(arr);
    } else {
        for (var i = 0; i < n; i++) {
            perm(arr, n - 1, cb);
            swap(arr, n % 2 ? 0 : i, n - 1);
        }
    }
}

perm([1,2,3,4], 4, function (p) {
    console.log(p);
})

这是一个非常有用的测试功能，因此我将其用于我使用的数据驱动测试工具包：

https://github.com/quicbit-js/test-kit#tpermut-