C++数据结构--组合学--查找集合的所有子集

朱雀 2021-11-05 12:28 377阅读 0赞

**1.查找所有子集  
对于集合S，如果S有n个元素，则它有2的n次方个子集  
问题求解步骤：  
\*假设S有n个元素，从S中删除元素x,剩下n-1个元素构成一个新的集合S1,则S1有2的n-1次方个子集.  
\*将元素x加入S1中的每个子集中，这样就产生了新的2的n-1次方个子集，这些新子集和S1构成了集合S的所有子集  
Example：对于集合S\{1,2,3\}  
![20130810084713437][]  
  
  
实现代码：  
  
  
\#include<iostream>  
\#include<set>  
using namespace std;  
  
  
template<typename T>  
set<set<T>> combination(set<T> &s)  
\{  
set<set<T>> result;//结果集  
set<set<T>> prime;//保存从S中删除元素x后的集合S1的所有子集   
set<set<T>> prime\_plus;//保存从s1的每个子集加上X后构成的所有子集   
 if(s.empty()) //空集时结束递归   
\{   
 set<T> empty; //空集  
result.insert(empty);  
return result;  
\}  
  
T temVal=\*s.begin(); //保存X   
s.erase(s.begin()); //从S集合中删除X  
prime=combination(s);  
auto it=prime.begin();  
set<T> temSet;  
for(;it!=prime.end();it++) //从s1的每个子集加上X   
\{   
temSet=\*it;  
temSet.insert(temVal);  
prime\_plus.insert(temSet);  
\}  
  
for(set<T> x:prime) //把prime加到结果集中   
 result.insert(x);  
  
for(set<T> x:prime\_plus) //把prime\_plus加到结果集中   
 result.insert(x);  
  
  
return result;  
  
  
\}  
  
  
  
  
  
  
测试代码：  
template<typename T>  
//打印所有子集   
void print(set<set<T>> &ss)  
\{   
for(set<T> p:ss)  
\{   
if(p.empty())  
 cout<<"\{\}"<<ends;  
else  
\{   
cout<<"\{";  
for(T x:p)  
 cout<<x<<ends;  
cout<<"\}"<<ends;  
  
\}   
  
\}  
\}  
  
int main ()  
\{  
set<int> s\{1,2,3\};  
  
set<set<int>> res=combination(s);  
  
  
print(res);  
return 0;  
\}**

**运行结果：**

**![Center][]**

[20130810084713437]: /images/20211105/9532875101a34ff5b1747c0f5f69260e.png
[Center]: /images/20211105/e7783a94ba15427e817dd8c5ef8e4105.png