我有一个这样的数组
[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 方法。
这个问题是否有其他发现?
最佳答案
首先要注意的是,排列的数量相对于元素的数量增加得非常快(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');
关于javascript - 尽可能多地打乱数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18681165/