子集生成法
程序员文章站
2024-03-21 15:06:58
...
生成集合的子集的时候,经常使用两种方式位向量法和二进制法
位向量法生成子集:
/*子集生成位向量法*/
#include<cstdio>
int B[20];
void print_subset(int n,int *B,int cur)
{
if(cur == n) {
for(int i=0;i<cur;i++) if(B[i]) printf("%d ",i);
printf("\n");
return ;
}
B[cur]=1;
print_subset(n,B,cur+1);
B[cur]=0;
print_subset(n,B,cur+1);
}
int main()
{
print_subset(3,B,0);
return 0;
}
二进制法生成子集:
/*算法思想
例如求4个元素 3 2 1 0 的子集。
那么用二进制的1代表每一位是否选中。
十进制 二进制
0 0000 代表空集
1 0001 代表{0}
2 0010 代表{1}
3 0011 代表{0,1}
4 0100 代表{2}
...
15 1110 代表{3,2,1}
16 1111 代表{3,2,1,0}
如果n很大的话可以用字符串模拟二进制
*/
# include <stdio.h>
# include <algorithm>
using namespace std;
//二进制法求子集
void print_subset(int n,int s){
for(int i=0;i<n;i++){
if(s & (1<<i)) //1左移i位,监测s的哪一位为1,为1的话输出
printf("%d ",i);
}
printf("\n");
}
int main() {
int n=3;
for(int i=0;i<(1<<n);i++){//1左移n位等价于2^n-1.因为子集个数2^n-1
print_subset(n,i);
}
return 0;
}
上一篇: 数据结构(不带头结点的单链表)