算法用于:将一组元素分成两组的所有可能方法? [英] Algorithm for: All possible ways of splitting a set of elements into two sets?

问题描述

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

I have n elements in a set U (lets assume represented by an array of size n). I want to find all possible ways of dividing the set U into two sets A and B, where |A| + |B| = n.

例如，如果U = {a，b，c，d}，则组合为:

So for example, if U = {a,b,c,d}, the combinations would be:

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}

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

Note that the following two cases are considered equal and only one should be computed:

案例1:A = {a，b}-B = {c，d}

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

案例2:A = {c，d}-B = {a，b}

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

还请注意，集合A或B都不能为空.

Also note that none of the sets A or B can be empty.

我想实现它的方式是通过跟踪数组中的索引并逐步移动它们.索引的数量将等于集合A中元素的数量，而集合B将包含所有剩余的未索引元素.

The way I'm thinking of implementing it is by just keeping track of indices in the array and moving them step by step. The number of indices will be equal to the number of elements in the set A, and set B will contain all the remaining un-indexed elements.

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

I was wondering if anyone knew of a better implementation. Im looking for better efficiency because this code will be executed on a fairly large set of data.

谢谢！

推荐答案

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

Take all the integers from 1 to 2^(n-1), non-inclusive. So if n = 4, the integers from 1 to 7.

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

Each of these numbers, written in binary, represents the elements present in set A. Set B consists of the remaining elements. Note that since we're only going to 2^(n-1), not 2^n, the high bit is always set for set B; we're always putting the first element in set B, since you want order not to matter.

这篇关于算法用于:将一组元素分成两组的所有可能方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！