集合的幂集

集合A的幂集是由集合A的所有子集所组成的的集合。

如:A={1,2,3},则A的幂集P(A)={{1,2,3},{1,2},{1,3},{1},{2,3},{2},{3},{ }}。

求一个集合的幂集就是求一个集合的所有的子集,方法有穷举法,分治法,回溯等,这里主要介绍一下回溯法

回溯法是设计递归过程的一种重要的方法,它的求解过实质上是一个先序遍历一棵“状态树”的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中的。

幂集中的每个元素是一个集合,它或是空集,或含集合A中一个元素,或含集合A中两个元素…… 或等于集合A。反之,从集合A 的每个元素来看,它只有两种状态:它或属幂集的无素集,或不属幂集的元素集。则求幂集p(A)的元素的过程可看成是依次对集合A中元素进行“取”或“舍”的过程,并且可以用一棵二叉树来表示过程中幂集元素的状态变化过程,树中的根结点表示幂集元素的初始状态(空集);叶子结点表示它的终结状态,而第i层的分支结点,则表示已对集合A中前i-1个元素进行了取舍处理的当前状态(左分支表示取,右分支表示舍 )。因此求幂集元素的过程即为先序遍历这棵状态树的过程。

具体算法如下:

C/C++描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>
#include <ctype.h>
#include <stdlib.h>
#include <string>
using namespace std;
 
char a[100];
char b[100];
 
void GetPowerSet(int i, char a[])
{
	char x;
	int k;
	int len = strlen(a);
	if(i >= len)
	{
		if(b[0])
			cout << b <<  endl;
		else
			cout << "XX" << endl;  // 表示空集
	}
	else
	{
		x = a[i];
		k = strlen(b);
		b[k] = x;
		GetPowerSet(i+1, a);
		b[k] = 0;
		GetPowerSet(i+1, a);
	}
}
 
 
int main()
{
	while(scanf("%s", a) != EOF)
	{
		printf("%s的幂集是:\n", a);
		printf("------------\n");
		GetPowerSet(0, a);
		printf("------------\n");
	}
}

注:以上部分来至网上。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《集合的幂集》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注