はじめに
Python 組合せ列挙などと検索すると、標準ライブラリitertoolsのpermutationsやcombinationsを使って実装している記事が多くでてきます。
しかしそんなものは甘えに過ぎません、$Pythonista$たるもの標準ライブラリくらい一度は自力で実装しておきたいものです。
※ライブラリの利用を否定しているわけではありません。
※むしろ、自力で実装するよりはライブラリの方が高速でしょうから、実際に運用するときは大人しくitertools使いましょう。
対象読者
「じゃあpermutations / combinationsの中身はどうなってるの？」と思ってるそこのあなた
いざ実装
再帰関数って？？
すごくわかりやすい記事があるのでそちらを参照してください。
順列(Permutations)
itertools.permutationsの中身を再現してみます。
プロセス
前提として、以下のような書き方を用います。
-
{要素1, 要素2, ...}：数字の組、順番は関係ない -
[要素1, 要素2, ...]：数字の順列、順番が関係ある -
([順列1], [順列2], ...)：求めた順列の組
それでは、{1, 2, 3}を用いた順列を全て生成する過程を順を追って考えてみましょう。
-
1から始まる順列を生成する-
1を除いた{2, 3}を用いた順列を生成する-
{2, 3}を用いて2から始まる順列を生成する- 残りの数字の組
{3}から順列を生成する- 順列の組
([3])を返す - 求めた順列の先頭にそれぞれ
2をくっつける - 順列の組
([2, 3])を返す
- 順列の組
- 残りの数字の組
-
{2, 3}を用いて3から始まる順列を生成する- 残りの数字の組
{2}から順列を生成する- 順列の組
([2])を返す
- 順列の組
- 求めた順列の先頭にそれぞれ
3をくっつける - 順列の組
([3, 2])を返す
- 残りの数字の組
- 順列の組
([2, 3], [3, 2])を返す
-
- 求めた順列の先頭にそれぞれ
1をくっつける - 順列の組
([1, 2, 3], [1, 3, 2])を返す
-
-
2から始まる順列を生成する- ...
-
3から始まる順列を生成する- ...
結果
(
[1, 2, 3], # 1から始まる順列
[1, 3, 2],
[2, 1, 3], # 2から始まる順列
[2, 3, 1],
[3, 1, 2], # 3から始まる順列
[3, 2, 1],
)
難しそうに見えますが、実は以下の3つの動作を繰り返しているだけなのです
- 数字の組から1つ取り出す
- 残りの数字の組から順列の組を作る
- 求まった順列の先頭に1.で取り出した数字をくっつける
ただし、1.で数字が1個しかないときは要素数1の順列を返します
要は、求める順列を小さい単位に分割して求めていく感じですね。
コード
実際にはこうやって実装しています。
def permutations(my_list):
if len(my_list) == 1:
return [my_list] # 1. 要素数1の順列を返す
else:
result = [] # 順列の組を保存しておくためのリスト
for i, val in enumerate(my_list): # 1. 数字の組から1つ取り出す
rest = permutations(my_list[:i] + my_list[i+1:]) # 2. 残りの数字の組から順列の組を作る
for rest_perm in rest:
perm = [val] + rest_perm # 3. 求まった順列の先頭に1で取り出した数字をくっつける
result.append(perm)
return result # 順列の組を返す
実行結果
if __name__ == "__main__":
my_list = [1, 2, 3]
perms = permutations(my_list)
print(perms)
### 出力 ###
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
また、n個の要素からr個取り出したいという場合は、このような実装になります。
def permutations(my_list, r=None):
if r == None: # rが設定されていないときはmy_listの要素数に初期化
r = len(my_list)
if r == 1:
return [[val] for val in my_list] # my_listを要素数1の順列の組にする
else:
result = []
for i, val in enumerate(my_list):
rest = permutations(my_list[:i] + my_list[i+1:], r-1) # 取り出す数を1つ減らす
for rest_perm in rest:
perm = [val] + rest_perm
result.append(perm)
return result
実行結果
if __name__ == "__main__":
my_list = [1, 2, 3, 4]
perm = permutations(my_list, 2)
print(perm)
### 出力 ###
[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]
また、itertools.permutationsはジェネレータ1ですので、こんな実装になってるはずです。yieldの仕組みはこちらのリンク2などを参照してみてください。
def permutations_generator(my_list, r=None):
if r == None:
r = len(my_list)
if r == 1:
for val in my_list:
yield [val]
else:
for i, val in enumerate(my_list):
rest = permutations_generator(my_list[:i] + my_list[i+1:], r-1)
# yield from ([val] + rest_perm for rest_perm in rest)
for rest_perm in rest:
yield [val] + rest_perm
実行結果
if __name__ == "__main__":
my_list = [1, 2, 3]
for p in permutations_generator(my_list):
print(p)
### 出力 ###
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
組合せ(Combinations)
プロセス
基本的には順列の場合と同じです。ただし、順番を気にする必要がありません。
したがって、次の操作に関して、
-
{1, 2, 3}から1を含む組合せを列挙 -
{1, 2, 3}から2を含む組合せを列挙
2.では{2, 3}から2を含む組合せを列挙すればいいわけですね。
（1かつ2を含む組合せはもう既に列挙されているからです）
コード
これを踏まえると、コードは次のようになります。
def combinations(my_list, r=None):
if r == None:
r = len(my_list)
if r == 1:
return [[val] for val in my_list] # my_listを要素数1の組合せの組にする
else:
result = []
for i, val in enumerate(my_list):
rest = combinations(my_list[i+1:], r-1) # (i+1)番目以降の要素を使えばいい
for rest_perm in rest:
perm = [val] + rest_perm
result.append(perm)
return result
実行結果
if __name__ == "__main__":
my_list = [1, 2, 3, 4]
comb = combinations(my_list, 2)
print(comb)
### 出力 ###
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
おわりに
あくまで一例ですので、重複順列なども条件を少し変えると実装することができます。
以上です。良い組合せライフを。