集合中所有可能的独特组合

debugcn 发表于 Dev

托尔伯格

我正在构建一个应用程序来测试不同的图标。管理员上传了许多图标，并输入了必须同时显示多少个图标。然后，该应用会依次显示所有可能的图标集，直到显示了所有图标组合为止。

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

总图标数（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],    
]

要求：

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

我一直在尝试编写一个递归函数，但是我还没有真正要显示的东西。我无法绕开它:(

卡斯珀·米德尔波·彼得森（Kasper Middelboe Petersen）

基于给出该问题的答案的思想：计算所有n大小的排列，而无需重复且没有“经典”排序

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

从左侧开始，找到最右边的一个零开头的数字。放一个

零的位置并对数组的其余部分进行排序。

免责声明：我的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;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。