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

子集生成法

程序员文章站 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;
}

相关标签: 算法 生成子集