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

Question

我在集合 U 中有 n 个元素（假设由大小为 n 的数组表示）。我想找到将集合 U 分为两个集合 A 和 B 的所有可能方法，其中 |A| + |B| = 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) 之间的所有整数，不包含 1 和 2^(n-1)。因此，如果 n = 4，则为 1 到 7 之间的整数。

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

Answer 2

如果它有助于阐明 dfan 的方法在做什么，这里是 1-7 的整数、整数的位串以及用于拆分的相应组 my_list=['a', 'b', 'c', ' d']。位串中的 3 个字符对应于 my_list 的索引 1、2 和 3。如果该位为 1，则该元素将进入第一个列表。索引 0 ('a') 处的元素始终位于第二组中。

1 001 ['d'] ['a', 'b', 'c']
2 010 ['c'] ['a', 'b', 'd']
3 011 ['c', 'd'] ['a', 'b']
4 100 ['b'] ['a', 'c', 'd']
5 101 ['b', 'd'] ['a', 'c']
6 110 ['b', 'c'] ['a', 'd']
7 111 ['b', 'c', 'd'] ['a']