bitset使ってみた． combination::nCrの列挙

がんばって、Combinationの列挙をしてみた．

#include  
#include 
#include 
#include 
#include 
using namespace std;

long long mypow(int k, int n) {
  long long ans = 1;
  for(int i = 0; i < n; i++) {
    ans *= k;
  }
  return ans;
}



int main() {
  const int N = 21;
  int ch = 7;
  vector > comb;
  long long sz = mypow(2, N);
  int begin = (1 << ch) -1;
  int end = (begin << (N-ch) );
  for(int i = (1 << ch)-1; i <= end; i++) {
    bitset tmp(i);
    vector cop;

    if(tmp.count() == ch) {
      for(int j = 0; j < N; j++) {
	if(tmp[j] == 1) {
	  cop.push_back(j+1);
	}
      }
      comb.push_back(cop);
    } //end if
  }
  sort(comb.begin(), comb.end());
  for(int i = 0; i < comb.size(); i++) {
    for(int j = 0; j < comb[i].size(); j++) {
      cout << comb[i][j] << " ";
    }
    cout << endl;
  }
}

赤の文字を加えたら、辞書順になったよぉ．

手軽にCombination列挙するなら、next_permutation使うといいかも。

string number = "123456789";
string prev = ""; cur = "";  //上r桁を取る
do {
	cur = number.substr(0, n);
	if(number != prev) {
	}
	perv = cur;
}while(next_permutation(number.begin(), number.end()) );
//でも、無駄な作業が多くなる〜