ビット全探索
1. ビット全探索とは
集合の全部分集合を探索する方法
使う/使わないの全探索で制約が小さかったらbit全探索を検討する
集合の要素数を$ nとすると，部分集合は全部で$ 2^n個存在する．
２進数を用いる
2. ２進数の基本
(1) 文字列を2進数として読み込み
文字列を整数に変換するint関数に第2引数を指定する．
code: python
a = int('11', 2) # intの第2引数で指定
print(a) # 3
(2) 整数を2進数として表示
f文字列で，フォーマットでb指定．
code: python
a, b = 12, 3
print(f'{a:b}') # 1100．b指定で2進数表示
print(f'{b:04b}') # 0011. 04bで4桁指定
(3) 論理演算
排他的論理和は，2つが同じなら0，異なれば1．意外によく使う．
code: python
a, b = 12, 10 # 1100, 1010
print(f'{a & b:04b}') # 論理積．1000
print(f'{a | b:04b}') # 論理和．1110
print(f'{a ^ b:04b}') # 排他的論理和．0110
(4) シフト演算
左に1ビットシフト → 2倍．一番右（最下位ビット）に0を付けるイメージ
右に1ビットシフト → 1/2倍．一番右（最下位ビット）を削除するイメージ
code: python
a = 12 # 1100
print(f'{a << 1:04b}') # 11000．10進数では24
print(f'{a >> 1:04b}') # 110． 10進数では6
3. 部分集合と2進数
(1) 基本的な考え方
大きさ$ nの集合$ S=\{e_0,\ e_1,\ \dots ,\ e_{n-1}\}の部分集合を考える．
各要素は部分集合に「含まれる」or「含まれない」の2択なので，部分集合は$ nビット列で表せる．
後の都合上，要素$ e_iの0/1を下位$ iビットで表す．一番右のビットが最初の要素の状態を表す．
例）$ S=\{e_0,\ e_1,\ e_2\}の部分集合$ S'：
$ S' =\phiのとき，000
$ S' =\{e_0\}のとき，001
$ S' =\{e_1\}のとき，010
$ S' =\{e_2\}のとき，100
$ S' =\{e_0,\ e_1\}のとき，011
$ S' =\{e_0,e_2\}のとき，101
$ S' =\{e_1,\ e_2\}のとき，110
$ S' =\{e_0,\ e_1,\ e_2\}のとき，111
上の例では，要素数3の集合の全部分集合が，000から111までの8つの3ビット列で表現される．
3ビット列を10進数に変換すれば，要素数3の集合の全部分集合が，0から7までの整数で表現される．
一般に，要素数$ nの集合の全部分集合は，0から$ 2^n - 1で表現できる．1 << nが$ 2^nになるので，0から$ 2^n - 1までの範囲はrange(1 << n)．
(2) 整数$ sが表す集合に属する要素の抽出
$ n = 3,\ s = 5のとき，整数$ sの2進数は101なので，$ S' =\{e_0,e_2\}． これをプログラムで実装する方法は？
数学的に考えれば，次のようになる．
$ 5 = 2^2\times1\ +\ 2^1\times0\ + 2^0\times1なので，$ 2^iで割ったときの余りを確認する
code: python
s, n = 5, 3
ans = []
for i in range(n):
if s % 2: # s % 2 == 1でも可
ans.append(i)
s //= 2 # s >>= 1 でも可
print(*ans) # 0 2
$ sのビットを考えれば，次のようにも書ける．
code: python
s, n = 5, 3
ans = []
for i in range(n):
if (s >> i) & 1: # iビット右にシフトして，最下位ビットのみ残す
ans.append(i)
print(*ans) # 0 2
4. コード例
(1) 部分集合をすべて探索し，部分集合の要素（文字列）をすべて連結
code: python
n = len(S)
for s in range(1 << n): # s = 0, 1, ..., 2^n - 1
sub = ''
for i in range(n):
if (s >> i) & 1: # 下からiビット目が1なら
print(s, sub)
# 0
# 1 0
# 2 1
# 3 01
# 4 2
# 5 02
# 6 12
# 7 012
(2) 部分集合をすべて探索し，部分集合の要素（集合）の和集合を表示
code: python
n = len(S)
for s in range(1 << n):
union_set = set()
for i in range(n):
if (s >> i) & 1:
print(s, union_set)
# 0 set()
# 1 {0, 1, 2}
# 2 {0, 2, 4}
# 3 {0, 1, 2, 4}
# 4 {2, 3, 4}
# 5 {0, 1, 2, 3, 4}
# 6 {0, 2, 3, 4}
# 7 {0, 1, 2, 3, 4}
5. （参考）itertoolsを使う方法
code: python
from itertools import product
n = len(S)
for pat in product(0, 1, repeat=n): # 直積．n個の0, 1から1つずつ選択する全組合せ sub = ''
for i in range(n):
print(pat, sub)
# (0, 0, 0)
# (0, 0, 1) 2
# (0, 1, 0) 1
# (0, 1, 1) 12
# (1, 0, 0) 0
# (1, 0, 1) 02
# (1, 1, 0) 01
# (1, 1, 1) 012
6. 練習問題