[算法设计]求幂集

算法设计与分析(1)

求幂集问题(穷举法)

给定一个数n,求出从1-n的所有子集

法一:直接穷举

#include <stdio.h>
#define MaxN 100 //元素的最大值
#define MaxSize 100 //子集的最大值

typedef struct{
	int n; //子集我的个数
	int data[MaxSize][MaxN]; //元素
}PsetType;


void copy(int a[], int b[], int n){//将a数组的值复制给b数组
	for(int i=0; i<=n; ++i)
		b[i] = a[i];
}

void pset(int n, PsetType &p){
	int a[MaxN];
	//初始化
	p.data[0][0] = 0;
	p.n = 1;
	//初始化结束
	for(int i=1; i<=n; ++i){
		int m = p.n; //原幂集中子集的个数
		for(int j=0; j<m; ++j){
			copy(p.data[j], a, p.data[j][0]);
			a[0]++; //子集元素个数加1
			a[a[0]] = i;
			copy(a, p.data[p.n], a[0]);
			p.n++;
		}
	}
}


void disp(PsetType p){
	for(int i=0; i<p.n; ++i){
		printf("{");
		for(int j=1; j<=p.data[i][0];++j){
		printf("%d",p.data[i][j]);
		}
		printf("}\n");
	}
}

int main(){
	PsetType p;
	int n = 5;
	pset(n, p);
	disp(p);
	return 0;
}

法二:增量穷举法

#include <stdio.h>
#define MaxN 100 //元素的最大值
#define MaxSize 100 //子集的最大值

typedef struct{
	int n; //子集我的个数
	int data[MaxSize][MaxN]; //元素
}PsetType;


void copy(int a[], int b[], int n){//将a数组的值复制给b数组
	for(int i=0; i<=n; ++i)
		b[i] = a[i];
}

void pset(int n, PsetType &p){
	int a[MaxN];
	//初始化
	p.data[0][0] = 0;
	p.n = 1;
	//初始化结束
	for(int i=1; i<=n; ++i){
		int m = p.n; //原幂集中子集的个数
		for(int j=0; j<m; ++j){
			copy(p.data[j], a, p.data[j][0]);
			a[0]++; //子集元素个数加1
			a[a[0]] = i;
			copy(a, p.data[p.n], a[0]);
			p.n++;
		}
	}
}


void disp(PsetType p){
	for(int i=0; i<p.n; ++i){
		printf("{");
		for(int j=1; j<=p.data[i][0];++j){
		printf("%d",p.data[i][j]);
		}
		printf("}\n");
	}
}

int main(){
	PsetType p;
	int n = 5;
	pset(n, p);
	disp(p);
	return 0;
}

示例图: