ある集合のすべての組み合わせを列挙したいときに、bit全探索と呼ばれるアルゴリズムを使うといいことを学んだ。

int main() {
  int n = 3;

  // 組み合わせの数だけループする
  for (int bit = 0; bit < (1 << n); bit++) {
    // 組み合わせに含まれる要素
    vector<int> numbers;

    // 全要素についてループする
    for (int i = 0; i < n; i++) {
      // 要素が組み合わせに含まれるかチェックする
      if (bit & (1 << i)) {
        // 組み合わせに要素を追加する
        numbers.push_back(i);
      }
    }

    printf("{");
    for (int i = 0; i < numbers.size(); i++) {
      printf((i == 0) ? "%d" : " %d", numbers[i]); 
    }
    printf("} ");
  }
  printf("\n");
}

$ ./a.out
{} {0} {1} {0 1} {2} {0 2} {1 2} {0 1 2}

組み合わせの数

for (int bit = 0; bit < (1 << n); bit++) {
}

ある集合のすべての組み合わせは、各要素について含めるか含めないかの2択によって生まれるので、2^<要素数>になる。1 << nは2^nと同じなので、組み合わせの数だけループしていることになる。

組み合わせの作り方

for (int i = 0; i < n; i++) {
  if (bit & (1 << i)) {
  }
}

bit & (1 << i)は要素iが組み合わせに含まれるかをチェックしている。&はAND演算なので、bitと(1 << i)をそれぞれ2進数として考える。

bitは上のコードだと0から7までの数になるので、2進数では000から111までということになる。

一方、iは上のコードだと0, 1, 2なので、(1 << i)はそれぞれ001, 010, 100になる。

なので、bitが000だったらどの要素も含まれないことになるし、101だったら0と2が含まれることになる。つまり、要素の組み合わせをbitが示す2進数で表していると言える。