输出集合的所有子集
时间：2010-09-23 来源：wsnhyjj
有两种方法：
1. 按照位图方法，用一个位图（我代码里用的一个数组）来表示集合，对应的位为1则表示成员存在，为0则不存在，输出地时候遍历位图，输出对应位为1的项。（代码中的SubSet2函数）
2. 思想很简单，每个数字要么在子集中，要么不在子集中，所以我们采取这样的做法，对于原集合中的任意一个数字，我们要么取之，要么不取，用递归实现较方便。（代码中的SubSet函数）
/* * Description: * 输出一个集合的所有子集。 * Author :FinL * Language: C++ * Date : 2010-09-23 */ #include <iostream> using namespace std;
void SubSet(int* arr,int num,int n,int *include) { if(num==n) { for(int i=0;i<n;i++) { if(include[i]) cout<<arr[i]<<" "; } cout<<endl; } else { include[num]=0; SubSet(arr,num+1,n,include); include[num]=1; SubSet(arr,num+1,n,include); } }
void SubSet2(int *arr,int n,int *include) { int sum=0,i=0,k=1; while(i++<n) k *= 2; while(sum<k) { int m=0,tmp=sum; while(m<n) { include[m]=tmp%2; tmp /=2; if(include[m]) cout<<arr[m]<<" "; if(0==tmp) break; m++; } cout<<endl; sum++; } }
int main() { // int arr[]={1,2,4,6,3,7,97,46,32,25,12,11}; int arr[]={1,2,3,4}; int n;
n=sizeof(arr)/sizeof(arr[0]); int *include =new int[n]; memset(include,0,n*sizeof(int));
// SubSet(arr,0,n,include); SubSet2(arr,n,include); return 0; }
/* * Description: * 输出一个集合的所有子集。 * Author :FinL * Language: C++ * Date : 2010-09-23 */ #include <iostream> using namespace std;
void SubSet(int* arr,int num,int n,int *include) { if(num==n) { for(int i=0;i<n;i++) { if(include[i]) cout<<arr[i]<<" "; } cout<<endl; } else { include[num]=0; SubSet(arr,num+1,n,include); include[num]=1; SubSet(arr,num+1,n,include); } }
void SubSet2(int *arr,int n,int *include) { int sum=0,i=0,k=1; while(i++<n) k *= 2; while(sum<k) { int m=0,tmp=sum; while(m<n) { include[m]=tmp%2; tmp /=2; if(include[m]) cout<<arr[m]<<" "; if(0==tmp) break; m++; } cout<<endl; sum++; } }
int main() { // int arr[]={1,2,4,6,3,7,97,46,32,25,12,11}; int arr[]={1,2,3,4}; int n;
n=sizeof(arr)/sizeof(arr[0]); int *include =new int[n]; memset(include,0,n*sizeof(int));
// SubSet(arr,0,n,include); SubSet2(arr,n,include); return 0; }
相关阅读 更多 +
