查找集合的所有子集

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因为每个元素可以存在(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

如果有其他人过来并且仍在疑惑,这里是使用Michael在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而不是vector(我曾经在代码中避免使用迭代器).

Answer 4

如果要列举所有可能的子集来看看这个文件.他们讨论了不同的方法,如词典顺序,灰色编码和银行家的序列.他们给出了银行家序列的示例实现,并讨论了解决方案的不同特征,例如性能.

Answer 5

在这里,我已经详细解释过了.如果你喜欢博客文章,请做upvote.

http://cod3rutopia.blogspot.in/

如果你在这里找不到我的博客,任何方式都是解释.

这是一个本质上递归的问题.

基本上,对于要出现在子集中的元素,有两个选项:

1)它存在于集合中

2)在集合中没有.

这就是为什么一组n个数具有2 ^ n个子集的原因.(每个元素有2个选项)

下面是打印所有子集的伪代码(C++),后面是一个解释代码如何工作的示例.1)A []是要查找其子集的数字数组.2)bool a []是布尔数组,其中a [i]告诉数字A [i]是否存在于集合中.

print(int A[],int low,int high)  
   {
    if(low>high)  
    {
     for(all entries i in bool a[] which are true)  
        print(A[i])
    }  
   else  
   {set a[low] to true //include the element in the subset  
    print(A,low+1,high)  
    set a[low] to false//not including the element in the subset  
    print(A,low+1,high)
   }  
  }