如何求全集的全部子集

ryuken2000

已知一个全集，求它的全部子集。
比如全集为{A、B、C}，则它的全部子集是：
{A、B、C}
{A、B}
{A、C}
{A}
{B、C}
{B}
{C}
{}

要求使用递归方式来实现。

多谢。

dzbjet

算法：
求集合的全部子集：
输入：一个集合
输出：该集合的所有子集

给定集合A = { a1, a2, a3, ...., an ( 1 <= n ) }
去集合的第一个元素a1, 剩下的A的元素组成集合B。即 A = { a1, B } ( B 为集合 )
则可得知：
集合A的全部子集为：
A
{a1}
B 的全部子集
以及
A 与B的全部非空真子集的组合。

[ 本帖最后由 dzbjet 于 2007-9-13 13:54 编辑 ]

cjaizss

子集的编码：
A = { a1, a2, a3, ...., an ( 1 <= n ) }
其子集：
{am1,am2,am3...amk};
二进制编码：
0 0 0... 1  0...0  1  0....0    1    0 ...
1 2 3...m1...     m2....        mk ...
现在明白了吗？
用一个数从0自加到2^n-1,按照其二进制编码依次输出

ryuken2000

非常感谢。
我现在开始写代码。

cjaizss

原帖由 dzbjet 于 2007-9-13 13:51 发表
算法：
求集合的全部子集：
输入：一个集合
输出：该集合的所有子集

给定集合A = { a1, a2, a3, ...., an ( 1  

递归是一种解决手段，可是特别这个时候偶不考虑，不仅仅效率，而且在这里可能会产生爆炸性效果。

ryuken2000

刚根据cjaizss的算法，写了一个非递归实现。
不过我想锻炼一下递归思维，现在还没有想出该如何写dzbjet 提供的递归算法。

在此谢谢二位。

ryuken2000

下面是我刚才实现的非递归方式的源代码，有没有更精巧的实现，大家讨论一下。

#include <stdio.h> #include <math.h> int BinaryPlus(char *list, int len); int PrintSubset(char *subset, char *list, int len); int main(int argc, char *argv[]) { &nbsp;&nbsp;int i, len, power; &nbsp;&nbsp;char *p; &nbsp;&nbsp;if (argc != 2) { &nbsp;&nbsp;&nbsp;&nbsp;fprintf(stderr,"USAGE: listsubsets <SETS>\n"); &nbsp;&nbsp;&nbsp;&nbsp;return 0; &nbsp;&nbsp;} &nbsp;&nbsp;len = strlen(argv[1]); &nbsp;&nbsp;p = (char *)malloc(len); &nbsp;&nbsp;if (p == NULL) { &nbsp;&nbsp;&nbsp;&nbsp;fprintf(stderr, "ERROR: can not allocate memory!\n"); &nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;} &nbsp;&nbsp;memset(p, 0x00, len); &nbsp;&nbsp;power = pow(2, len); &nbsp;&nbsp;for (i = 0; i < power; i++) { &nbsp;&nbsp;&nbsp;&nbsprintSubset(argv[1], p, len); &nbsp;&nbsp;&nbsp;&nbsp;putchar('\n'); &nbsp;&nbsp;&nbsp;&nbsp;BinaryPlus(p, len); &nbsp;&nbsp;} &nbsp;&nbsp;free(p); &nbsp;&nbsp;return 0; } int BinaryPlus(char *list, int len) { &nbsp;&nbsp;int i; &nbsp;&nbsp;for (i = 0; i < len; i++) { &nbsp;&nbsp;&nbsp;&nbsp;list[i] = (++list[i]) % 2; &nbsp;&nbsp;&nbsp;&nbsp;if (list[i] == 1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break; &nbsp;&nbsp;} &nbsp;&nbsp;return 0; } int PrintSubset(char *subset, char *list, int len) { &nbsp;&nbsp;int i; &nbsp;&nbsp;for (i = 0; i < len; i++) &nbsp;&nbsp;&nbsp;&nbsp;if (list[i] == 1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;putchar(subset[i]); &nbsp;&nbsp;return 0; }

[ 本帖最后由 ryuken2000 于 2007-9-13 14:37 编辑 ]

ypxing

这种题目,递归的时间复杂度是一样的
只是函数调用的次数多了,效率低而已.

原帖由 cjaizss 于 2007-9-13 14:06 发表

递归是一种解决手段，可是特别这个时候偶不考虑，不仅仅效率，而且在这里可能会产生爆炸性效果。

dzbjet

我给个 phtyon 的实现吧：
虽然此问题不适合用递归，因为递归的深度是跟集合的元素个数成正比的。

def get_SubSet(A):     all_set = []     # 全集 相当于 A     all_set.append( A )     if len(A) > 1:         # 集合A的第一个元素为一个集合, 相当于 a1         a1 = A[0]         all_set.append( list(a1) )         # 求剩下元素组成集合的所有集合, 相当于 B         B = A[1:]         for item in get_SubSet( B ):             all_set.append( item )             # 求 a1 与 B中的所有非空真子集 所构成的所有集合             if item != B and item != []:                 new_item = item[0:]                 new_item.insert(0,a1)                 all_set.append( new_item )         return all_set     # <= 1, 加入空集     all_set.append([])     return all_set

[ 本帖最后由 dzbjet 于 2007-9-13 16:29 编辑 ]

ryuken2000

非常感谢