javascript - 尽可能多地打乱数组

Question

我有一个这样的数组

[0,2,3]

这个数组可能的洗牌是

[0,2,3], [2,3,0], [3,0,2], [3,2,0], [0,3,2], [2,0,3]

如何获得这些组合？我目前唯一的想法是

n = maximum num of possible combinations, coms = []
while( coms.length <= n )
    temp = shuffle( original the array );
    if temp is there in coms
       return
    else 
       coms.push(temp);

但我不认为这是高效的，因为这里我们盲目地依赖均匀分布的 shuffle 方法。

这个问题是否有其他发现？

Answer 1

首先要注意的是，排列的数量相对于元素的数量增加得非常快(13 个元素 = 60 亿个排列)，因此对于足够大的输入，任何生成它们的算法的性能都会下降数组。

要注意的第二件事是，由于排列的数量非常大，将它们存储在内存中的成本很高，因此最好使用生成器来生成排列并在生成它们时对其进行处理。

第三个需要注意的是，递归算法带来的开销很大，所以即使找到了递归的解法，也要争取得到非递归的解法。如果存在递归解决方案，则始终可以获得非递归解决方案，但这可能会增加代码的复杂性。

我已经为您编写了一个基于 Steinhaus–Johnson–Trotter 算法 ( http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm ) 的非递归实现

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

function factorial(n) {
  var val = 1;
  for (var i=1; i<n; i++) {
    val *= i;
  }
  return val;
}


function permute(perm, func){
  var total = factorial(perm.length);

  for (var j=0, i=0, inc=1;  j<total;  j++, inc*=-1, i+=inc) {

    for (; i<perm.length-1 && i>=0; i+=inc) {
      func.call(perm);
      swap (perm, i, i+1);
    }  

    func.call(perm);

    if (inc === 1) {
      swap(perm, 0,1);
    } else {
      swap(perm, perm.length-1, perm.length-2);
    }
  }
}

console.clear();

count = 0;
permute([1,2,3,4,5,6], function(){console.log(this); count++;});

console.log('There have been ' + count + ' permutations');

http://jsbin.com/eXefawe/2/edit