この記事では、bit全探索で選んだり選ばなかったりするもののことを「対象」と呼びます。
背景
bit演算を用いたbit全探索は実装が少し重めで、コードからその意味を読み取りづらいです。この記事では、bit全探索で頭を悩ませた方々に対して、解釈一つである「bitの直積集合」について紹介します。
急いでいる人向け
from itertools import product
# 例: 数列Aから1つ以上いくつか選んだとき、その和が3で割り切れるものがあるかどうかを判定。
A = [1, 4, 13, 34]
n = len(A)
for bits in product([0, 1], repeat=n):
print("bits: ", bits)
a = [x for bit, x in zip(bits, A) if bit == 1]
if not a: continue
print("選んだもの: ", a)
print("和: ", sum(a))
if sum(a) % 3 == 0:
print("Yes")
exit()
# bits: (0, 0, 0, 0)
# bits: (0, 0, 0, 1)
# 選んだもの: [34]
# 和: 34
# bits: (0, 0, 1, 0)
# 選んだもの: [13]
# 和: 13
# bits: (0, 0, 1, 1)
# 選んだもの: [13, 34]
# 和: 47
# bits: (0, 1, 0, 0)
# 選んだもの: [4]
# 和: 4
# bits: (0, 1, 0, 1)
# 選んだもの: [4, 34]
# 和: 38
# bits: (0, 1, 1, 0)
# 選んだもの: [4, 13]
# 和: 17
# bits: (0, 1, 1, 1)
# 選んだもの: [4, 13, 34]
# 和: 51
# Yes
5分で理解できる解説
bit全探索は下記のような方法でも実現できます。
選ぶ対象が$\{0, 1\}$という「bit集合」を持っているとします。
選ぶ対象が複数あるとき、それぞれの「bit集合」の直積(後述)を取ると、対象の選ぶ選ばないの組み合わせの全パターンを取得することができます。
上記の例は、下記コードの別の書き方となります。
from itertools import product
# 例: 数列Aから1つ以上いくつか選んだとき、その和が3で割り切れるものがあるかどうかを判定。
A = [1, 4, 13, 34]
one = [0, 1]
four = [0, 1]
thirteen = [0, 1]
thirtyfour = [0, 1]
for bits in product(one, four, thirteen, thirtyfour):
print("bits: ", bits)
a = [x for bit, x in zip(bits, A) if bit == 1]
if not a: continue
print("選んだもの: ", a)
print("和: ", sum(a))
if sum(a) % 3 == 0:
print("Yes")
exit()
product(直積を取りたい複数の集合)というのが直積集合の要素を列挙する関数です。
直積集合とは、複数の集合に対してそれぞれの要素を一つずつ取り出して組とするときの全パターンを集めたものです。
product関数は、例えば以下のように使えます(トランプの例)。
from itertools import product
suit = ["♥", "♦", "♤", "♧"]
rank = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"]
for card in product(suit, rank):
print("".join(card))
# ♥A
# ♥2
# ♥3
# ...
# ♥J
# ♥Q
# ♥K
# ♦A
# ♦2
# ♦3
# ...
# ♦J
# ♦Q
# ♦K
# ♤A
# ♤2
# ♤3
# ...
# ♤J
# ♤Q
# ♤K
# ♧A
# ♧2
# ♧3
# ...
# ♧J
# ♧Q
# ♧K
最初の例に戻ります。one, four, thirteen, thirtyfourはすべて[0, 1]なので、product関数の引数repeatを利用することができます。
from itertools import product
# ...(略)
one = [0, 1]
four = [0, 1]
thirteen = [0, 1]
thirtyfour = [0, 1]
for bits in product(one, four, thirteen, thirtyfour):
↓
from itertools import product
# ...(略)
for bits in product([0, 1], repeat=4):
from itertools import productを忘れないようにしましょう。
以上、簡単な解説です。
以下、詳しい解説となります。
bitで組み合わせを表現
ある集合をbitで表現し、対象を選ぶ場合を1、選ばない場合を0とすれば、組み合わせを表現することができます。
組み合わせ例: A～Fから、B, C, Eを選ぶ。
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
bit全探索とは、bitで「選ぶ」「選ばない」を表現し、その組み合わせの全パターンを列挙し、探索する方法のことでした。
直積集合
直積集合とは、複数の集合に対して要素を一つずつ取り出して組とするときの、その全パターンを集めた集合です。
具体例としては、トランプの例がわかりやすいです。
トランプは数の集合(A, 2, 3 ... 10, J, Q, K)とマークの集合(♡, ♢, ♤, ♧)の直積集合です。
| ♥ | ♦ | ♤ | ♧ | |
|---|---|---|---|---|
| A | ♥A | ♦A | ♤A | ♧A |
| 2 | ♥2 | ♦2 | ♤2 | ♧2 |
| ... | ... | ... | ... | |
| K | ♥K | ♦K | ♤K | ♧K |
以降、集合$A$と集合$B$があるとして、その直積集合を$A×B$というように表記します。
例えばトランプは、数の集合$Rank$ とマークの集合$Suit$ の直積集合$Rank × Suit$です。
bit全探索と直積集合
直積集合でbitによる組み合わせを表現します。
まずは二つの対象の選び方を考えてみます。
二つの対象AとBを選ぶ組み合わせは、「二つとも選ばない」「Aだけ選ぶ」「Bだけ選ぶ」「二つとも選ぶ」の4パターンあります。
bitで表現するとしたら以下の表のようになります。
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
例えば組の順番を(A, B)とし、bitが(1, 0)なら「Aを選び、Bを選ばない」ということです。
ここで、対象Aには「選ぶ(= 1)」「選ばない(= 0)」という二つの要素を持つ集合$A = \{0, 1\}$、対象Bにも「選ぶ」「選ばない」という二つの要素を持つ集合$B = \{0, 1\}$があると言えます。
そうしたとき、対象A(= $\{0, 1\}$)と対象B(= $\{0, 1\}$)を選ぶ組み合わせの全パターンは、直積集合
$\{0, 1\} × \{0, 1\}(= \{(0, 0), (0, 1), (1, 0), (1, 1)\})$
で表すことができます。
続いて、対象を三つ以上に広げてみます。
まず、直積集合は三つ以上の集合でも作ることができます。直積集合は複数の集合に対して要素を一つずつ取り出して組とするときの、その全パターンを集めた集合ということなので、三つ以上の集合でも問題なく直積集合を作れます。
先ほど直積集合を二次元の表にしてしまったため混乱すると思いますので、三つ以上でも大丈夫であると納得できるように説明します。集合$A$, 集合$B$, 集合$C$があるとして、その直積集合$A×B×C$をあらわします。
まず、集合$A$, 集合$B$の直積集合$A × B$を$P$とします。直積集合$P$は集合ですので、もちろん他の集合と直積集合を取ることができます。
集合$P$と集合$C$の直積集合、$P × C$は二次元の表であらわすことができます。
具体例として、対象A, B, Cを選び方を表にしてみます。それぞれ「選ぶ(= 1)」「選ばない(= 0)」の二つの要素を持つ集合を持っています。
まずは$P = A × B$を求めます。
これは先ほど表であらわしました。
| A\B | 0 | 1 |
|---|---|---|
| 0 | (0, 0) | (0, 1) |
| 1 | (1, 0) | (1, 1) |
つまり、$P = \{(0, 0), (0, 1), (1, 0), (1, 1)\}$です。
続いて$P × C$は以下のような表であらわせます。
| P\C | 0 | 1 |
|---|---|---|
| (0, 0) | (0, 0, 0) | (0, 0, 1) |
| (0, 1) | (0, 1, 0) | (0, 1, 1) |
| (1, 0) | (1, 0, 0) | (1, 0, 1) |
| (1, 1) | (1, 1, 0) | (1, 1, 1) |
(※ $P × C$は本来は、((0, 0), 0)のようになりそうですが、((x, y), z)と(x, y, z)の対応は全単射なので気にしない方向でいきます。。。)
これで三つ以上の集合について直積集合を取れることに納得がいったと思います。もちろん、$\{「選ぶ」「選ばない」\}$というような集合を持つ対象についても同様です。
例:
対象 A～Fを選ぶ組み合わせの全パターンは
- $A = \{0, 1\}$
- $B = \{0, 1\}$
- $C = \{0, 1\}$
- $D = \{0, 1\}$
- $E = \{0, 1\}$
- $F = \{0, 1\}$
の直積集合、$A×B×C×D×E×F$で表すことができます。
Pythonによる実装
Pythonには、標準ライブラリに直積集合を生成する関数があります。itertoolsモジュールのproduct関数がそれにあたります。
以下はA～Fを選ぶ組み合わせ全パターンを列挙し、出力する実装です。
from itertools import product
items = ["A", "B", "C", "D", "E", "F"]
A = [0, 1]
B = [0, 1]
C = [0, 1]
D = [0, 1]
E = [0, 1]
F = [0, 1]
for bits in product(A, B, C, D, E, F):
comb = [x for x, bit in zip(items, bits) if bit == 1]
print(comb)
[]
['F']
['E']
['E', 'F']
['D']
['D', 'F']
['D', 'E']
['D', 'E', 'F']
...(省略)...
['A', 'B', 'C']
['A', 'B', 'C', 'F']
['A', 'B', 'C', 'E']
['A', 'B', 'C', 'E', 'F']
['A', 'B', 'C', 'D']
['A', 'B', 'C', 'D', 'F']
['A', 'B', 'C', 'D', 'E']
['A', 'B', 'C', 'D', 'E', 'F']
集合$\{0, 1\}$の直積集合であることに注意してください。
この実装ではA～Fの「選ぶ」「選ばない」の集合$\{0, 1\}$をそれぞれ用意していますが、全て$\{0, 1\}$と、同じですのでproduct関数のキーワード引数repeatを使えばより簡潔になります。
from itertools import product
items = ["A", "B", "C", "D", "E", "F"]
n = len(items)
for bits in product([0, 1], repeat=n):
comb = [x for x, bit in zip(items, bits) if bit == 1]
print(comb)
出力結果は上記と同じです。
まとめ
- bit全探索とは、各対象の「選ぶ」「選ばない」の全パターンを集めたもの
- 直積集合とは、二つ以上の集合から要素を一つずつ取り出し、その組の全パターンを集めたもの
- bit全探索において、対象は「選ぶ」「選ばない」という要素を持つ集合を持っている。
- 全対象の$\{「選ぶ」, 「選ばない」\}$という集合の直積集合をとれば、各対象の「選ぶ」「選ばない」の全パターンを集めたものになる。(= それを使えばbit全探索ができる)