背景
bit演算を用いたbit全探索は実装が少し重めで、コードからその意味を読みづらいです。この記事では、bit全探索で頭を悩ませた方々に対して解釈一つである「べき集合」について紹介します。
急いでいる人向け
from itertools import combinations
# 例: 数列Aから1つ以上いくつか選んだとき、その和が3で割り切れるものがあるかどうかを判定。
A = [1, 4, 13, 34]
n = len(A)
for k in range(n+1):
for comb in combinations(A, k):
print(comb)
print(sum(comb))
if sum(comb) % 3 == 0:
print("Yes")
exit()
# (1,)
# 1
# (4,)
# 4
# (13,)
# 13
# (34,)
# 34
# (1, 4)
# 5
# (1, 13)
# 14
# (1, 34)
# 35
# (4, 13)
# 17
# (4, 34)
# 38
# (13, 34)
# 47
# (1, 4, 13)
# 18
# Yes
3分で理解できる解説
bit全探索はn個要素を持つ列から0個選ぶ, 1個選ぶ, 2個選ぶ, ..., n個選ぶ場合の全パターンを探索するアルゴリズムと解釈できます。
そのため、0, 1, 2, ..., nをループし、ループ変数をkとしたとき、k個を選ぶ場合の組み合わせを列挙するとbit全探索としてやりたいことは実現できます。
上記コードの下記部分がそれを実現する箇所になります。
from itertools import combinations
# ...(略)
for k in range(n+1):
for comb in combinations(A, k):
combinations(列, 選ぶ個数)というのが、列からある個数を選ぶ場合の組み合わせを列挙する関数です。
例えば、以下のような列挙ができます。
from itertools import combinations
A = [1, 2, 3, 4, 5]
# Aから3個選ぶ組み合わせを列挙
for comb in combinations(A, 3):
print(comb)
# (1, 2, 3)
# (1, 2, 4)
# (1, 2, 5)
# (1, 3, 4)
# (1, 3, 5)
# (1, 4, 5)
# (2, 3, 4)
# (2, 3, 5)
# (2, 4, 5)
# (3, 4, 5)
from itertools import combinationsを忘れないようにしましょう。
以上、簡単な解説です。
以下、詳しい解説となります。
bitで組み合わせを表現
ある集合をbitで表現し、ある要素を選ぶ場合を1、選ばない場合を0とすれば、組み合わせを表現することができます。
組み合わせ例: A～Fから、B, C, Eを選ぶ
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
この表で1としたものを集めたものは、もとの集合の部分集合となります。
bit全探索は、二進法のように順番に組み合わせを探索していくものでした。
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
...
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 1 | 0 |
...
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
べき集合
冪集合（べきしゅうごう、英: power set）とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。
先ほど、表で1としたものを集めたものは、もとの集合の部分集合となると述べました。
上記で列挙した表を眺めて見ると、まんべんなく部分集合を列挙していると言えるでしょう。
つまり、部分集合の全体を表しているということであり、bit全探索として挙げた上記列挙表の集まりはまさにべき集合だと解釈できます。
べき集合を作るもう一つの方法
上記列挙表を並び替えてみます。
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
...
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 0 |
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 0 | 0 |
...
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
1の個数が少ない順に並べました。
この列挙からは、0個選ぶ場合の組み合わせ、1個選ぶ場合の組み合わせ、2個選ぶ場合の組み合わせ、...、n個選ぶ場合の組み合わせというようにグループ分けができそうです。
つまりべき集合の作り方について、以下のようにいうこともできます。
集合から0個選ぶ、 1個選ぶ、 2個選ぶ、 ...、 n個選ぶ場合の組み合わせ全パターンを集めるとべき集合となる。
Pythonのコードにすると、列からある個数選ぶ場合の組み合わせを列挙する関数combinationsを使って、べき集合の要素(部分集合)を列挙することができます。
まず、combinationsは例えば以下のような列挙ができます。
from itertools import combinations
A = [1, 2, 3, 4, 5]
# Aから3個選ぶ組み合わせを列挙
for comb in combinations(A, 3):
print(comb)
# (1, 2, 3)
# (1, 2, 4)
# (1, 2, 5)
# (1, 3, 4)
# (1, 3, 5)
# (1, 4, 5)
# (2, 3, 4)
# (2, 3, 5)
# (2, 4, 5)
# (3, 4, 5)
range関数で0~nを選ぶ個数とすれば、combinationsでべき集合の要素を列挙できます。
from itertools import combinations
S = ["A", "B", "C", "D", "E", "F"]
n = len(S)
for k in range(n+1):
for comb in combinations(S, k):
print(comb)
# ()
# ('A',)
# ('B',)
# ('C',)
# ...
# ('F',)
# ('A', 'B')
# ('A', 'C')
# ('A', 'D')
# ...
# ('A', 'B', 'C', 'D', 'E', 'F')
まとめ
- 組み合わせとしてbitで1としたものを集めると、もとの集合の部分集合となる。
- bit全探索はもとの集合の部分集合全体を探索するもの。
- bit全探索で列挙したものを並び替えると、0個選ぶ、 1個選ぶ、2個選ぶ、...、n個選ぶ場合の組み合わせ全パターンを列挙したものともいえる。
- Pythonではrangeとcombinationsを使って下記のように実現できる
from itertools import combinations
S = ["A", "B", "C", "D", "E", "F"]
n = len(S)
for k in range(n+1):
for comb in combinations(S, k):
print(comb)
注意
実際は、bit演算を使う全探索のほうが計算が最適化されているため、そちらのほうでも実装できるようにしておいたほうが良いです。こちらの記事ではあくまで、別の解釈を知ることで理解を深めるものとなります。