ある集合のすべての組み合わせを列挙したいときに、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進数で表していると言える。