algorithm - 有没有一种简单的方法可以找到一组子集的非重复组？

Question

假设我有一个集合:{1,2,...,N}，我想找到 K 个非空子集的非重复组，每个子集中具有特定数量的元素。

例如:集合:{1,2,3,4,5,6,7}子集数3，元素数3,3 ,1。这将生成如下组:{{1,2,3},{4,5,6},{7}} 或 {{5,7,2},{4,3,1},{6 }}等

在这种情况下，所有可能组的数量等于 C(7,3)*C(4,3)*C(1,1)*1/(2!) = 35* 4/2 = 70

如果我要生成第一个组合然后生成第二个组合，我会得到 140 个结果，因为这种方法不会考虑阶乘。

所以我的问题是:有没有一种简单的方法可以检查某个群组是否已经出现？我是否需要创建一个包含所有先前计算的组的数组，并每次检查是否已生成新的组？

Answer 1

生成所有组，但如果大小相同的子集出现在 lexicographical order 中，则只保留一个组.

例如，您将保留组 {{1,2,3},{4,5,6},{7}} 因为 {1,2,3} 按字典顺序在 {4,5,6} 之前。

但是，您会丢弃组 {{5,7,2},{4,3,1},{6}} 因为 {5,7,2} 应该跟在 {4,3,1} 之后。理论是，在某个时候，您将生成顺序正确的组 {{4,3,1},{5,7,2},{6}}，因此将保留。

---

下一级优化是不生成所有组，但只生成字典顺序正确的组。例如，如果第一个子集是 {5,7,2}，那么第二个子集的形式必须是 {6,x,y}，因为 6 是唯一一个未使用的大于 5 的数字。