算法：将一组元素分成两个集合的所有可能方式？

Question

我有一个包含n个元素的集合U（假设用大小为n的数组表示）。我想找到将集合U划分为两个集合A和B的所有可能方式，其中| A | + | B | = n。

例如，如果U={a,b,c,d}，则组合如下： - A={a}，B={b,c,d} - A={b}，B={a,c,d} - A={c}，B={a,b,d} - A={d}，B={a,b,c} - A={a，b}，B={c，d} - A={a，c}，B={b，d} - A={a，d}，B={b，c}

请注意，以下两种情况被视为相等，只计算一次即可： 1. A={a，b}，B={c，d} 2. A={c，d}，B={a，b}

还要注意，A或B集合都不能是空集。

我的思路是仅跟踪数组中的索引并逐步移动它们。索引的数量将等于集合A中的元素数量，而集合B将包含所有未编入索引的元素。

我想知道是否有更好的实现方式。因为这段代码将在相当大的数据集上执行，所以我正在寻求更高的效率。

谢谢！

- alguru

Answer 1

取出从1到2^(n-1)之间的所有整数，不包括2^(n-1)。因此，如果n=4，则为1到7的整数。

将这些数字写成二进制形式，表示集合A中存在的元素。集合B由其余元素组成。请注意，由于我们只考虑到2^(n-1)，而不是2^n，因此对于集合B始终设置高位；我们总是将第一个元素放入集合B，因为您希望顺序无关紧要。

- dfan

---

谢谢您的快速回复！我喜欢这种方法，并在几个案例中尝试了一下，似乎效果不错！我想知道您是否有任何想法，可以告诉我在哪里找到一个（或多或少）正式的证明，以说明为什么这个方法有效。 - alguru

每个项目 x 要么在集合 A 中，要么不在，这对应于位号 x 是 1 还是 0。通过这种方式，你的 N 个值的所有可能的 2^N 子集都可以用一个 N 位二进制数表示，我们只需遍历所有 N 位二进制数即可。 - dfan

"proof by inspection"... - Sanjay Manohar