我正在尝试编写一个执行以下操作的函数:
- 将整数数组作为参数(例如[1,2,3,4])
- 创建[1,2,3,4]的所有可能排列的数组,每个排列的长度为4
下面的函数(我在网上找到了它)通过将字符串作为参数并返回该字符串的所有排列来实现
我无法弄清楚如何对其进行修改以使其能够与整数数组一起使用,(我认为这与某些方法在字符串上的处理方式与在整数上的处理方式不同有关,但是我不确定。 ..)
var permArr = [], usedChars = [];
function permute(input) {
var i, ch, chars = input.split("");
for (i = 0; i < chars.length; i++) {
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中做到这一点
如果您注意到,代码实际上会在进行任何置换之前将字符拆分为一个数组,因此您只需删除联接和拆分操作
var permArr = [],
usedChars = [];
function permute(input) {
var i, ch;
for (i = 0; i < input.length; i++) {
ch = input.splice(i, 1)[0];
usedChars.push(ch);
if (input.length == 0) {
permArr.push(usedChars.slice());
}
permute(input);
input.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
document.write(JSON.stringify(permute([5, 3, 7, 1])));
有点晚了,但是喜欢在这里添加一个稍微更优雅的版本。可以是任何数组...
function permutator(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);
}
return results;
}
return permute(inputArr);
}
添加了ES6(2015)版本。也不会突变原始输入数组。在Chrome的控制台中运行...
const permutator = (inputArr) => {
let result = [];
const permute = (arr, m = []) => {
if (arr.length === 0) {
result.push(m)
} else {
for (let i = 0; i < arr.length; i++) {
let curr = arr.slice();
let next = curr.splice(i, 1);
permute(curr.slice(), m.concat(next))
}
}
}
permute(inputArr)
return result;
}
所以...
permutator(['c','a','t']);
产量...
[ [ 'c', 'a', 't' ],
[ 'c', 't', 'a' ],
[ 'a', 'c', 't' ],
[ 'a', 't', 'c' ],
[ 't', 'c', 'a' ],
[ 't', 'a', 'c' ] ]
和...
permutator([1,2,3]);
产量...
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
以下非常有效的算法使用Heap方法生成N个元素的所有排列,并且运行时复杂度为O(N!):
function permute(permutation) {
var length = permutation.length,
result = [permutation.slice()],
c = new Array(length).fill(0),
i = 1, k, p;
while (i < length) {
if (c[i] < i) {
k = i % 2 && c[i];
p = permutation[i];
permutation[i] = permutation[k];
permutation[k] = p;
++c[i];
i = 1;
result.push(permutation.slice());
} else {
c[i] = 0;
++i;
}
}
return result;
}
console.log(permute([1, 2, 3]));
实现为O(N)中具有空间复杂度的生成器的相同算法:
性能比较
随时将您的实现添加到以下Benchmark.js测试套件中:
Chrome 48的运行时结果:
- 99.152ms这个算法
- 153.115ms MarkusT
- 401.255ms js-combinatorics
- 497.037ms Urielzen
- 925.669ms Oriol
- 1026.571ms西关藤
- 2529.841ms分隔
- 3992.622ms猴子
- 4514.665ms Oriol
var inputArray = [1, 2, 3];
var result = inputArray.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item);
}, []);
alert(JSON.stringify(result));
现在可以调用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;
})();
}
该问题的大多数答案都使用昂贵的操作,例如连续插入和删除数组中的项,或者以迭代方式复制数组。
相反,这是典型的回溯解决方案:
function permute(arr) {
var results = [],
l = arr.length,
used = Array(l), // Array of bools. Keeps track of used items
data = Array(l); // Stores items of the current permutation
(function backtracking(pos) {
if(pos == l) return results.push(data.slice());
for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items
used[i] = true; // Mark item as used
data[pos] = arr[i]; // Assign item at the current position
backtracking(pos+1); // Recursive call
used[i] = false; // Mark item as not used
}
})(0);
return results;
}
permute([1,2,3,4]); // [ [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1] ]
由于结果数组很大,因此最好逐个迭代结果,而不是同时分配所有数据。在ES6中,可以使用生成器来完成:
function permute(arr) {
var l = arr.length,
used = Array(l),
data = Array(l);
return function* backtracking(pos) {
if(pos == l) yield data.slice();
else for(var i=0; i<l; ++i) if(!used[i]) {
used[i] = true;
data[pos] = arr[i];
yield* backtracking(pos+1);
used[i] = false;
}
}(0);
}
var p = permute([1,2,3,4]);
p.next(); // {value: [1,2,3,4], done: false}
p.next(); // {value: [1,2,4,3], done: false}
// ...
p.next(); // {value: [4,3,2,1], done: false}
p.next(); // {value: undefined, done: true}
以下函数对任何类型的数组进行排列,并在找到的每个排列上调用指定的回调函数:
/*
Permutate the elements in the specified array by swapping them
in-place and calling the specified callback function on the array
for each permutation.
Return the number of permutations.
If array is undefined, null or empty, return 0.
NOTE: when permutation succeeds, the array should be in the original state
on exit!
*/
function permutate(array, callback) {
// Do the actual permuation work on array[], starting at index
function p(array, index, callback) {
// Swap elements i1 and i2 in array a[]
function swap(a, i1, i2) {
var t = a[i1];
a[i1] = a[i2];
a[i2] = t;
}
if (index == array.length - 1) {
callback(array);
return 1;
} else {
var count = p(array, index + 1, callback);
for (var i = index + 1; i < array.length; i++) {
swap(array, i, index);
count += p(array, index + 1, callback);
swap(array, i, index);
}
return count;
}
}
if (!array || array.length == 0) {
return 0;
}
return p(array, 0, callback);
}
如果您这样称呼它:
// Empty array to hold results
var result = [];
// Permutate [1, 2, 3], pushing every permutation onto result[]
permutate([1, 2, 3], function (a) {
// Create a copy of a[] and add that to result[]
result.push(a.slice(0));
});
// Show result[]
document.write(result);
我认为它将完全满足您的需要-result
用数组[1、2、3]的排列填充一个称为数组的数组。结果是:
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
JSFiddle上的代码稍微清晰一些:http : //jsfiddle.net/MgmMg/6/
受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]);
});
}
document.write(JSON.stringify(perms([1,2,3])));
这是一项有趣的任务,这是我的贡献。非常简单,快速。如果有兴趣,请忍受并继续阅读。
如果您想快速完成这项工作,则绝对必须投入动态编程。这意味着您应该忘记递归方法。这是肯定的...
好的,使用堆方法的le_m代码似乎是迄今为止最快的。好吧,我还没有为我的算法起个名字,我不知道它是否已经实现,但是它非常简单,快速。与所有动态编程方法一样,我们将从最简单的问题开始,然后得出最终结果。
假设我们有一个数组,a = [1,2,3]
我们将从
r = [[1]]; // result
t = []; // interim result
然后执行以下三个步骤;
- 对于我们
r
(结果)数组的每一项,我们将添加输入数组的下一项。 - 我们将旋转每个项目的长度很多次,并将每个实例存储在临时结果数组中
t
。(除了第一个不会浪费时间0旋转的时间) - 一旦我们完成
r
了临时数组的所有项目,就t
应该保留下一级结果,因此我们继续r = t; t = [];
进行直到输入数组的长度为止a
。
因此,以下是我们的步骤;
r array | push next item to | get length many rotations
| each sub array | of each subarray
-----------------------------------------------------------
[[1]] | [[1,2]] | [[1,2],[2,1]]
----------|-------------------|----------------------------
[[1,2], | [[1,2,3], | [[1,2,3],[2,3,1],[3,1,2],
[2,1]] | [2,1,3]] | [2,1,3],[1,3,2],[3,2,1]]
----------|-------------------|----------------------------
previous t| |
-----------------------------------------------------------
所以这是代码
function perm(a){
var r = [[a[0]]],
t = [],
s = [];
if (a.length <= 1) return a;
for (var i = 1, la = a.length; i < la; i++){
for (var j = 0, lr = r.length; j < lr; j++){
r[j].push(a[i]);
t.push(r[j]);
for(var k = 1, lrj = r[j].length; k < lrj; k++){
for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj];
t[t.length] = s;
s = [];
}
}
r = t;
t = [];
}
return r;
}
var arr = [0,1,2,4,5];
console.log("The length of the permutation is:",perm(arr).length);
console.time("Permutation test");
for (var z = 0; z < 2000; z++) perm(arr);
console.timeEnd("Permutation test");
在多次测试中,我看到它可以在25〜35ms内解决[0,1,2,3,4]的120个排列2000次。
如今(2020)最快,最有效的解决方案
function getArrayMutations (arr, perms = [], len = arr.length) {
if (len === 1) perms.push(arr.slice(0))
for (let i = 0; i < len; i++) {
getArrayMutations(arr, perms, len - 1)
len % 2 // parity dependent adjacent elements swap
? [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]]
: [arr[i], arr[len - 1]] = [arr[len - 1], arr[i]]
}
return perms
}
const arrayToMutate = [1, 2, 3, 4, 5, 6, 7, 8, 9]
const startTime = performance.now()
const arrayOfMutations = getArrayMutations(arrayToMutate)
const stopTime = performance.now()
const duration = (stopTime - startTime) / 1000
console.log(`${arrayOfMutations.length.toLocaleString('en-US')} permutations found in ${duration.toLocaleString('en-US')}s`)
无需外部阵列或其他功能即可回答
function permutator (arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}
for (var i = 0; i < arr.length; i++) {
var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1)));
for (var j = 0; j < subPerms.length; j++) {
subPerms[j].unshift(arr[i]);
permutations.push(subPerms[j]);
}
}
return permutations;
}
这是一个很酷的解决方案
const rotations = ([l, ...ls], right=[]) =>
l ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []
const permutations = ([x, ...xs]) =>
x ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
console.log(permutations("cat"))
这是另一个“更递归”的解决方案。
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);
输出:
[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
function perm(xs) {
return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) {
for (var i = 0; i < xs.length; i++) {
acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i)));
}
return acc;
}, []);
}
用以下方法进行测试:
console.log(JSON.stringify(perm([1, 2, 3,4])));
其他大多数答案都没有利用新的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)}`);
#!/usr/bin/env node
"use strict";
function perm(arr) {
if(arr.length<2) return [arr];
var res = [];
arr.forEach(function(x, i) {
perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) {
res.push([x].concat(a));
});
});
return res;
}
console.log(perm([1,2,3,4]));
这是我做的...
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;
},[]);
}
它是如何工作的:如果数组长于一个元素,它将遍历每个元素,并以对其余元素作为参数的递归调用将其连接起来。它不会改变原始数组。
使用flatMap的功能性答案:
const getPermutationsFor = (arr, permutation = []) =>
arr.length === 0
? [permutation]
: arr.flatMap((item, i, arr) =>
getPermutationsFor(
arr.filter((_,j) => j !== i),
[...permutation, item]
)
);
我对该网站的第一项贡献。而且,根据我所做的测试,此代码在此日期之前的运行速度比此处提到的所有其他方法要快,当然,如果值很少,则运行时间最少,但是添加太多时,时间将成倍增加。
function permutations(arr) {
var finalArr = [];
function iterator(arrayTaken, tree) {
var temp;
for (var i = 0; i < tree; i++) {
temp = arrayTaken.slice();
temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]);
if (tree >= arr.length) {
finalArr.push(temp);
} else {
iterator(temp, tree + 1);
}
}
}
iterator(arr, 1);
return finalArr;
};
"use strict";
function getPermutations(arrP) {
var results = [];
var arr = arrP;
arr.unshift(null);
var length = arr.length;
while (arr[0] === null) {
results.push(arr.slice(1).join(''));
let less = null;
let lessIndex = null;
for (let i = length - 1; i > 0; i--) {
if(arr[i - 1] < arr[i]){
less = arr[i - 1];
lessIndex = i - 1;
break;
}
}
for (let i = length - 1; i > lessIndex; i--) {
if(arr[i] > less){
arr[lessIndex] = arr[i];
arr[i] = less;
break;
}
}
for(let i = lessIndex + 1; i<length; i++){
for(let j = i + 1; j < length; j++){
if(arr[i] > arr[j] ){
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
}
}
return results;
}
var res = getPermutations([1,2,3,4,5]);
var out = document.getElementById('myTxtArr');
res.forEach(function(i){ out.value+=i+', '});
textarea{
height:500px;
width:500px;
}
<textarea id='myTxtArr'></textarea>
输出按字典顺序排列的排列。仅适用于数字。在其他情况下,您必须在第34行上更改交换方法。
与@crl的Haskell样式的解决方案在精神上类似,但是可以使用reduce
:
function permutations( base ) {
if (base.length == 0) return [[]]
return permutations( base.slice(1) ).reduce( function(acc,perm) {
return acc.concat( base.map( function(e,pos) {
var new_perm = perm.slice()
new_perm.splice(pos,0,base[0])
return new_perm
}))
},[])
}
这是一个非常好的map / reduce用例:
function permutations(arr) {
return (arr.length === 1) ? arr :
arr.reduce((acc, cv, index) => {
let remaining = [...arr];
remaining.splice(index, 1);
return acc.concat(permutations(remaining).map(a => [].concat(cv,a)));
}, []);
}
- 首先,我们处理基本情况,如果其中仅包含项目,则仅返回数组
- 在所有其他情况下
- 我们创建一个空数组
- 遍历输入数组
- 并添加当前值的数组和其余数组的所有排列
[].concat(cv,a)
这是最低的ES6版本。可以从Lodash中拉平和不使用功能。
const flatten = xs =>
xs.reduce((cum, next) => [...cum, ...next], []);
const without = (xs, x) =>
xs.filter(y => y !== x);
const permutations = xs =>
flatten(xs.map(x =>
xs.length < 2
? [xs]
: permutations(without(xs, x)).map(perm => [x, ...perm])
));
结果:
permutations([1,2,3])
// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
perm = x => x[0] ? x.reduce((a, n) => (perm(x.filter(m => m!=n)).forEach(y => a.push([n,...y])), a), []): [[]]
const permutations = array => {
let permut = [];
helperFunction(0, array, permut);
return permut;
};
const helperFunction = (i, array, permut) => {
if (i === array.length - 1) {
permut.push(array.slice());
} else {
for (let j = i; j < array.length; j++) {
swapElements(i, j, array);
helperFunction(i + 1, array, permut);
swapElements(i, j, array);
}
}
};
function swapElements(a, b, array) {
let temp = array[a];
array[a] = array[b];
array[b] = temp;
}
console.log(permutations([1, 2, 3]));
很晚了。仍然以防万一,如果这可以帮助任何人。
function permute(arr) {
if (arr.length == 1) return arr
let res = arr.map((d, i) => permute([...arr.slice(0, i),...arr.slice(i + 1)])
.map(v => [d,v].join(''))).flat()
return res
}
console.log(permute([1,2,3,4]))
我在编写此版本的过程中遇到了麻烦,该版本试图简洁但易读,并且纯函数式编程。
function stringPermutations ([...input]) {
if (input.length === 1) return input;
return input
.map((thisChar, index) => {
const remainingChars = [...input.slice(0, index), ...input.slice(index + 1)];
return stringPermutations(remainingChars)
.map(remainder => thisChar + remainder);
})
.reduce((acc, cur) => [...acc, ...cur]);
}
请注意,参数格式会将输入字符串转换为数组。不知道这是否太神奇了..不知道我在野外看到过它。为了实现真正的可读性,我可能会改用input = [...input]
函数的第一行。
这是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/
我写了一篇文章来演示如何在JavaScript中置换数组。这是执行此操作的代码。
var count=0;
function permute(pre,cur){
var len=cur.length;
for(var i=0;i<len;i++){
var p=clone(pre);
var c=clone(cur);
p.push(cur[i]);
remove(c,cur[i]);
if(len>1){
permute(p,c);
}else{
print(p);
count++;
}
}
}
function print(arr){
var len=arr.length;
for(var i=0;i<len;i++){
document.write(arr[i]+" ");
}
document.write("<br />");
}
function remove(arr,item){
if(contains(arr,item)){
var len=arr.length;
for(var i = len-1; i >= 0; i--){ // STEP 1
if(arr[i] == item){ // STEP 2
arr.splice(i,1); // STEP 3
}
}
}
}
function contains(arr,value){
for(var i=0;i<arr.length;i++){
if(arr[i]==value){
return true;
}
}
return false;
}
function clone(arr){
var a=new Array();
var len=arr.length;
for(var i=0;i<len;i++){
a.push(arr[i]);
}
return a;
}
刚打电话
置换([],[1,2,3,4])
将工作。有关其工作原理的详细信息,请参阅该帖子中的说明。
function nPr(xs, r) {
if (!r) return [];
return xs.reduce(function(memo, cur, i) {
var others = xs.slice(0,i).concat(xs.slice(i+1)),
perms = nPr(others, r-1),
newElms = !perms.length ? [[cur]] :
perms.map(function(perm) { return [cur].concat(perm) });
return memo.concat(newElms);
}, []);
}
文章标签:javascript , permutation
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!
评论已关闭!