perogram

N個からK個選ぶ全探索(蟻本 p144)

f:id:peroon:20191117172942j:plain

  • 例として、N個からK個選ぶことを考えます
  • N=5
  • K=2
  • N人のクラスからK人の委員長を選ぶことをイメージします
  • もちろんN人はそれぞれ別の人です(赤玉・白玉のように同一視しない)

蟻本VER

    ll n = 5;
    ll k = 2;
    int comb = (1<<k) - 1;
    while(comb<1<<n){

      //ここで組み合わせに対して処理をする
      cout << bitset<5>(comb) << endl;

      int x = comb & -comb, y = comb + x;
      comb = ((comb & ~y) / x>>1) | y;
    }

出力

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000
  • 各行で1が2つピッタリ出現していることを確認してください

next_permutation VER

    vector<int> V = {0, 0, 0, 1, 1};
    do{
      debug(V);
    }while(next_permutation(ALL(V)));

出力

[V]: {0, 0, 0, 1, 1}
[V]: {0, 0, 1, 0, 1}
[V]: {0, 0, 1, 1, 0}
[V]: {0, 1, 0, 0, 1}
[V]: {0, 1, 0, 1, 0}
[V]: {0, 1, 1, 0, 0}
[V]: {1, 0, 0, 0, 1}
[V]: {1, 0, 0, 1, 0}
[V]: {1, 0, 1, 0, 0}
[V]: {1, 1, 0, 0, 0}
  • 同じく、各行で1が2つピッタリ出現しています

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?