【部分集合全列挙】~ bit全探索 ~

はじめに

今回は部分集合の全列挙について考えます！
競技プログラミングで出た時に、実装を忘れることがあるので改めて確認します。便利なライブラリがあるので、基礎を理解した上で省エネ実装もしてみます！

やりたいこと

配列を与えられた時に、全ての部分集合を列挙したい。
それぞれの要素に対して「選ぶ」と「選ばない」の２通りがあるので、全体としては$2^n$通りになります。

具体例

li = [1,2,3]
n = len(li) # n = 3

要素数３の配列を用意しました。
これを使って実装を考えてみます！

実装（手書き）

L = []
for bit in range(1 << n):
    li = []
    for i in range(n):
        if bit & (1 << i): li.append(1)
        else: li.append(0)
    L.append(li)
print(L)

出力

[[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]]

bit全探索を実装しています。これは、数を２進数と見てAND演算を考えるものです。
ex) 1 -> 001, 2 -> 010, 3 -> 011, 4 -> 100, ...
こうしていくと、綺麗に全パターンの$2^n$通りを挙げることができます。

実装（ライブラリ）

from itertools import product

L = list(product([0,1],repeat=3))
print(L)

出力

[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

ライブラリを使用して実装しています。
直積を考えることで列挙ができます。

最後に

全探索をするための基本的なbit全探索を改めて確認しました。
個人的に覚えづらかったので、何のために何をしているか、を整理することができてよかったです。

最後まで読んでいただきありがとうございました！

参考文献

https://docs.python.org/ja/3.13/library/itertools.html