bit全探索の基本

bit全探索とは、bit(0,1)の演算を用いて、選択のパターンを全て探索するアルゴリズムのことであり、以下のような用途で利用できます。

• N個の要素からなる集合の部分集合をすべて探索
• 「YES」、「NO」等の2パターンの選択肢がN個ある場合に、選択のすべてのパターンを探索

上記の用途はどちらも同じことをさしており、例えば、「N個の要素からなる集合の部分集合をすべて探索」は、「N個の各要素を「選ぶ」か「選ばない」の2パターンの選択の組み合わせをすべて探索」するということと同義です。

bit全探索の考え方

#

2パターンの選択を2進数の桁が0か1かで表します。 例えば、1を「選択」、0を「未選択」として、3匹の動物(犬、猫、鳥)がいる場合、各動物を選択したいとします。 犬を一番左の桁、猫を中央の桁、鳥を一番右の桁に対応させると、2進数では、犬と鳥を選ぶ場合を101と書けます。また、猫だけなら010と。このように選択するパターンを2進数で、すべて書きわけることができます。

今回は以下のように書き分けることができます。(◯が「選択」、×が「未選択」)

このように全ての選択を2進数で表現でき、上記は簡単なアルゴリズムでコーディングできます。

bit全探索の使いどころ

#

使いどころとしては、「2通りの選択肢がN個ある場合に全てのパターン探索」する場合であります。他の書き方でも実現できますが、bit全探索はコードが簡潔で分かりやすいので、bit全探索を選択します。 注意点としては、計算量が \(N * 2^N\) になるため、Nが多くなると計算時間が膨大となります。

bit全探索の実装

#

bit全探索をPythonで実装してみます。 今回は、以下のような集合からすべての組み合わせ(部分集合)を出力する。つまり各要素ごとに「選択」もしくは「未選択」をした場合の全ての組み合わせを出力します。

sample_list = ['A', 'B', 'C', 'D']

なお、上記は、要素数が4なので、 \(2^4 = 16\)通りの部分集合ができます。

実際のコードは以下の通りです。簡単な解説はコード中にあります。

sample_list = ['A', 'B', 'C', 'D']

## 要素数をカウント
len_sample_list = len(sample_list)

## 2 ** len_sample_listで選択する全パターンを探索
for i in range(2 ** len_sample_list):
    out_list = []
    ## どの桁が1になっているかをチェックするために2進数の各桁をループ
    for j in range(len_sample_list):
        ## i >> jで確認したい桁を一番右までずらして1と論理積をとって「選択」している要素を確認
        if (i >> j) & 1:
            out_list.append(sample_list[j])
    print(out_list)