bit全探索の基本

この記事では、アルゴリズムのbit全探索についてまとめます。 なお、書き慣れているPythonで解説・実装をしていきます。

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)

終わりに

今回はbit全探索について簡単にまとめました。今後は他のアルゴリズムに関しても順次まとめていきます。