JavaScript中集合的所有可能的唯一组合

Question

我正在构建一个应用程序来测试不同的图标。管理员上传一些图标，并输入必须同时显示多少图标。然后，应用程序按顺序显示所有可能的图标集，直到所有的图标组合都显示出来。

现在，我需要一个函数来根据两个数字生成所有唯一的图标组合：

• 图标总数(i)
• 每组图标的数量。

如果i=6和s= 3，则希望输出如下所示：

[
  [1, 2, 3],
  [1, 2, 4],
  [1, 2, 5],
  [1, 2, 6],
  [1, 3, 4],
  [1, 3, 5],
  [1, 3, 6],
  [1, 4, 5],
  [1, 4, 6],
  [1, 5, 6],
  [2, 3, 4],
  [2, 3, 5],
  [2, 3, 6],
  [2, 4, 5],
  [2, 4, 6],
  [2, 5, 6],
  [3, 4, 5],
  [3, 4, 6],
  [3, 5, 6],
  [4, 5, 6],    
]

要求：

• 所有的集合都必须是唯一的
• 一个数字只能在一个集合中出现一次。

我一直试图编写一个递归函数，但是我没有任何东西可以显示。我不能把头绕过去：

Answer 1

基于这个问题的答案：Computing all n-sized permutations without repetitions and without "classic" ordering

然后使用类似于C++ std::next_permutation的算法，其工作方式如下：

• 从左边走，找到最右边的一个以零为单位。把一个放进去
• 0的位置并对数组的其余部分进行排序。

免责声明:我的javascript非常、非常生疏，所以我确信有一种更优雅的实现方法。

function combine(n, k) {
  var result = [];

  // initialize array of values
  var values = [];
  for (var i = 1; i <= n; i++) {
    values[i - 1] = i;
  }

  // initialize permutations
  var perm = [];
  for (var i = 0; i < n; i++) {
    if (i < k) {
      perm[i] = 1;
    } else {
      perm[i] = 0;
    }
  }
  perm.sort();

  whileloop:
    while (true) {
      // save subresult
      var subresult = [];
      for (var i = 0; i < n; i++) {
        if (perm[i] == 1) {
          subresult.push(values[i]);
        }
      }
      result.push(subresult);

      // get next permutation
      for (var i = n - 1; i > 0; i--) {
        if (perm[i - 1] == 1) {
          continue;
        }
        if (perm[i] == 1) {
          perm[i - 1] = 1;
          perm[i] = 0;
          perm = perm.slice(0, i).concat(perm.slice(i).sort())
          continue whileloop;
        }
      }

      // no additional permutations exist
      break whileloop;
    }

  return result;
}

Answer 2

将n元素组合成多个集合和k元素，每个元素不重复，如何做到。算法相对简单，主要思想是:首先输入一组k元素，然后尝试从集合的末尾增量每个元素，以填充另一个k集等等。当我们不能这样做的时候，我们就离开这个过程(所有可能的集合都准备好了)。

function combine(n,k) {
  var result = Array();
  var a = Array();

  // make initial (first) k-set
  for (var i=1; i<=k; i++) {
    a[i-1] = i;
  }

  j = k-1;
  while (j >= 1) {

    // submit current results
    result.push(a.slice());

    if (a[k-1] == n) {
      j = j - 1;
    } else {
      j = k-1;
    }

    if (j >= 1) {
      // make next k-set based on previous one
      for (var i=k; i>=j; i--) {
        a[i-1] = a[j-1] + i - j + 1;
      }
    }
  }

  return result;
}

注意: JavaScript数组有启动索引0，所以在代码中，我们对数组索引进行了-1校正(导致从1到n的可能值集)。