0

您将如何以编程方式将一组数字的所有可能的唯一组合枚举到多个组中？

例如，如果我有集合 {1,2,3,4,5,6,7,8,9,10} 并且我想要 3 个大小为 3、3、2 的组，一个可能的子集是 { [1, 2, 3], [4, 5, 6], [7, 8] }

这将等同于 { [3, 2, 1], [6, 5, 4], [7, 8] } 并且将被视为重复

而 { [4, 2, 3], [1, 5, 6], [7, 8] } 将被视为不同的子集

显然，我正在寻找最有效和最实用的方法。我将使用相当大的 N，因此算法需要可扩展。

4

1 回答 1

1

考虑这个问题的另一种方法是 multiset 的排列 {1, 1, 1, 2, 2, 2, 3, 3}。如果这样的排列在位置p上具有价值，那将意味着原始集合中的元素应该放在 partition 中。ijji

使用例如 C++ 模板next_permutation，您可以枚举这些排列，如下所示：

int main() {
  int a[] = { 0, 0, 0, 1, 1, 1, 2, 2 };
  do {
    // Here a[j] == i means element j of your set goes in partition i.
    // Do whatever you want to do with the permutations generated this way.
  } while (std::next_permutation(a, a + 8));
}

结果将包含 10!/(3!3!2!) = 560 种不同的组合。此代码的演示运行，包括与您的问题陈述中使用的符号类似的输出，可在 ideone 获得。如果您想知道 gcc 是如何实现的，您可以查看源代码next_permutation，但只有在目标项目的许可证允许复制该代码时才这样做。

于 2013-07-15T06:33:04.777 回答