生成 JavaScript 数组的排列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/37579994/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generate permutations of JavaScript array
提问by DSB
I have an array of n different elements in javascript, I know there are n! possible ways to order these elements. I want to know what's the most effective (fastest) algorithm to generate all possible orderings of this array?
我在javascript中有n个不同元素的数组，我知道有n个！对这些元素进行排序的可能方法。我想知道生成该数组所有可能排序的最有效（最快）算法是什么？
I have this code:
我有这个代码：
var swap = function(array, frstElm, scndElm) {
var temp = array[frstElm];
array[frstElm] = array[scndElm];
array[scndElm] = temp;
}
var permutation = function(array, leftIndex, size) {
var x;
if(leftIndex === size) {
temp = "";
for (var i = 0; i < array.length; i++) {
temp += array[i] + " ";
}
console.log("---------------> " + temp);
} else {
for(x = leftIndex; x < size; x++) {
swap(array, leftIndex, x);
permutation(array, leftIndex + 1, size);
swap(array, leftIndex, x);
}
}
}
arrCities = ["Sidney", "Melbourne", "Queenstown"];
permutation(arrCities, 0, arrCities.length);
And it works, but I guess swapping every item to get the combinations is a bit expensive memory wise, I thought a good way of doing it is just focusing on the indexes of the array and getting all the permutations of the numbers, I'm wondering if there's a way of computing all of them without having to switch elements within the array? I guess recursively is possible to get all of them, I need help to do so.
它有效，但我想交换每个项目以获得组合在内存方面有点昂贵，我认为这样做的一个好方法是只关注数组的索引并获取数字的所有排列，我是想知道是否有一种方法可以计算所有这些而无需切换数组中的元素？我想递归地获得所有这些是可能的，我需要帮助来做到这一点。
So for example if I have:
例如，如果我有：
arrCities = ["Sidney", "Melbourne", "Queenstown"];
I want the output to be:
我希望输出是：
[[012],[021],[102],[120],[201],[210]]
or:
或者：
[[0,1,2],
[0,2,1],
[1,0,2],
[1,2,0],
[2,0,1],
[2,1,0]]
I'm reading this: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
我正在阅读：http: //en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations
But Wikipedia has never been good at explaining. I don't understand much of it, I have to say my math level isn't the best.
但维基百科从来不擅长解释。我不太明白，我不得不说我的数学水平不是最好的。
回答by chacmoolvm
This function, perm(xs), returns all the permutations of a given array:
这个函数perm(xs)返回给定数组的所有排列：
function perm(xs) {
let ret = [];
for (let i = 0; i < xs.length; i = i + 1) {
let rest = perm(xs.slice(0, i).concat(xs.slice(i + 1)));
if(!rest.length) {
ret.push([xs[i]])
} else {
for(let j = 0; j < rest.length; j = j + 1) {
ret.push([xs[i]].concat(rest[j]))
}
}
}
return ret;
}
console.log(perm([1,2,3]).join("\n"));回答by le_m
Using Heap's method (you can find it in this paperwhich your Wikipedia article links to), you can generate all permutations of N elements with runtime complexity in O(N!) and space complexity in O(N). This algorithm is based on swapping elements. AFAIK this is as fast as it gets, there is no faster method to calculate all permutations.
使用 Heap 的方法（您可以在维基百科文章链接到的这篇论文中找到它），您可以生成 N 个元素的所有排列，运行时复杂度为 O(N!)，空间复杂度为 O(N)。该算法基于交换元素。AFAIK 这是尽可能快的，没有更快的方法来计算所有排列。
For an implementation and examples, please have a look at my recent answerat the related question "permutations in javascript".
有关实现和示例，请查看我最近在相关问题“javascript 中的排列”中的回答。
回答by Boris Yuzhakov
It is just for fun - my recursive solve in one string
这只是为了好玩 - 我在一个字符串中递归解决
const perm = a => a.length ? a.reduce((r, v, i) => [ ...r, ...perm([ ...a.slice(0, i), ...a.slice(i + 1) ]).map(x => [ v, ...x ])], []) : [[]]
回答by Erik Engi
This is my version based on le_m's code:
这是我基于le_m代码的版本：
function permute(array) {
Array.prototype.swap = function (index, otherIndex) {
var valueAtIndex = this[index]
this[index] = this[otherIndex]
this[otherIndex] = valueAtIndex
}
var result = [array.slice()]
, length = array.length
for (var i = 1, heap = new Array(length).fill(0)
; i < length
;)
if (heap[i] < i) {
array.swap(i, i % 2 && heap[i])
result.push(array.slice())
heap[i]++
i = 1
} else {
heap[i] = 0
i++
}
return result
}
console.log(permute([1, 2, 3]))This is my recursive JavaScript implementation of the same algorithm:
这是我对相同算法的递归 JavaScript 实现：
Array.prototype.swap = function (index, otherIndex) {
var valueAtIndex = this[index]
this[index] = this[otherIndex]
this[otherIndex] = valueAtIndex
}
Array.prototype.permutation = function permutation(array, n) {
array = array || this
n = n || array.length
var result = []
if (n == 1)
result = [array.slice()]
else {
const nextN = n - 1
for (var i = 0; i < nextN; i++) {
result.push(...permutation(array, nextN))
array.swap(Number(!(n % 2)) && i, nextN)
}
result.push(...permutation(array, nextN))
}
return result
}
console.log([1, 2, 3].permutation())