#include <cstdio> #include <cstring> #include <vector> using namespace std; void DoSth(vector<int>& chosen) { for(int i=0; i<chosen.size(); i++) printf("%d ", chosen[i]); printf(" "); } void Combination1(int n, int m, int begin, vector<int>& chosen) { if(n - begin + 1 < m) return; chosen.push_back(begin); if(m - 1 == 0) DoSth(chosen) else Combination1(n, m - 1, begin + 1, chosen); chosen.pop_back(); Combination1(n, m, begin + 1, chosen); } void Combination2(int n, int m, int begin, vector<int>& chosen) { if(n - begin + 1 < m) return; if(m == 0) { DoSth(chosen); return; } for(int i=begin; i<=n; i++) { chosen.push_back(i); Combination2(n, m - 1, i + 1, chosen); chosen.pop_back(); } } void Combination(int n, int m) { vector<int> chosen; Combination1(n,m,1,chosen); } void Permutation(int n, int m, int k, vector<int> &chosen) { if(chosen.size()>m || chosen.size()+n-k+1<m) return; if(k==m) { for(int i=0; i<chosen.size(); i++) printf("%d ",chosen[i]+1); printf(" "); return; } for(int i=0; i<n; i++) { int ok=true; for(int j=0; j<chosen.size(); j++) { if(i==chosen[j]) { ok=false; break; } } if(ok) { chosen.push_back(i); Permutation(n,m,k+1,chosen); chosen.pop_back(); } } } void Permutation(int n, int m) { vector<int> chosen; Permutation(n, m, 0, chosen); } void Subset(int n, int begin, vector<int> &chosen) { for(int i=0; i<chosen.size(); i++) printf("%d ", chosen[i]+1); printf(" "); if(begin==n) return; for(int i=begin; i<n; i++) { chosen.push_back(i); Subset(n, i+1, chosen); chosen.pop_back(); } } void Subset(int n) { vector<int> chosen; Subset(n, 0, chosen); } int main() { int op; do{ printf("Combination(1) or Permutation(2) or Subset(3)? "); int n, m; scanf("%d",&op); printf("Input n and m "); if(op==3) printf("Just input m to your heart's content. "); scanf("%d%d",&n,&m); switch(op) { case 1: Combination(n,m); break; case 2: Permutation(n, m); break; case 3: Subset(n); break; } printf("continue(1) or exit(0)? "); scanf("%d",&op); }while(op==1); return 0; }