我花了一整天时间(最后)在周五的一个入学申请实践中围绕一个排列算法.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最终排列数组的日志如下:
["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个排列被重复.我很难过.
编辑:上面是更新的代码考虑到评论说的帮助.仍然只有一半的排列.
除了使用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));
自2018年1月以来更新的答案:接受的答案绝对正确,但从那时起js已经发展.随之而来的是一些新功能,其中2个可以帮助这个答案.
数组解构:
let [a, b] = [1, 2]; // a=1, b=2
发电机:
function *foo { yield 1; yield 2; yield 3; } const bar = foo(); bar.next(); // 1 bar.next(); // 2 bar.next(); // 3
有了这个,我们可以像这样实现Heap的算法:
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; }