欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求集合的所有子集

程序员文章站 2024-03-21 15:02:46
...

转载博客:https://blog.csdn.net/yanerhao/article/details/77075462

我们知道一个一个包含n个元素的集合一共有2^n个子集,例如:

集合S包含三个元素{a, b, c},则它的所有子集为:{ }(空集), {a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。

这里先用位操作的思路来求解,具体方法:用2进制Bit位来标记集合中的某个元素是否被选中,1代表选中,0代表未选中。例如集合{a, b, c}的所有子集可如下表示:

{}(空集)               0 0 0

{a}                       0 0 1

{b}                       0 1 0

{c}                       1 0 0

{a, b}                   0 1 1

{a, c}                   1 0 1

{b, c}                   1 1 0

{a, b, c}               1 1 1

分析中也可以看出一个包含N个元素的集合S有2^N个子集,非常容易想到的方法就是遍历0~2^N-1的所有整数,并转化为二进制,按以上思路输出所有子集:
代码:
 

void get_allsubset(int a[],int n){
int mask=0;
int start=0;
int end=(1<<n)-1;
int i=0;
bool isnull;
for(mask=start;mask<=end;mask++){
    isnull=1;
    for(i=0;i<n;i++)
	if((1<<i)&mask){
	    isnull=0;
	    cout<<a[i]<<" ";
	                }
    if(isnull)cout<<"!";
    cout<<endl;
                                  }
}

 

相关标签: 子集