子集生成算法

2019-11-08 00:43:55

字体：大中小

来源：转载

供稿：网友

刘汝佳书上的内容这里的代码对现阶段的提升很有用下文提到的集合其元素默认为0~n-1（n）个

1.增量构造法

意思就是一次选一个放到Ａ里

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <deque>#include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <cctype>#include <algorithm>using namespace std;typedef long long ll;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;#define mem(s,t) (memset(s,t,sizeof(s)))#define SZ(v) (int(v.size()))#define D(v) cout<<#v<<" "<<v<<endlint A[20];void PRint_subset(int n,int* A,int cur){ for(int i=0;i<cur;i++) printf("%d ",A[i]); printf("/n"); int s =cur ? A[cur-1]+1 : 0;//第一个记为0 可以学习的代码 for(int i=s;i<n;i++){ A[cur]=i;给下标为cur的赋值 print_subset(n,A,cur+1); //递归构造子集 }}int main(){#ifdef LOCAL freopen("in.txt","r",stdin); freopen("o.txt","w",stdout);#endif int n; cin>>n;//n不要太大 print_subset(n,A,0); return 0;}

先写for 再递归 可以得到这种输出

这里写图片描述

2.位向量法

构造一个位向量B[i]，而不是直接构造子集A本身 B[i]==1当且仅当i在子集A 中

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <deque>#include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <cctype>#include <algorithm>using namespace std;typedef long long ll;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;#define mem(s,t) (memset(s,t,sizeof(s)))#define SZ(v) (int(v.size()))#define D(v) cout<<#v<<" "<<v<<endlvoid print_subset(int n,int* B,int cur){ if(cur==n){ for(int i=0;i<n;i++) if(B[i]) cout<<i<<" "; cout<<endl; return; }else{ B[cur]=1; print_subset(n,B,cur+1); B[cur]=0; print_subset(n,B,cur+1); }}int main(){#ifdef LOCAL freopen("in.txt","r",stdin); freopen("o.txt","w",stdout);#endif int n; cin>>n; int B[20]; print_subset(n,B,0); return 0;}

解答树有2047个结点，而上一种只有1024个但实际应用大部分情况区别不大这里写图片描述

3.二进制法

技巧性不错的解法需要好好学习 //注意这里的集合为0~n-1分别对应 10110 01100 00100 11110 {1,2,4} {2,3} {2} {1,2,3,4}

#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <deque>#include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <cctype>#include <algorithm>using namespace std;typedef long long ll;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;#define mem(s,t) (memset(s,t,sizeof(s)))#define SZ(v) (int(v.size()))#define D(v) cout<<#v<<" "<<v<<endlvoid print_subset(int n,int s){ for(int i=0;i<n;i++) if(s&(1<<i)) printf("%d ",i); printf("/n");} int main(){#ifdef LOCAL freopen("in.txt","r",stdin); freopen("o.txt","w",stdout);#endif int n;cin>>n; for(int i=0;i<(1<<n);i++){//i的编码为0,1,2,3,4,..., 2^n-1 //即为各个子集的编码 print_subset(n,i); } return 0;}

这里写图片描述