生成JavaScript数组的排列 [英] Generate permutations of JavaScript array

问题描述

我在javascript中有一个n个不同元素的数组，我知道有n个！订购这些元素的可能方式。我想知道什么是最有效（最快）的算法来生成这个数组的所有可能的排序？

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?

我有这段代码：

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

我希望输出为：

[[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

但维基百科从未擅长解释。我不太了解它，我不得不说我的数学水平不是最好的。

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.

推荐答案

这个函数， perm（xs），返回给定数组的所有排列：

This function, perm(xs), returns all the permutations of a given array:

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

这篇关于生成JavaScript数组的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！