查找集合的所有子集

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 subsets2）获得的二进制表示形式2^n。例如：8 in binary is 10003）从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){&nbsp; &nbsp; vector< vector<int> > subset;&nbsp; &nbsp; vector<int> empty;&nbsp; &nbsp; subset.push_back( empty );&nbsp; &nbsp; for (int i = 0; i < set.size(); i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; vector< vector<int> > subsetTemp = subset;&nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < subsetTemp.size(); j++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subsetTemp[j].push_back( set[i] );&nbsp; &nbsp; &nbsp; &nbsp; for (int j = 0; j < subsetTemp.size(); j++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subset.push_back( subsetTemp[j] );&nbsp; &nbsp; }&nbsp; &nbsp; return subset;}但是要考虑到，这将返回一组大小为2 ^ N的集合，其中包含所有可能的子集，这意味着可能存在重复项。如果您不希望这样做，我建议您实际使用a set而不是a vector（我曾经使用它来避免代码中的迭代器）。