查找集合的所有子集

Question

我需要一种算法来查找集合中所有元素的集合的子集n。S={1,2,3,4...n}编辑：我目前无法理解所提供的答案。我想逐步说明答案如何找到子集。例如，S={1,2,3,4,5}你怎么知道{1}和{1,2}是子集？有人可以帮我用C ++中的一个简单函数来查找{1,2,3,4,5}的子集

Answer 1

递归执行此操作非常简单。基本思想是，对于每个元素，可以将子集划分为包含该元素的子集和不包含子元素的子集，否则这两组子集是相等的。

• 对于n = 1，子集为{{}，{1}}

• 对于n> 1，找到1，...，n-1的子集，并制作两个副本。对于其中之一，将n添加到每个子集。然后将两个副本合并。

编辑使其清晰可见：

• {1}的子集为{{}，{1}}

• 对于{1，2}，取{{}，{1}}，向每个子集加2以得到{{2}，{1，2}}，并与{{}，{1}}取并{{}，{1}，{2}，{1、2}}

• 重复直到达到n

Answer 2

回答为时已晚，但是在这里听起来很容易采用迭代方法：

1）对于一组n元素，获取的值2^n。将有2 ^ n个子集。（2 ^ n，因为每个元素可以是present（1）或不存在（0）。因此对于n个元素，将有2 ^ n个子集。）例如：

for 3 elements, say {a,b,c}, there will be 2^3=8 subsets

2）获得的二进制表示形式2^n。例如：

8 in binary is 1000

3）从0转到(2^n - 1)。在每次迭代中，对于二进制表示形式中的每个1，请形成一个子集，其子元素对应于二进制表示形式中该1的索引。例如：

For the elements {a, b, c}

000 will give    {}

001 will give    {c}

010 will give    {b}

011 will give    {b, c}

100 will give    {a}

101 will give    {a, c}

110 will give    {a, b}

111 will give    {a, b, c}

4）对在步骤3中找到的所有子集进行并集。返回。例如：

Simple union of above sets!

Answer 3

万一其他人来了并且仍然想知道，这是一个使用C ++中迈克尔的解释的函数

vector< vector<int> > getAllSubsets(vector<int> set)

{

    vector< vector<int> > subset;

    vector<int> empty;

    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)

    {

        vector< vector<int> > subsetTemp = subset;

        for (int j = 0; j < subsetTemp.size(); j++)

            subsetTemp[j].push_back( set[i] );

        for (int j = 0; j < subsetTemp.size(); j++)

            subset.push_back( subsetTemp[j] );

    }

    return subset;

}

但是要考虑到，这将返回一组大小为2 ^ N的集合，其中包含所有可能的子集，这意味着可能存在重复项。如果您不希望这样做，我建议您实际使用a set而不是a vector（我曾经使用它来避免代码中的迭代器）。