pythonで部分集合を探索する方法3選

前回の再帰に関する記事で組み合わせの列挙を扱いました．他の方法でも解いたみたいと考え，今回の記事を作成するに至りました．

目次

部分集合の問題って何？

部分集合を扱った問題がどのような問題なのかをまず解説していきます． 問題
n個の要素を持つ配列Aの要素を0個以上足し合わせることで作ることのできる整数を全て列挙してください．

このような問題があった時考えなければいけないのが足し合わせることのできる全ての配列要素の組み合わせを列挙し，それらの組み合わせを計算し，出力するということが考えられると思います．
このような組み合わせの列挙には配列の中の要素を選択するか，しないかという処理を全ての要素に行い，組み合わせを作ることでできます．
今回はこういった場合の組み合わせの列挙を3つの方法で作っていきたいと思います．
最後にはこういった組み合わせを使った問題を実際に解いてみたいと思います．
まずは選択する(1), しない(0)のリストをそれぞれの方法で作っていきます.

再帰関数を使った方法

まず，一つ目が自分で組み合わせを作り上げていくプログラムになります．再帰関数を用いて実際に自分で作るので実装力は身につくかもしれませんが，競技プログラミングなどではコードを書く速度を求められるのであまりお勧めはできません．
勉強がてら作ってみたいという人は挑戦してみてください.

def comb(i, A, ans):
    if i == n:
        ans.append(list(A)) 
        return
    
    comb(i+1, A, ans)
    A[i] = 1 
    comb(i+1, A, ans)
    A[i] = 0

n = 5
A = [0]*n
ans = []
comb(0, A, ans)
print(ans)

出力

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

itertoolsを使った方法

二つ目が，itertoolsを用いた方法です．pythonの標準ライブラリの一つで効率的なループ処理を行ってくれます．
よく使うものとしては順列(n!)，組み合わせの数(nCr)がありますが，その他にもたくさんのことができるので気になる方はこちらから確認してみてください．
今回のような問題に使えるのがこのitertoolsの中の"product"になります．
上記で作成したような配列を一瞬で作ることができます．
出力に関しては似たような形なので省略します．

import itertools
n = 5
print(list(itertools.product(range(2), repeat = n)))

bitを使った方法

三つ目が，二進数(bit)を用いた方法です．bitでこのような組み合わせを探索することをbit全探索というような呼び方をしたりします．
整数を2進数表記に変えてくれるpythonの組み込み関数binを用いることでbitの文字列を作ることができます．
今回の組み合わせは選択するかしないか，つまり，0と1で表現できます．
この特性を生かして全組み合わせをbitで表現することができます．
bin()では先頭に "0b" が付いた形で出力されるのでそこだけ注意しましょう.

n = 5
ans = []
for i in range(2**n):
    ans.append(bin(i)[2:].zfill(n))
print(ans)

これら三つの方法それぞれ出力の形式がリスト，タプル，文字列と異なりますが，似たような処理で扱うことができるので探索方法として紹介しました．
最後にどういった問題を解くことができるのか実際に解くことで解説していきたいと思います.

実践編

今回はAtCoderの問題:C-たくさんの数式を使っていきたいと思います．
問題文
1 以上 9 以下の数字のみからなる文字列Sが与えられます． この文字列の中で,あなたはこれら文字と文字の間のうち,いくつかの場所に + を入れることができます.一つも入れなくてもかまいません. ただし,+ が連続してはいけません.
このようにして出来る全ての文字列を数式とみなし,和を計算することができます.
ありうる全ての数式の値を計算し,その合計を出力してください.

制約
1≤|S|≤10
Sに含まれる文字は全て 1 〜 9 の数字

解答コード

S =input()
ans_list = []
if len(S) == 1:
    print(int(S))
else:
    for i in range(2**(len(S)-1)):
        comb = bin(i)[2:].zfill(len(S)-1)
        num_list = []
        num = S[0]
        for i in range(len(comb)):
            if comb[i] == "1":
                num_list.append(int(num))
                num = S[i+1]
            else:
                num += S[i+1]
        num_list.append(int(num))
        ans_list.append(sum(num_list))
    print(sum(ans_list))

今回扱った問題では入力Sの間に"+"を入れるかどうかという組み合わせを列挙し，実際にその組み合わせによってできた数式を計算することで答えにたどり着くことができると思います．
ビットシフトの考え方を使うことでもっとコードを短く書くこともできますが，直感的な理解のためにこのような形で書いてみました．
コードを順番にさらっていけば理解できると思うのでもし扱った問題が解けなければ上記のコードを参考にしてみてください.
また，zfill()はゼロ埋めのことで
例えば，("1").zfill(3)としたら"001"となります．このように指定した文字列の長さにするために左側に0を埋めてくれます．

今回は部分集合をpythonでどう作るかということを解説してきました．
こんな方法が他にもあるよだったり，もっとこうした方が簡単だよというようなことがありましたら，コメントよろしくお願いします．