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

TL;DR

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

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

bit全探索のアルゴリズム

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

演算名	演算子	説明	例
bitごとのAND	&	共に1のところだけが1になる	0b0101 & 0b0011 = 0b0001
bitごとの左シフト	<<	2倍	0b01011 << 1 = 0b10110

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

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

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

bit	bit(0b)	i=0(0b)	bit&i	i=1(0b)	bit&i(0b)	i=2(0b)	bit&2	array
0	0000	0001	0	0010	0	0100	0	()
1	0001	0001	1	0010	0	0100	0	(0)
2	0010	0001	0	0010	2	0100	0	(1)
3	0011	0001	1	0010	2	0100	0	(0,1)
4	0100	0001	0	0010	0	0100	4	(2)
5	0101	0001	1	0010	0	0100	4	(0,2)
6	0110	0001	0	0010	2	0100	4	(1,2)
7	0111	0001	1	0010	2	0100	4	(0,1,2)

実装

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