: All possible ways of splitting a set of elements into two sets? 的算法

Question

我在集合 U 中有 n 个元素(假设由大小为 n 的数组表示)。我想找到将集合 U 分成两组 A 和 B 的所有可能方法，其中 |A| + |乙| = n.

例如，如果 U = {a,b,c,d}，组合将是:

1. A = {a} -- B = {b,c,d}
2. A = {b} -- B = {a,c,d}
3. A = {c} -- B = {a,b,d}
4. A = {d} -- B = {a,b,c}
5. A = {a,b} -- B = {c,d}
6. A = {a,c} -- B = {b,d}
7. A = {a,d} -- B = {b,c}

请注意，以下两种情况被认为是相等的，只应计算一种情况:

情况 1:A = {a,b} -- B = {c,d}

情况 2:A = {c,d} -- B = {a,b}

另请注意，集合 A 或 B 都不能为空。

我正在考虑实现它的方式是只跟踪数组中的索引并逐步移动它们。索引数将等于集合 A 中的元素数，集合 B 将包含所有剩余的未索引元素。

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

谢谢!

Answer 1

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

这些数字中的每一个都以二进制表示，代表集合 A 中存在的元素。集合 B 由其余元素组成。请注意，因为我们只去 2^(n-1)，而不是 2^n，所以总是为集合 B 设置高位；我们总是将第一个元素放在集合 B 中，因为您希望顺序无关紧要。