JavaScript中的排列?

我试图写一个函数，它做以下工作:

  • 以一个整数数组作为参数(例如[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中做到这一点

210637 次浏览
小开
最佳答案

如果您注意到，代码实际上在进行任何排列之前将字符拆分为一个数组，因此只需删除连接和拆分操作

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])));

小开

我已经改进了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;
})();
}


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;
})();
}
document.write(JSON.stringify(permute([5, 3, 7, 1])));

小开

下面的函数排列任意类型的数组，并对发现的每个排列调用指定的回调函数:

/*
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);

我认为它将完全满足你的需要-用数组[1,2,3]的排列填充一个名为result的数组。结果是:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]

JSFiddle: http://jsfiddle.net/MgmMg/6/上的代码稍微清晰一些

小开

有点晚了，但喜欢在这里添加一个稍微优雅的版本。可以是任何数组…

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 ] ]
小开 
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));
小开

我对网站的第一个贡献。此外，根据我所做的测试，这段代码比在此之前提到的所有其他方法运行得更快，当然，如果值很少，它是最小的，但是当添加太多时，时间会呈指数增长。

var result = permutations([1,2,3,4]);


var output = window.document.getElementById('output');
output.innerHTML = JSON.stringify(result);


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;
};
<div id="output"></div>

小开

无需外部数组或附加函数即可回答

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;
}
小开

这是另一个“more recursive”。解决方案。

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>

Output:

[ 'ABC', 'BAC', 'BCA', 'ACB', 'CAB', 'CBA' ]
小开

我写了一个帖子来演示如何在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])

将工作。关于这是如何工作的详细信息，请参考那篇文章中的解释。

小开

一些受到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])));

小开

对这个问题的大多数回答都使用昂贵的操作，如连续插入和删除数组中的项，或重复复制数组。

相反，这是典型的回溯解决方案:

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}
小开 
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);
}, []);
}
小开

. 
"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>

Outputs lexicographically ordered permutations. Works only with numbers. In other case, you have to change the swap method on line 34.

小开 
   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])));
小开

以下非常高效的算法使用堆的方法生成运行时复杂度为O(N!)的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)的发电机实现的算法相同:

function* permute(permutation) {
var length = permutation.length,
c = Array(length).fill(0),
i = 1, k, p;


yield permutation.slice();
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;
yield permutation.slice();
} else {
c[i] = 0;
++i;
}
}
}


// Memory efficient iteration through permutations:
for (var permutation of permute([1, 2, 3])) console.log(permutation);


// Simple array conversion:
var permutations = [...permute([1, 2, 3])];

性能比较

请随意将您的实现添加到以下benchmark.js测试套件:

function permute_SiGanteng(input) {
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
}
return permute(input);
}


function permute_delimited(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);
}


function permute_monkey(inputArray) {
return 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);
}, []);
}


function permute_Oriol(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_MarkusT(input) {
function permutate(array, callback) {
function p(array, index, callback) {
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);
}
var result = [];
permutate(input, function(a) {
result.push(a.slice(0));
});
return result;
}


function permute_le_m(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;
}


function permute_Urielzen(arr) {
var finalArr = [];
var iterator = function (arrayTaken, tree) {
for (var i = 0; i < tree; i++) {
var 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;
}


function permute_Taylor_Hakes(arr) {
var permutations = [];
if (arr.length === 1) {
return [ arr ];
}


for (var i = 0; i <  arr.length; i++) {
var subPerms = permute_Taylor_Hakes(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;
}


var Combinatorics = (function () {
'use strict';
var version = "0.5.2";
/* combinatory arithmetics */
var P = function(m, n) {
var p = 1;
while (n--) p *= m--;
return p;
};
var C = function(m, n) {
if (n > m) {
return 0;
}
return P(m, n) / P(n, n);
};
var factorial = function(n) {
return P(n, n);
};
var factoradic = function(n, d) {
var f = 1;
if (!d) {
for (d = 1; f < n; f *= ++d);
if (f > n) f /= d--;
} else {
f = factorial(d);
}
var result = [0];
for (; d; f /= d--) {
result[d] = Math.floor(n / f);
n %= f;
}
return result;
};
/* common methods */
var addProperties = function(dst, src) {
Object.keys(src).forEach(function(p) {
Object.defineProperty(dst, p, {
value: src[p],
configurable: p == 'next'
});
});
};
var hideProperty = function(o, p) {
Object.defineProperty(o, p, {
writable: true
});
};
var toArray = function(f) {
var e, result = [];
this.init();
while (e = this.next()) result.push(f ? f(e) : e);
this.init();
return result;
};
var common = {
toArray: toArray,
map: toArray,
forEach: function(f) {
var e;
this.init();
while (e = this.next()) f(e);
this.init();
},
filter: function(f) {
var e, result = [];
this.init();
while (e = this.next()) if (f(e)) result.push(e);
this.init();
return result;
},
lazyMap: function(f) {
this._lazyMap = f;
return this;
},
lazyFilter: function(f) {
Object.defineProperty(this, 'next', {
writable: true
});
if (typeof f !== 'function') {
this.next = this._next;
} else {
if (typeof (this._next) !== 'function') {
this._next = this.next;
}
var _next = this._next.bind(this);
this.next = (function() {
var e;
while (e = _next()) {
if (f(e))
return e;
}
return e;
}).bind(this);
}
Object.defineProperty(this, 'next', {
writable: false
});
return this;
}


};
/* power set */
var power = function(ary, fun) {
var size = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
that.index = 0;
},
nth: function(n) {
if (n >= size) return;
var i = 0,
result = [];
for (; n; n >>>= 1, i++) if (n & 1) result.push(this[i]);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
},
next: function() {
return this.nth(this.index++);
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* combination */
var nextIndex = function(n) {
var smallest = n & -n,
ripple = n + smallest,
new_smallest = ripple & -ripple,
ones = ((new_smallest / smallest) >> 1) - 1;
return ripple | ones;
};
var combination = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var first = (1 << nelem) - 1,
size = C(ary.length, nelem),
maxIndex = 1 << ary.length,
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'index');
addProperties(that, {
valueOf: sizeOf,
init: function() {
this.index = first;
},
next: function() {
if (this.index >= maxIndex) return;
var i = 0,
n = this.index,
result = [];
for (; n; n >>>= 1, i++) {
if (n & 1) result[result.length] = this[i];
}


this.index = nextIndex(this.index);
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};
/* permutation */
var _permutation = function(ary) {
var that = ary.slice(),
size = factorial(that.length);
that.index = 0;
that.next = function() {
if (this.index >= size) return;
var copy = this.slice(),
digits = factoradic(this.index, this.length),
result = [],
i = this.length - 1;
for (; i >= 0; --i) result.push(copy.splice(digits[i], 1)[0]);
this.index++;
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
};
return that;
};
// which is really a permutation of combination
var permutation = function(ary, nelem, fun) {
if (!nelem) nelem = ary.length;
if (nelem < 1) throw new RangeError;
if (nelem > ary.length) throw new RangeError;
var size = P(ary.length, nelem),
sizeOf = function() {
return size;
},
that = Object.create(ary.slice(), {
length: {
get: sizeOf
}
});
hideProperty(that, 'cmb');
hideProperty(that, 'per');
addProperties(that, {
valueOf: function() {
return size;
},
init: function() {
this.cmb = combination(ary, nelem);
this.per = _permutation(this.cmb.next());
},
next: function() {
var result = this.per.next();
if (!result) {
var cmb = this.cmb.next();
if (!cmb) return;
this.per = _permutation(cmb);
return this.next();
}
return (typeof (that._lazyMap) === 'function')?that._lazyMap(result):result;
}
});
addProperties(that, common);
that.init();
return (typeof (fun) === 'function') ? that.map(fun) : that;
};


/* export */
var Combinatorics = Object.create(null);
addProperties(Combinatorics, {
C: C,
P: P,
factorial: factorial,
factoradic: factoradic,
permutation: permutation,
});
return Combinatorics;
})();


function permute_Technicalbloke(inputArray) {
if (inputArray.length === 1) return inputArray;
return inputArray.reduce( function(accumulator,_,index){
permute_Technicalbloke([...inputArray.slice(0,index),...inputArray.slice(index+1)])
.map(value=>accumulator.push([inputArray[index],value]));
return accumulator;
},[]);
}


var suite = new Benchmark.Suite;
var input = [0, 1, 2, 3, 4];


suite.add('permute_SiGanteng', function() {
permute_SiGanteng(input);
})
.add('permute_delimited', function() {
permute_delimited(input);
})
.add('permute_monkey', function() {
permute_monkey(input);
})
.add('permute_Oriol', function() {
permute_Oriol(input);
})
.add('permute_MarkusT', function() {
permute_MarkusT(input);
})
.add('permute_le_m', function() {
permute_le_m(input);
})
.add('permute_Urielzen', function() {
permute_Urielzen(input);
})
.add('permute_Taylor_Hakes', function() {
permute_Taylor_Hakes(input);
})
.add('permute_Combinatorics', function() {
Combinatorics.permutation(input).toArray();
})
.add('permute_Technicalbloke', function() {
permute_Technicalbloke(input);
})
.on('cycle', function(event) {
console.log(String(event.target));
})
.on('complete', function() {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.run({async: true});
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/platform/1.3.4/platform.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>

Chrome 48的运行时结果:

小开 
function swap(array1, index1, index2) {
var temp;
temp = array1[index1];
array1[index1] = array1[index2];
array1[index2] = temp;
}


function permute(a, l, r) {
var i;
if (l == r) {
console.log(a.join(''));
} else {
for (i = l; i <= r; i++) {
swap(a, l, i);
permute(a, l + 1, r);
swap(a, l, i);
}
}
}




permute(["A","B","C", "D"],0,3);

//样本执行 //更多的细节请参考这个链接

/ / http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

小开

在精神上类似于@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
}))
},[])
}
小开

这是一个有趣的任务这是我的贡献。它非常简单和快速。如果有兴趣，请耐心阅读。

如果你想快速完成这项工作，你肯定得让自己进入动态编程。这意味着您应该忘记递归方法。那是肯定的……

好的le_m的代码，它使用堆的方法似乎是目前为止最快的。我的算法还没有名字，我不知道它是否已经实现了，但它非常简单和快速。与所有动态规划方法一样，我们将从最简单的问题开始，然后走向最终的结果。

假设我们有一个数组a = [1,2,3]作为开始

r = [[1]]; // result
t = [];    // interim result

然后遵循以下三个步骤;

  1. 对于r (result)数组的每一项，我们将添加输入数组的下一项。
  2. 我们将旋转每个项的长度多次，并将每个实例存储在中间结果数组t中。(好吧，除了第一个不浪费时间的0旋转)
  3. 一旦我们处理完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次。

小开

这是一个非常好的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)的所有排列
      • 李< / ul > < / >
小开

这是一个很短的解决方案，只适用于1或2个长字符串。它是一个联机程序，使用ES6而不依赖jQuery，速度非常快。享受:

var p = l => l.length<2 ? [l] : l.length==2 ? [l[0]+l[1],l[1]+l[0]] : Function('throw Error("unimplemented")')();
小开

大多数其他答案没有利用新的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)}`);

小开 
  let permutations = []


permutate([], {
color: ['red', 'green'],
size: ['big', 'small', 'medium'],
type: ['saison', 'oldtimer']
})


function permutate (currentVals, remainingAttrs) {
remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => {
let currentValsNew = currentVals.slice(0)
currentValsNew.push(attrVal)


if (Object.keys(remainingAttrs).length > 1) {
let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs))
delete remainingAttrsNew[Object.keys(remainingAttrs)[0]]


permutate(currentValsNew, remainingAttrsNew)
} else {
permutations.push(currentValsNew)
}
})
}

结果:

[
[ 'red', 'big', 'saison' ],
[ 'red', 'big', 'oldtimer' ],
[ 'red', 'small', 'saison' ],
[ 'red', 'small', 'oldtimer' ],
[ 'red', 'medium', 'saison' ],
[ 'red', 'medium', 'oldtimer' ],
[ 'green', 'big', 'saison' ],
[ 'green', 'big', 'oldtimer' ],
[ 'green', 'small', 'saison' ],
[ 'green', 'small', 'oldtimer' ],
[ 'green', 'medium', 'saison' ],
[ 'green', 'medium', 'oldtimer' ]
]
小开 
#!/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 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"]
小开

这是一个最小的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]代替函数的第一行。

小开

这里有一个很酷的解决方案

const rotations = ([l, ...ls], right=[]) =>
l !== void 0 ? [[l, ...ls, ...right], ...rotations(ls, [...right, l])] : []


const permutations = ([x, ...xs]) =>
x !== void 0 ? permutations(xs).flatMap((p) => rotations([x, ...p])) : [[]]
  

console.log(permutations("cat"))

小开

这是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/

小开

这是我做的一个…

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]
)
);
小开

我使用了一个字符串而不是一个数组，似乎我的算法消耗的时间更少。我把我的算法贴在这里，我测量的时间正确吗?

console.time('process');


var result = []


function swapper(toSwap){
let start = toSwap[0]
let end = toSwap.slice(1)
return end + start
}




function perm(str){
let i = str.length
let filling = i - 1


let buckets = i*filling
let tmpSwap = ''
for(let j=0; j<filling; j++){
if(j===0){
result.push(str)
}else{
if(j === 1){
tmpSwap = swapper(str.slice(1))
result.push(str[0]+ tmpSwap)
if(j === filling-1 && result.length < buckets){
perm(swapper(str))
}


}else{
tmpSwap = swapper(tmpSwap)
result.push(str[0]+ tmpSwap)
if(j === filling-1 && result.length < buckets){
perm(swapper(str))
}
}
}
}


if(result.length = buckets){
return result
}else{
return 'something went wrong'
}


}










console.log(perm('abcdefghijk'))


console.timeEnd('process');
小开

目前最快、最有效、最优雅的版本(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`)

小开

这是一个非常简洁的递归解决方案，允许您输入输出排列的大小，类似于统计运算符nPr。“排列”。这允许您获得特定大小的所有可能的排列。

function generatePermutations(list, size=list.length) {
if (size > list.length) return [];
else if (size == 1) return list.map(d=>[d]);
return list.flatMap(d => generatePermutations(list.filter(a => a !== d), size - 1).map(item => [d, ...item]));
}

generatePermutations([1,2,3])

[[1, 2, 3],[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

generatePermutations([1,2,3],2)

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
小开

这是delimited的更简洁的版本

function permutator (inputArr) {
const result = []


function permute (arr, m = []) {
if (arr.length) {
arr.forEach((item, i) => {
const restArr = [...arr.slice(0, i), ...arr.slice(i + 1)]
permute(restArr, [...m, item])
})
} else {
result.push(m)
}
}


permute(inputArr)


return result
}
小开

我认为下面的解决方案的唯一不同之处在于，我在出现空情况前一步停止了递归。希望嵌入的评论是充分的解释。

function Permutations (A) // computes all possible ordered sequences of the entries in array A and returns them as an array of arrays
{
var perms = [];


for (var i = 0 ; i < A.length ; i++)
{
var rem = A.slice (0); // copy input array to retain remainder of elements after removing i'th element
var el = rem.splice (i,1);
if (A.length == 2) {perms.push ([el [0],rem [0]])} // recursion end case
else
{
var sub = Permutations (rem); // recursive call
for (var s = 0 ; s < sub.length ; s++) // process recursive response, adding el to the start of each returned sequence
{
sub [s].splice (0,0,el [0]);
perms.push (sub [s]);
};
};
};


return perms ;


};// end of Permutations function
小开

我想你可能会喜欢这个:

const permute1 = (arr: any[]): any[][] =>
arr.reduce(
(acc, curr) =>
acc.length > 0
? acc
.map((p) =>
Array.from({ length: p.length + 1 }, (_, i) =>
p.slice(0, i).concat(curr, p.slice(i))
)
)
.flat()
: [[curr]],
[]
);
小开

为了解决这个问题，我的想法如下…

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']

所以…排列行为是有规律的。

和数组实例的总排列是…所有可能的子排列从原始数组中移除每个单个字符，并将该单个字符与它们相对的子排列连接起来。也许代码能更好地解释这一点。

再见!

 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);

小开

下面是递归函数=>https://recursion.vercel.app/

 var permute = function (nums) {
let answer = [];


var permuter = function (arr, permutation = []) {
if (arr.length === 0) {
return answer.push(permutation);
} else {
for (let i = 0; i < arr.length; i++) {
let currentArr = arr.slice();
let next = currentArr.splice(i, 1);
permuter(currentArr, permutation.concat(next)); ///we use concat because splice returns an array.
}
}
};


permuter(nums);


return answer;
};

提交答案