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

我在集合 U 中有 n 个元素(假设由大小为 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 将包含所有剩余的未索引元素。

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

谢谢!

最佳答案

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

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

关于: All possible ways of splitting a set of elements into two sets? 的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6999460/