bit全探索を理解するために

TL;DR

全探索をする際の重要なアルゴリズムとして、bit全探索が挙げられます。bit全探索を使うことで、部分集合を全パターン列挙できます。

しかし、実際のコードを見て何をやっているのか直感的に理解することが難しかったので、自分が理解しやすい形でまとめてみました。

bit全探索のアルゴリズム

bit全探索で使用するbit演算は以下です。0bは2進数表記であることを示します。

1. bitをn回左シフトし(2^n)、その数ループを回す
2. ループ内でn回ループさせる（部分集合分）
3. bitが当てはまる部分の数値がそのループ内での部分集合

bitが当てはまる部分の数値を整理すると(bit & (1 << i))が0にならないiをseqに格納していくことから以下のようになります(0bは二進数表記)。

書き下してみるときれいに部分集合が列挙されています。すなわち、(bit & (1 << i))はbitが一致する場所は0以外になる、ということです。

実装

nim

import sequtils

let n = 3

# {0, 1, ..., n-1}の部分集合を全探索
for bit in 0..<(1 shl n):
  var vec = newSeq[int]()
    for i in 0..<n:
      if (bit and (1 shl i)) != 0:
        vec.add(i)
  echo bit, " : ", vec