生成JavaScript数组的排列

Question

我有一个包含n个不同元素的 JavaScript 数组，我知道这些元素可以有 n! 种可能的排序方式。我想知道生成这个数组所有可能排列的最有效（最快）的算法是什么？

我有以下代码：

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

它起作用，但我猜交换每个项目以获得组合在内存方面有点昂贵，我认为一个好的方法是只关注数组的索引并获取数字的所有排列，我想知道是否有一种方式可以计算所有这些而不必在数组中切换元素？我猜递归可能可以获取它们所有，我需要帮助完成。

例如，如果我有：

arrCities = ["Sidney", "Melbourne", "Queenstown"];

我希望你能翻译成以下输出：

[[012],[021],[102],[120],[201],[210]]

或者：

[[0,1,2],
 [0,2,1],
 [1,0,2],
 [1,2,0],
 [2,0,1],
 [2,1,0]]

我正在阅读这个页面： http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

但是维基百科从来没有很好地解释过。我不太理解其中的大部分内容，我必须承认我的数学水平不是很好。

- DSB

---

请解释一下您所说的“最有效”的含义。是指速度最快？还是内存使用最低？ - Russbear

除非您确保数组中的 n 个元素彼此不同（或者更好地说，可辨别），否则并不存在 n! 种排列方式。如果两个元素无法区分，则已经少于 n! 种排列方式（实际上，这将导致有重复的排列）。 - pid

@EvanTrimboli，那个方法必须在数组内切换元素以实现所有排列，这个速度（和内存）方面可能过于昂贵，我不擅长数学，但我的逻辑告诉我应该有一种方法来计算范围内的所有可能数字，这样做比实际重新定位每个元素要快得多。 - DSB

当然，你可以很容易地找出有多少个，那只是一个公式。但你仍然需要生成输出。这仍然是同样的问题。无论是字符串还是数字，它们仍然是你想要为其生成排列的唯一可识别的事物。 - Evan Trimboli

将其关闭为最初建议的目标的重复项。这里没有任何答案实际上解决了这个问题的要求：您的输入是一个数组，您的输出是所有排列的所有索引的数组，但所有答案都回答了另一个问题。输出 [ [ 012 ], [ 021 ]，…] 不太可能有用，因为这样的文字已被弃用。幸运的是，使用提供的排列函数和 array.map((_, index) => index) 作为输入而不是 array 可以涵盖所有用例。 - Sebastian Simon

Answer 1

这个函数 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"));

- chacmoolvm

Answer 2

使用Heap算法（您可以在这篇文章中找到，这篇文章是您的维基百科文章链接的），您可以生成N个元素的所有排列，其运行时间复杂度为O(N!)，空间复杂度为O(N)。该算法基于交换元素实现。据我所知，这是最快的计算所有排列的方法，没有更快的方法。

有关实现和示例，请查看我在相关问题“javascript中的排列”的最新答案。

- le_m

---

有没有一些方法可以不计算所有可能的排列，而是做一个相当接近的计算呢？ - DSB

@DSB 我不认为我理解了。如果您不想生成所有排列，而只是想要一些，请查看Lehmer code，它允许您快速计算给定词典序排列索引的单个排列。 - le_m

使用此答案(https://dev59.com/oGkw5IYBdhLWcg3wV5ID#37580979) 进行的基本测试比上面@chacmoolvm的回答快了10倍。 - Paul Grimshaw

Answer 3

这只是一种娱乐方式——我用一行代码实现了递归求解

const perm = a => a.length ? a.reduce((r, v, i) => [ ...r, ...perm([ ...a.slice(0, i), ...a.slice(i + 1) ]).map(x => [ v, ...x ])], []) : [[]]

- Boris Yuzhakov

---

计算11个元素的排列需要很长时间。 - 18augst

好的，我现在就说吧，我喜欢一行代码。非常感谢你！ - J-Cake

酷，但也很难读懂。 - Life after Guest

Answer 4

这是基于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]))

这是我对同样算法的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())

- Erik Engi

Answer 5

function permutations(str) {
 return (str.length <= 1) ? [str] :
         Array.from(new Set(
           str.split('')
              .map((char, i) => permutations(str.substr(0, i) + str.substr(i + 1)).map(p => char + p))
              .reduce((r, x) => r.concat(x), [])
         ));
}

- ngassaki cardorel