子集生成

 1 //2016.8.31
 2 #include <iostream>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 void print_subset(int n, int *a, int cur)//增量构造法
 8 {
 9     for(int i = 0; i < cur; i++)cout<<a[i];//打印当前集合，即选出的元素序号
10     cout<<endl;
11     int tmp = cur?a[cur-1]+1:0;//确定当前元素的最小可能值
12     for(int i = tmp; i < n; i++)
13     {
14         a[cur] = i;
15         print_subset(n, a, cur+1);//递归构造子集
16     }
17 }
18 
19 void print_subset2(int n, int *b, int cur)//位向量法
20 {
21     if(cur==n){//打印
22         for(int i = 0; i < n; i++)
23               if(b[i])cout<<i;
24         cout<<endl;
25         return ;
26     }
27     b[cur] = 1;//选择第cur个元素
28     print_subset2(n, b, cur+1);
29     b[cur] = 0;//不选择第cur个元素
30     print_subset2(n, b, cur+1);
31 }
32 
33 void print_subset3(int n)//二进制法，A&B,A|B,A^B分别对应集合A和B的交、并、对称差
34 {
35     for(int s = 0; s < (1<<n); s++){
36         for(int i = 0; i < n; i++)
37               if(s&(1<<i))cout<<i;
38         cout<<endl;
39     }
40 }
41 
42 int main()
43 {
44     int a[4], b[4];
45     print_subset(4, a, 0);
46     cout<<"--------------------------------------"<<endl;
47     print_subset2(4, b, 0);
48     cout<<"--------------------------------------"<<endl;
49     print_subset3(4);
50     return 0;
51 }