ビット全探索 - Truly the knowledge base

ビット全探索

$ N個の要素を持つ配列の要素を選択する、あるいは選択しないことを、ビット列を生成することによって行う形式の全探索。

時間計算量は$ O(2 ^ N)であるため、$ N < 20 ほどなら現実的な時間で探索できる。それ以上の高速化には、動的計画法（Dynamic Programming）を適用することができる。

部分和問題などに適用できる。

再帰関数を用いて探索する方法もある。

ビット列を用いて探索する方法

code:bit.py

for i in range(1 << N):

pass # ここに初期化の処理を書く

for j in range(N):

bit = (i >> j) & 1

if bit:

# 組み合わせ検索時の処理

else:

# 組み合わせを検索し終わった時の処理

continue

itertools.product を使う方法

code:python

for selectors in itertools.product(range(2), repeat=N):

for j in range(N):

pass

itertools.combinations を使う方法

$ N個の要素からなる配列の中から $ r （ただし、$ 0 \leq r \leq N）個取り出す組みあわせを全部試すことと言い換えることができるので、以下の処理を用いることもできる。

code:combinations.py

for r in range(N + 1):

for _ in itertools.combinations(iterable, r):

pass # ここに初期化の処理を書く

for i in _:

# 組み合わせ検索時の処理

else:

# 組み合わせを検索し終わった時の処理

continue

Bit全探索のベンチマーク