bit全探索とは

「n 個の選択肢それぞれに Yes or No の二択があるが、その部分集合（選択できるパターン）の全てを網羅的にチェックしたい」といった場合に使えます。Yes or No の二択が n 箇所あるので、パターン数は $2^n$ になります。（何も選ばないという選択肢もパターンに含まれます）

この選択肢の1つ1つを2進数の bit に見立ててシフト演算でチェックを行うことから「bit 全探索」とも呼ばれますが、やっていることは単なる全探索です。

例題 1

みかん（100円）りんご（200円）ぶどう（300円）がそれぞれ1つずつ果物屋さんにありました。財布の中には300円ありますが、考え得るすべての買い物パターンを列挙しなさい。

全ての買い物パターンで合計金額を計算し、その中から300円以下で済んだものを列挙すればよさそうです。全部で $2^3=8$ パターンとなりますので、基本的にはこれで for ループを回してチェックを行います。（「何も買わない」「み」「り」「ぶ」「み＋り」「み＋ぶ」「り＋ぶ」「み＋り＋ぶ」の8通りです）

main.py

money = 300
item = (("みかん", 100), ("りんご", 200), ("ぶどう", 300))
n = len(item)
for i in range(2 ** n):
    # ここで必要なチェックを行う

ここで各アイテムを買う / 買わないを「2 進数のそれぞれの桁が 0 であるのか 1 であるのか（左から順に、みかん、りんご、ぶどう）」で表現してみると以下の表のようになり、i = 0 から i = 7 までの間にきちんと全チェックできそうなことが分かります。

10進数表記	2進数表記	買い物リスト
0	000	（何も買わない）
1	001	ぶどう
2	010	りんご
3	011	りんご＋ぶどう
4	100	みかん
5	101	みかん　　　　＋ぶどう
6	110	みかん＋りんご
7	111	みかん＋りんご＋ぶどう

では、たとえば i = 5 の時にそれが「みかん＋ぶどう」であることをどうやって判別すればいいでしょうか。「2 進数表記のそれぞれの桁が 0 であるか 1 であるか」がどのアイテムを購入したかを表すフラグになっていますのでこれをチェックすれば良さそうです。

2 進数表記した場合の下から数えて n 桁目（一番下の桁を 0 とします）が 1 であるかどうかをチェックするためのコードは、(i >> n) & 1 です。これは「i を n 回右にシフトして 1 と論理積を取る（最下位の桁が 1 であるかどうかチェックする）」ということになります。

>>> i = 5
>>> bin(i)
'0b101'  # 5 を 2 進数で表記すると 101
>>> bin(i >> 2)
'0b1'  # 5 を 2 回右にシフトすると 001
>>> print((i >> 2) & 1)
1  # 5 を 2 回右にシフトしたものと 1 の論理積は 1 (=True)

下から 0 桁目が 1 であればぶどう入り、下から 1 桁目が 1 であればりんご入り、下から 2 桁目が 2 であればみかん入りということになりますので、最初のコードにこのチェックを加えてみます。

main.py

money = 300
item = (("みかん", 100), ("りんご", 200), ("ぶどう", 300))
n = len(item)
for i in range(2 ** n):
    bag = []
    print("pattern {}: ".format(i), end="")
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(item[j][0])  # フラグが立っていたら bag に果物を詰める
    print(bag)

出力結果は以下の通りで、どうやらうまくピックアップできた様子です。

pattern 0: []
pattern 1: ['みかん']
pattern 2: ['りんご']
pattern 3: ['みかん', 'りんご']
pattern 4: ['ぶどう']
pattern 5: ['みかん', 'ぶどう']
pattern 6: ['りんご', 'ぶどう']
pattern 7: ['みかん', 'りんご', 'ぶどう']

解答例

money = 300
item = (("みかん", 100), ("りんご", 200), ("ぶどう", 300))
n = len(item)
for i in range(2 ** n):
    bag = []
    total = 0
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(item[j][0])  # フラグが立っていたら bag に果物を詰める
            total += item[j][1]  # 買い物累計額にも加算
    if (total <= money):
        print(total, bag)

出力結果は以下の通りで、何も買わないという選択肢も含めると 5 パターンあるようでした。

0 []
100 ['みかん']
200 ['りんご']
300 ['みかん', 'りんご']
300 ['ぶどう']

例題 2：ABC 079 C Train Ticket

小学校時代にあった算数クイズ。$0;2;9;0$ といった数字同士の隙間に $+$ か $-$ を入れて特定の答え（今回の場合は $7$）を導き出すアレです。$0-2+9+0=7$ ・・・できた！という問題。

数字同士のすき間にためしに $+$ か $-$ を片っ端から入れてみて答えが導き出せるパターンを書き出せばよさそうです。「数字同士のすき間の個数分、二択（$+$ or $-$）が存在し、それらを全探索したい」ので bit全探索が使えます。

まずはためしにどんな選択肢があり得るのか全部書き出してみます。

main.py

n = [int(x) for x in input()]
op_cnt = len(n) - 1  # すき間の個数
for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt  # あらかじめ ["-", "-", "-"] というリストを作っておく
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き
    print(op)

入力した数字が 4 桁の場合（隙間は 3 つ）の出力は下記の通りになりますので、どうやらうまく列挙できているようです。

['-', '-', '-']
['-', '-', '+']
['-', '+', '-']
['-', '+', '+']
['+', '-', '-']
['+', '-', '+']
['+', '+', '-']
['+', '+', '+']

解答例

あとは数字の隙間にこれらの演算子を挿入して計算してみるだけですね。eval ってとても便利です。どなたか要素数の異なるリスト同士をスマートに互い違いマージする方法教えてください。

main.py

n = input()
op_cnt = len(n) - 1  # すき間の個数
for i in range(2 ** op_cnt):
    op = ["-"] * op_cnt  # あらかじめ ["-", "-", "-"] というリストを作っておく
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き

    formula = ""
    for p_n, p_o in zip(n, op + [""]):  # 少々モヤッとする
        formula += (p_n + p_o)
    if eval(formula) == 7:
        print(formula + "=7")
        break

計算量（loop数）について

選択肢が n 個ある場合のループの回数は $n*2^n$ 回となります。$n=3$ の場合はたかだか24回ですが、$n=10$ だと約1万回、$n=20$ だと約2,000万回ものループが回ることになります。

我が家のパソコンの場合、$n=20(\fallingdotseq10^7)$ で答えが返ってくるまでに約7秒ほどかかりましたので、$n=50(\fallingdotseq10^{16})$ だと計算が終わるまで約221年くらいかかりそうです（笑）

$2^n$ アルゴリズムは意外とすぐに計算量の爆発が起きますので、選択肢の制約条件には十分気を付けてご利用ください。