我有一个这样的数组
[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');
尝试递归方法。这里有一个提示： 的每个排列[0,2,3]都是
[0]加上[2,3]或的排列[2]加上[0,3]或的排列[3]加上一个排列[0,2]正如 zodiac 所说，这个问题的最佳解决方案是递归解决方案：
var permute = (function () {
return permute;
function permute(list) {
return list.length ?
list.reduce(permutate, []) :
[[]];
}
function permutate(permutations, item, index, list) {
return permutations.concat(permute(
list.slice(0, index).concat(
list.slice(index + 1)))
.map(concat, [item]));
}
function concat(list) {
return this.concat(list);
}
}());
alert(JSON.stringify(permute([1,2,3])));希望有帮助。
可以通过选择集合中的一个元素并递归地排列（重新排列）剩余元素来找到集合的所有排列。回溯法可用于寻找解决方案。
算法步骤（来源）：
伪代码（来源）：
permute(i)
if i == N output A[N]
else
for j = i to N do
swap(A[i], A[j])
permute(i+1)
swap(A[i], A[j])
Javascript 实现（jsFiddle）：
Array.prototype.clone = function () {
return this.slice(0);
};
var input = [1, 2, 3, 4];
var output = [];
function permute(i) {
if (i == input.length)
output.push(input.clone());
else {
for (var j = i; j < input.length; j++) {
swap(i, j);
permute(i + 1);
swap(i, j); // backtrack
}
}
};
function swap(i, j) {
var temp = input[i];
input[i] = input[j];
input[j] = temp;
}
permute(0);
console.log(output);
对于长度为 n 的数组，我们可以预先计算可能排列的数量。这是n！(n 阶乘)
function factorial(n){ return n<=0?1:n*factorial(n-1);}
//There are better ways, but just for illustration's sake
而且，我们可以创建一个函数，将 0...n!-1 之间的整数 p 映射到不同的排列。
function map(p,orgArr){
var tempArr=orgArr.slice(); //Create a copy
var l=orgArr.length;
var permArr=[];
var pick;
do{
pick=p%l; //mod operator
permArr.push(tempArr.splice(pick,1)[0]); //Remove item number pick from the old array and onto the new
p=(p-pick)/l;
l--;
}while(l>=1)
return permArr;
}
此时，您需要做的就是创建一个数组ordering=[0,1,2,3,...,factorial(n)-1]并对其进行洗牌。然后，你可以循环for(var i=0;i<=ordering.length;i++) doSomething(map(ordering[i],YourArray));
这只是留下了如何打乱排序数组的问题。我相信这是有据可查的并且超出了您的问题范围，因为答案取决于您的应用程序（即伪随机足够好，或者您是否需要一些加密强度、所需的速度等......）。请参阅如何随机化（随机播放）JavaScript 数组？和许多其他人。
或者，如果排列的数量如此之大，以至于您不想创建这个巨大的排序数组，您只需为上述循环在 0-n!-1 之间明确选择 i 的值。如果只需要一致性而不是随机性，一种简单的方法是使用原始根：http ://en.wikipedia.org/wiki/Primitive_root_modulo_n
你不需要递归。该演示应该使模式非常清晰：http: //jsfiddle.net/BGYk4/
function shuffle(arr) {
var output = [];
var n = arr.length;
var ways = [];
for(var i = 0, j = 1; i < n; ways.push(j *= ++i));
var totalWays = ways.pop();
for(var i = 0; i < totalWays; i++) {
var copy = arr.slice();
output[i] = [];
for(var k = ways.length - 1; k >= 0; k--) {
var c = Math.floor(i/ways[k]) % (k + 2);
output[i].push(copy.splice(c,1)[0]);
}
output[i].push(copy[0]);
}
return output;
}
这应该输出所有可能的“洗牌”
console.log(shuffle(['a', 'b', 'c', 'd', 'e']));
这个更可爱（但另一个示例的输出更清晰）：http: //jsfiddle.net/wCnLf/
function shuffle(list) {
var shufflings = [];
while(true) {
var clone = list.slice();
var shuffling = [];
var period = 1;
while(clone.length) {
var index = Math.floor(shufflings.length / period) % clone.length;
period *= clone.length;
shuffling.push(clone.splice(index,1)[0]);
}
shufflings.push(shuffling);
if(shufflings.length == period) return shufflings;
}
}
当然它仍然输出所有可能的“洗牌”
console.log(shuffle(['a', 'b', 'c', 'd', 'e']));
上面的tibos示例正是我正在寻找的，但我在运行它时遇到了一些问题，我将另一个解决方案作为 npm 模块：
var generator = new Permutation([1, 2, 3]);
while (generator.hasNext()) {
snippet.log(generator.next());
}<script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script>
<script src="http://rawgit.com/bcard/iterative-permutation/master/iterative-permutation.js"></script>