我试图写一个函数，它做以下工作:
以一个整数数组作为参数(例如[1,2,3,4])
创建一个包含[1,2,3,4]的所有可能排列的数组，每个排列的长度为4
下面的函数(我在网上找到的)通过接受一个字符串作为参数，并返回该字符串的所有排列来实现这一点
我不知道如何修改它，使它与整数数组一起工作，(我认为这与一些方法在字符串上的工作方式不同于在整数上的工作方式有关，但我不确定…)
let permArr = [];
let usedChars = [];
function permute(input) {
const chars = input.split("");
for (let i = 0; i < chars.length; i++) {
const ch = chars.splice(i, 1);
usedChars.push(ch);
if (chars.length === 0) {
permArr[permArr.length] = usedChars.join("");
}
permute(chars.join(""));
chars.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
注意:我希望函数返回整数数组，而不是字符串数组。
我真的需要解决方案是在JavaScript。我已经知道如何在python中做到这一点
一些受到Haskell启发的版本:
perms [] = [[]]
perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ]
function perms(xs) {
if (!xs.length) return [[]];
return xs.flatMap(x => {
// get permutations of xs without x, then prepend x to each
return perms(xs.filter(v => v!==x)).map(vs => [x, ...vs]);
});
// or this duplicate-safe way, suggested by @M.Charbonnier in the comments
// return xs.flatMap((x, i) => {
// return perms(xs.filter((v, j) => i!==j)).map(vs => [x, ...vs]);
// });
// or @user3658510's variant
// return xs.flatMap((x, i) => {
// return perms([...xs.slice(0,i),...xs.slice(i+1)]).map(vs => [x,...vs]);
// });
}
document.write(JSON.stringify(perms([1,2,3])));
这是Heap算法的实现(类似于@le_m算法)，只是它是递归的。
function permute_kingzee(arr,n=arr.length,out=[]) {
if(n == 1) {
return out.push(arr.slice());
} else {
for(let i=0; i<n; i++) {
permute_kingzee(arr,n-1, out);
let j = ( n % 2 == 0 ) ? i : 0;
let t = arr[n-1];
arr[n-1] = arr[j];
arr[j] = t;
}
return out;
}
}
它看起来也快得多:https://jsfiddle.net/3brqzaLe/
为了解决这个问题，我的想法如下…
1- (n)的总排列是(n!)
2-检查组合小n (n <= 4)。
3-应用递归技术。
if(n == 1) // ['a']
then permutation is (1) ['a']
if(n == 2) // ['a', 'b']
then permutations are (2) ['a', 'b'] ['b', 'a']
if(n == 3) // ['a', 'b', 'c']
then permutations are (6) ['a', 'b', 'c'] ['a', 'c', 'b'] ['b', 'a', 'c'] ['b', 'c', 'a'] ['c', 'a', 'b'] ['c', 'b', 'a']
所以…排列行为是有规律的。
和数组实例的总排列是…所有可能的子排列从原始数组中移除每个单个字符，并将该单个字符与它们相对的子排列连接起来。也许代码能更好地解释这一点。
Bye!
function permutations(array) {
let permutationList = [];
if(array.length == 1) {
return array;
}
for(let i = 0; i < array.length; i++) {
let arrayLength1 = [ array[i] ];
let auxArray = Object.values(array);
auxArray.splice(i, 1);
let subPermutations = this.permutations(auxArray);
for(let j = 0; j < subPermutations.length; j++) {
let arrayMerge = arrayLength1.concat(subPermutations[j]);
permutationList.push(arrayMerge);
}
}
return permutationList;
}
let results4 = permutations(['a', 'b' ,'c', 'd']);
let results6 = permutations(['a', 'b' ,'c', 'd', 'e', 'f']);
console.log(results4.length);
console.log(results4);
console.log(results6.length);
console.log(results6);
