求集合的所有子集
對(duì)于任意集合A，元素個(gè)數(shù)為n（空集n=0），其所有子集的個(gè)數(shù)為2^n個(gè)
如集合A={a,b,c},其子集個(gè)數(shù)為8；對(duì)于任意一個(gè)元素，在每個(gè)子集中，
要么存在，要么不存在，對(duì)應(yīng)關(guān)系是：
a->1或a->0
b->1或b->0
c->1或c->0
映射為子集：
(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b ? )
(1,0,1)->(a, ? c)
(1,0,0)->(a ? ? ?)
(0,1,1)->( ? b,c)
(0,1,0)->( ? b ? )
(0,0,1)->( ? ? ?c)
(0,0,0)->@ (@表示空集)
算法（1）：
觀察以上規(guī)律，與計(jì)算機(jī)中數(shù)據(jù)存儲(chǔ)方式相似，故可以通過(guò)一個(gè)整型數(shù)（int）與
集合映射000...000 ~ 111...111（0表示有，1表示無(wú)，反之亦可），通過(guò)該整型數(shù)
逐次增1可遍歷獲取所有的數(shù)，即獲取集合的相應(yīng)子集。
在這里提一下，使用這種方式映射集合，在進(jìn)行集合運(yùn)算時(shí)，相當(dāng)簡(jiǎn)便，如
交運(yùn)算對(duì)應(yīng)按位與&，{a,b,c}交{a,b}得{a,b}<--->111&110==110
并運(yùn)算對(duì)應(yīng)按位或|，
差運(yùn)算對(duì)應(yīng)&~。
算法（2）：
設(shè)函數(shù)f(n)=2^n (n>=0)，有如下遞推關(guān)系f(n)=2*f(n-1)=2*(2*f(n-2))
由此可知，求集合子集的算法可以用遞歸的方式實(shí)現(xiàn)，對(duì)于每個(gè)元素用一個(gè)映射列表marks，標(biāo)記其
在子集中的有無(wú)
很顯然，在集合元素個(gè)數(shù)少的情況下，算法（1）優(yōu)于算法（2），因?yàn)橹恍柰ㄟ^(guò)加法運(yùn)算，便能映射
出子集，而算法（2）要遞歸調(diào)用函數(shù)，速度稍慢。但算法（1）有一個(gè)嚴(yán)重缺陷，集合的個(gè)數(shù)不能大于在
計(jì)算機(jī)中一個(gè)整型數(shù)的位數(shù)，一般計(jì)算機(jī)中整型數(shù)的為32位。對(duì)于算法（2）就沒(méi)這樣限制。
-----------------------------------------------------------------------------------------
算法（1）,取低位到高位碼段作為映射列表
[cpp]view plaincopy
template
voidprint(T?a[],intmark,intlength)
{
boolallZero=true;
intlimit=1<
for(inti=0;i
{
if(((1<
{
allZero=false;
cout<
}
}
if(allZero==true)
{
cout<<"@";
}
cout<
}
template
voidsubset(T?a[],intlength)
{
if(length>31)return;
intlowFlag=0;//對(duì)應(yīng)000...000
inthighFlag=(1<
for(inti=lowFlag;i<=highFlag;++i)
{
print(a,i,length);
}
}
-----------------------------------------------------------------------------------------
算法（2）
[cpp]view plaincopy
template
voidprint(T?a[],boolmarks[],intlength)
{
boolallFalse=true;
for(inti=0;i
{
if(marks[i]==true)
{
allfalse=false;
cout<
}
}
if(allFalse==true)
{
cout<<"@";
}
cout<
}
template
voidsubset(T?a[],boolmarks[],intm,intn,intlength)
{
if(m>n)
{
print(a,marks,length);
}
else
{
marks[m]=true;
subset(a,marks,m+1,n,length);
marks[m]=false;
subset(a,marks,m+1,n,length);
}
}
