我试图写一个函数，它做以下工作:
以一个整数数组作为参数(例如[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中做到这一点
const removeItem = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i+1));
}
const makePermutations = (strArr) => {
const doPermutation = (strArr, pairArr) => {
return strArr.reduce((result, permutItem, i) => {
const currentPair = removeItem(pairArr, i);
const tempResult = currentPair.map((item) => permutItem+item);
return tempResult.length === 1 ? result.concat(tempResult) :
result.concat(doPermutation(tempResult, currentPair));
}, []);
}
return strArr.length === 1 ? strArr :
doPermutation(strArr, strArr);
}
makePermutations(["a", "b", "c", "d"]);
//result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]
这里有另一种“更递归”的解决方案。
function perms(input) {
var data = input.slice();
var permutations = [];
var n = data.length;
if (n === 0) {
return [
[]
];
} else {
var first = data.shift();
var words = perms(data);
words.forEach(function(word) {
for (var i = 0; i < n; ++i) {
var tmp = word.slice();
tmp.splice(i, 0, first)
permutations.push(tmp);
}
});
}
return permutations;
}
var str = 'ABC';
var chars = str.split('');
var result = perms(chars).map(function(p) {
return p.join('');
});
console.log(result);
var output = window.document.getElementById('output');
output.innerHTML = result;
<div id="output"></div>
输出:
[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
大多数其他答案没有利用新的javascript生成器函数，这是一个完美的解决这类问题。在内存中，一次可能只需要一个排列。此外，我更喜欢生成一系列索引的排列，因为这允许我对每个排列进行索引，并直接跳转到任何特定的排列，以及用于排列任何其他集合。
// ES6 generator version of python itertools [permutations and combinations]
const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; }
const isEmpty = arr => arr.length === 0;
const permutations = function*(a) {
const r = arguments[1] || [];
if (isEmpty(a)) yield r;
for (let i of range(a.length)) {
const aa = [...a];
const rr = [...r, ...aa.splice(i, 1)];
yield* permutations(aa, rr);
}
}
console.log('permutations of ABC');
console.log(JSON.stringify([...permutations([...'ABC'])]));
const combinations = function*(a, count) {
const r = arguments[2] || [];
if (count) {
count = count - 1;
for (let i of range(a.length - count)) {
const aa = a.slice(i);
const rr = [...r, ...aa.splice(0, 1)];
yield* combinations(aa, count, rr);
}
} else {
yield r;
}
}
console.log('combinations of 2 of ABC');
console.log(JSON.stringify([...combinations([...'ABC'], 2)]));
const permutator = function() {
const range = function*(args) {
let {begin = 0, count} = args;
for (let i = begin; count; count--, i+=1) {
yield i;
}
}
const factorial = fact => fact ? fact * factorial(fact - 1) : 1;
return {
perm: function(n, permutationId) {
const indexCount = factorial(n);
permutationId = ((permutationId%indexCount)+indexCount)%indexCount;
let permutation = [0];
for (const choiceCount of range({begin: 2, count: n-1})) {
const choice = permutationId % choiceCount;
const lastIndex = permutation.length;
permutation.push(choice);
permutation = permutation.map((cv, i, orig) =>
(cv < choice || i == lastIndex) ? cv : cv + 1
);
permutationId = Math.floor(permutationId / choiceCount);
}
return permutation.reverse();
},
perms: function*(n) {
for (let i of range({count: factorial(n)})) {
yield this.perm(n, i);
}
}
};
}();
console.log('indexing type permutator');
let i = 0;
for (let elem of permutator.perms(3)) {
console.log(`${i}: ${elem}`);
i+=1;
}
console.log();
console.log(`3: ${permutator.perm(3,3)}`);
这是我做的一个…
const permute = (ar) =>
ar.length === 1 ? ar : ar.reduce( (ac,_,i) =>
{permute([...ar.slice(0,i),...ar.slice(i+1)]).map(v=>ac.push([].concat(ar[i],v))); return ac;},[]);
又来了，只不过写得不那么简洁了……
function permute(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([].concat(inputArray[index],value)));
return accumulator;
},[]);
}
工作原理:如果数组比一个元素长，它会遍历每个元素，并将其与对自身的递归调用连接起来，其余元素作为参数。它不会改变原始数组。
我改进了SiGanteng的答案。
现在可以多次调用permute，因为permArr和usedChars每次都被清除。
function permute(input) {
var permArr = [],
usedChars = [];
return (function main() {
for (var i = 0; i < input.length; i++) {
var ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
main();
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr;
})();
}
函数排列（输入） {
var permArr = []，
使用的字符 = [];
return （函数 main（） {
for （var i = 0; i < input.length; i++） {
var ch = input.splice（i， 1）[0];
usedChars.push（ch）;
if （input.length == 0） {
permArr.push（usedChars.slice（））;
}
主（）;
input.splice（i， 0， ch）;
usedChars.pop（）;
}
返回permArr;
})();
}
document.write（JSON.stringify（permute（[5， 3， 7， 1]）））;
const removeItem = (arr, i) => {
return arr.slice(0, i).concat(arr.slice(i+1));
}
const makePermutations = (strArr) => {
const doPermutation = (strArr, pairArr) => {
return strArr.reduce((result, permutItem, i) => {
const currentPair = removeItem(pairArr, i);
const tempResult = currentPair.map((item) => permutItem+item);
return tempResult.length === 1 ? result.concat(tempResult) :
result.concat(doPermutation(tempResult, currentPair));
}, []);
}
return strArr.length === 1 ? strArr :
doPermutation(strArr, strArr);
}
makePermutations(["a", "b", "c", "d"]);
//result: ["abcd", "abdc", "acbd", "acdb", "adbc", "adcb", "bacd", "badc", "bcad", "bcda", "bdac", "bdca", "cabd", "cadb", "cbad", "cbda", "cdab", "cdba", "dabc", "dacb", "dbac", "dbca", "dcab", "dcba"]
