メインコンテンツまでスキップ

全探索: ビットで全パターンを試そう

ビット全探索は、選ぶ・選ばないを0と1で表し、すべての組み合わせを試す方法です。

3個の品物なら、各品物について「選ぶ」「選ばない」の2択があるので、全部で 2 × 2 × 2 = 8 通りです。

使いどころ​

  • 個数が少ないときの全パターン確認
  • 部分集合を作る問題
  • ナップサック問題の小さい版

手順​

  1. 0 から 2^n - 1 までの数を使う
  2. 各ビットを見る
  3. ビットが1ならその要素を選ぶ
  4. 作った組み合わせを調べる

図で見る​

コピペ用コード​

items = [3, 5, 8]

for bit in range(1 << len(items)):
    selected = []
    for i in range(len(items)):
        if bit & (1 << i):
            selected.append(items[i])
    print(selected)

コードの読み方​

  • 1 << len(items) は、2^n を表します。
  • bit & (1 << i) で、i 番目を選んでいるか判定します。
  • selected に、そのパターンで選んだ要素を入れています。

計算量​

ビット全探索の計算量は O(2^n × n) です（パターン数 × 各パターンの確認）。

nパターン数実行時間の目安
101,024一瞬
20約100万1秒前後
25約3,300万数十秒（きびしい）
40約1兆不可能 → 半分全列挙

「n が 20 以下なら全部試せる」が目安です。

別パターン1: 合計がちょうど target になる選び方を探す​

「いくつかの数を選んで合計をぴったり作れるか」という典型問題です。

items = [3, 5, 8, 10]
target = 13

for bit in range(1 << len(items)):
    total = 0
    selected = []
    for i in range(len(items)):
        if bit & (1 << i):
            total += items[i]
            selected.append(items[i])

    if total == target:
        print(f"見つかった: {selected}")  # [5, 8] と [3, 10]
  • 全パターンを試すので、「見つからない＝存在しない」と断言できるのが全探索の強みです。
  • 答えを1つ見つけて終わりたいときは、print の後に break を入れます。

別パターン2: itertools で同じことをする​

Python では itertools.product や combinations でも全パターンを作れます。ビット演算に慣れないうちは、こちらの方が読みやすいかもしれません。

from itertools import product

items = [3, 5, 8, 10]
target = 13

# 各要素について (選ばない, 選ぶ) = (0, 1) の全組み合わせ
for pattern in product([0, 1], repeat=len(items)):
    selected = [item for item, use in zip(items, pattern) if use]
    if sum(selected) == target:
        print(selected)
  • product([0, 1], repeat=4) は (0,0,0,0) から (1,1,1,1) までの16通りを順に返します。
  • zip(items, pattern) で「要素」と「選ぶかどうか」をペアにしています。
  • 動きはビット全探索と同じです。書き方の好みで選んで構いません。

ビット演算の早見表​

ビット全探索で使う演算をまとめます。

書き方意味例
1 << n2^n1 << 3 は 8
bit & (1 << i)i 番目のビットが立っているか0以外なら立っている
bit | (1 << i)i 番目のビットを立てる集合に i を追加
bin(bit)2進数の文字列で確認bin(5) は '0b101'
bin(bit).count("1")立っているビットの数選んだ個数

よくあるミス​

ミス何が起きるか対処
range(1 << n) を range(2 * n) と書くパターンが全然足りない2^n は 1 << n
bit & (1 << i) == 1 と比較するi > 0 で常に False（結果は 2^i）!= 0 判定か、そのまま if に渡す
n が大きいのに使う終わらないn > 20 なら動的計画法や半分全列挙を検討

注意点​

要素数が増えるとパターン数が一気に増えます。20個を超えるとかなり重くなることがあります。

AOJで挑戦してみよう！​

学んだレシピを実際に使って、ジャッジから「Accepted（正解）」を勝ち取ろう！

ALDS1_5_A: Exhaustive Search