用Javascript创建一个由唯一值组成的数组的组合。

Question

尽管阅读了很多关于排列/组合的问答：查找JavaScript数组值的所有组合 + JavaScript - 从n个具有m个元素的数组生成组合，但我还没有找到我正在寻找的结果的正确方法。 我有一个包含10个值的数组：

var arr = [0,1,2,3,4,5,6,7,8,9];

如果我没错的话，所有可能的排列数组的数量是唯一值（无重复项）：

[5,9,1,8,2,6,7,0,4,3] [4,8,0,2,1,9,7,3,6,5] ...

2x3x4x5x6x7x8x9x10 = 3628800

我正在尝试创建一个动态生成'n'数组的函数。例如：

function createArray(0) -> [0,1,2,3,4,5,6,7,8,9]
function createArray(45648) -> [0,1,5,3,2,8,7,9,6] (something like...)
function createArray(3628800) -> [9,8,7,6,5,4,3,2,1,0]

我想实现的方法是：

• 使用createArray(1)将最后2个符号进行排列（8,9 -> 9,8）

• 使用createArray(2->6)将最后3个符号进行排列（8,7,9 -> 9,8,7）

• 使用createArray(3628800)：所有值均被排列（从9到0）

你认为这个任务是否可行/容易，如果是，如何继续？

[编辑]

感谢有用的回答。

function permute(permutation, val) {

  var length = permutation.length,
  result = [permutation.slice()],
  c = new Array(length).fill(0),
  i = 1, k, p,
  n = 0;
  while (i < length) {
  if (c[i] < i) {
  if (n <= val) {   
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      if (n == val) {   
          arr = permutation.slice();
          console.log("n="+n+"\n"+arr);
          console.log( 'Duration: '+((new Date() - t1)/1000)+'s' );
          break;
      }
      else {  n+=1; }  
     }
   } else {
     c[i] = 0;
     ++i;
   }
  }
}

let t1 = new Date();
permute([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100000); // <- array requested

控制台: n=100000 + 0.5,8,1,7,2,3,6,4,9 + 耗时: 0.004秒

- Wolden

---

你会考虑使用像 generatorics 这样的 Node 模块吗？ - Wong Jia Hau

嗯，听起来像是计算机科学的练习题，也许你可以展示一下你目前的代码。 - vdj4y

@WongJiaHau 谢谢提供链接。如果可能的话，纯JS Vanilla将是首选。 - Wolden

请查看 https://dev59.com/oGkw5IYBdhLWcg3wV5ID#37580979。您可以将数组分成不同的大小 [1]，[2]，[3]，[..] / [1,2]，[2,3]，[3,4] .... 然后使用该函数处理每个数组。 - Raj Nandan Sharma

@CertainPerformance，我尝试了上面链接页面中的不同函数，但有些会在同一数组中创建重复值，有些（多维数组）则无法循环所有值，还有一些可以创建正确的数组，但我找不到编程方式来生成我需要的唯一数组... - Wolden

Answer 1

由于这个问题并没有描述一个具体的编程问题，而是一项相当复杂的任务，因此您不应该期望得到一个完整的解决方案作为答案，但我将尝试描述可能的解决方法：

正如你所说，排列的数量为2x3x4x...

您可以检查 n > 2，如果是真的，则检查 n > 2x3，如果是真的，则检查 n > 2x3x4。那样，您将知道要对多少尾随数组索引进行排列。然后，您必须确保以排序的线性方式计算排列，以不生成相同的排列两次。这是一个数学问题，编码本身应该相当容易（类似于在更改索引时切换位置n次）。

不确定这是否是您要寻找的答案，但制作独特的排列算法似乎相当复杂（例如，参见另一个问题的此答案 https://dev59.com/ymXWa4cB1Zd3GeqPR_fD#11425168），其中链接到这篇维基百科文章 https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order 以按字典顺序生成。

编辑：根据 Raj Sharma 在您的问题上的评论，这个生成排列的答案也很有价值： https://dev59.com/oGkw5IYBdhLWcg3wV5ID#37580979

- Ahorn