求所有子集集合 一定要好好学习

求所有子集集合 一定要好好学习

之前自己写集合自己集合的时候,总想着暴力枚举,各种错综复杂条件,吃力不讨好,看看别人的算法,好好学习

求集合的所有子集的算法

对于任意集合A,元素个数为n(空集n=0),其所有子集的个数为2^n个

如集合A={a,b,c},其子集个数为8;对于任意一个元素,在每个子集中,

要么存在,要么不存在,对应关系是:

映射为子集:

算法(1):

观察以上规律,与计算机中数据存储方式相似,故可以通过一个整型数(int)与集合映射000…000 ~ 111…111(0表示有,1表示无,反之亦可),通过该整型数逐次增1可遍历获取所有的数,即获取集合的相应子集。

在这里提一下,使用这种方式映射集合,在进行集合运算时,相当简便,如
交运算对应按位与&,{a,b,c}交{a,b}得{a,b}<—>111&110==110
并运算对应按位或|
差运算对应&~。

算法(2):

设函数f(n)=2^n (n>=0),有如下递推关系f(n)=2*f(n-1)=2*(2*f(n-2))由此可知,求集合子集的算法可以用递归的方式实现,对于每个元素用一个映射列表marks,标记其在子集中的有无

很显然,在集合元素个数少的情况下,算法(1)优于算法(2),因为只需通过加法运算,便能映射出子集,而算法(2)要递归调用函数,速度稍慢。但算法(1)有一个严重缺陷,集合的个数不能大于在计算机中一个整型数的位数,一般计算机中整型数的为32位。对于算法(2)就没这样限制。

code

算法1

回溯

参考:
http://plutoblog.iteye.com/blog/976218
https://leetcode.com/problems/subsets/discuss/

打赏

发表评论

电子邮件地址不会被公开。