如果我們有一個求集合的所有子集(包括集合自身)的需求，即有一個集合s,包括兩個元素 <a,b>，則其所有的子集為<a,ab,b>.

不難求得，子集個數(shù)sn與原集合元素個數(shù)n之間的關系為：sn=2^n-1。

?

本文分別講述兩種實現(xiàn)方法：

?

一：位圖法：

1）構造一個和集合一樣大小的數(shù)組A，分別與集合中的某個元素相應，數(shù)組A中的元素僅僅有兩種狀態(tài)：“1”和“0”，分別代表每次子集輸出中集合中相應元素是否要輸出。這樣數(shù)組A能夠看作是原集合的一個標記位圖。

2）數(shù)組A模擬整數(shù)“加一”的操作，每“加一”之后，就將原集合中全部與數(shù)組A中值為“1”的相相應的元素輸出。

設原集合為<a,b,c,d>。數(shù)組A的某次“加一”后的狀態(tài)為[1,0,1,1]，則本次輸出的子集為<a,c,d>。

詳細代碼例如以下：

/*使用非遞歸的思想 假設有一個數(shù)組? 大小為n那么就使用n 位的二進制 假設對應的位為1 那么就輸出這個位 假設對應的位為0 那么就不輸出這個位*//*使用位圖的思想 構造一個位集合 大小和數(shù)組大小一樣，假設位圖中對應的位為1,表示能夠輸出這個數(shù)組中的元素 假設位圖中對應位為0 表示數(shù)組中對應位不輸出這里模擬位圖使用的數(shù)組 ，這里的重點是模擬數(shù)組加1的操作*//*使用數(shù)組模擬位圖加1的操作? 數(shù)組能夠一直加1? 直到數(shù)組內(nèi)全部元素都是1函數(shù)返回值為bool 數(shù)組初始化最高位為1*/ #define MAX_LEN 10 void bitmap(char str[],const int n) {bitset<MAX_LEN> count;wang.set();int i=0;unsigned long value = wang.to_ulong();cout<<wang<<" "<<value<<endl;int count=0;while(value){bitset<MAX_LEN> bit(value--);for(i=0;i<bit.size();i++)if(bit[i])cout<<str[i];cout<<endl;count++;}cout<<count<<endl; }

3）時間復雜度：O(n*2^n)。事實上，在遍歷輸出子集的過程中。能夠對程序做進一步的優(yōu)化。

比如。在第m次迭代中。僅僅須要遍歷前k個元素，k=log2(m)+1。這樣，不考慮數(shù)組模擬"加一"操作的話,總遍歷次數(shù)為Sn=(n-2)*2^n+2,n>=2;Sn=1,n=1。盡管復雜度不變，但總執(zhí)行時間會降低。

4）空間復雜度：該方法每次迭代都是獨立進行，與上次迭代的結果沒有不論什么關系。因此每次輸出子集之后內(nèi)存都能夠被反復利用。

僅僅須要一個與原集合相同大小的數(shù)組?？臻g復雜度為O(n)。

?

?

二：遞歸迭代法：

1）採用遞歸迭代。詳細步驟例如以下，

設。原始集合s=<a,b,c,d>，子集結果為r：

第一次迭代：

r=<a>

第二次迭代：

r=<a ab b>

第三次迭代：

r=<a ab b ac abc bc c>

第四次迭代：

r=<a ab b ac abc bc c ad abd bd acd abcd bcd cd d>

?

每次迭代，都是上一次迭代的結果+上次迭代結果中每一個元素都加上當前迭代的元素+當前迭代的元素。

詳細代碼例如以下：

/*上述方法不可用 明確遞歸的思想 以下每次都是輸出back中的字符就可以 這次輸出的子集就是上次輸出的子集 +這次迭代的元素 + 這次迭代的元素的本身*/ #if 1 void print(char* str) {/*使用兩個數(shù)組。一個記錄上次迭代的結果 一個記錄這次須要輸出的結果 vec記錄的是下次迭代須要參考的子集back記錄的是參考vec迭代以后生成新的子集*/int count=0;vector<char> vec;vector<char> back;int j;for(int i=0;i<strlen(str);i++){if(i == 0){vec.push_back(str[i]);vec.push_back(',');back=vec;}else{for(j=0;j<back.size();j++)if(back[j] == ','){back.insert(back.begin() +j,str[i]);j++;}back.push_back(str[i]);back.push_back(','); }for(j=0;j<back.size();j++){if(back[j] == ','){printf("\r\n");count++;}elseprintf("%c",back[j]);if(i)vec.push_back(back[j]);}back=vec;}printf("sub_set count is %d \r\n",count); } #endif

2）時間復雜度

依據(jù)上述過程，不難求的。第k次迭代的迭代次數(shù)為：2^k-1。

n>=k>=1。迭代n次，總的遍歷次數(shù)為：2^(n+1)-(2+n),n>=1。

則時間復雜都為O(2^n)。

?

3）空間復雜度

因為該算法。下一次迭代過程都須要上一次迭代的結果，而最后一次迭代之后就沒有下一次了。

因此如果原始集合有n個元素。則在迭代過程中，總共須要保存的子集個數(shù)為2^(n-1)-1,n>=1。

但須要注意的是，這里之考慮了子集的個數(shù)，每一個子集元素的長度都視為1，這點要注意。

總結：

遞歸是非常耗時的。由于是遞歸，在第一種方法時，使用了C++中的bitset,這種方法效率非常高，在第二個方法中，使用兩個向量的目的是，一個向量記錄了這次迭代須要輸出的集合，一個向量是為了這次迭代須要參考上次輸出的情況。

轉載于:https://www.cnblogs.com/yxwkf/p/5367089.html

總結

以上是生活随笔為你收集整理的两种求集合全部子集的方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。