Pythonで順列・組合せを列挙する(再帰関数)

## はじめに

`Python 組合せ列挙`などと検索すると、標準ライブラリ[`itertools`](https://docs.python.org/ja/3/library/itertools.html)の`permutations`や`combinations`を使って実装している記事が多くでてきます。

**しかしそんなものは甘えに過ぎません、$Pythonista$たるもの標準ライブラリくらい一度は自力で実装しておきたいものです。**

※ライブラリの利用を否定しているわけではありません。
※むしろ、自力で実装するよりはライブラリの方が高速でしょうから、実際に運用するときは大人しく`itertools`使いましょう。

### 対象読者

「じゃあ`permutations / combinations`の中身はどうなってるの？」と思ってるそこのあなた

## いざ実装

### 再帰関数って？？

すごくわかりやすい記事があるのでそちらを参照してください。

[再帰関数を学ぶと、どんな世界が広がるか](https://qiita.com/drken/items/23a4f604fa3f505dd5ad)

### 順列(Permutations)
`itertools.permutations`の中身を再現してみます。

#### プロセス
前提として、以下のような書き方を用います。

- `{要素1, 要素2, ...}`：数字の組、順番は関係ない

- `[要素1, 要素2, ...]`：数字の順列、順番が関係ある

- `([順列1], [順列2], ...)`：求めた順列の組


それでは、`{1, 2, 3}`を用いた順列を全て生成する過程を順を追って考えてみましょう。

1. `1`から始まる順列を生成する
   1. `1`を除いた`{2, 3}`を用いた順列を生成する
      1. `{2, 3}`を用いて`2`から始まる順列を生成する
         1. 残りの数字の組`{3}`から順列を生成する
			   1. 順列の組`([3])`を返す
			2. 求めた順列の先頭にそれぞれ`2`をくっつける
			3. 順列の組`([2, 3])`を返す
		2. `{2, 3}`を用いて`3`から始まる順列を生成する
		   1. 残りの数字の組`{2}`から順列を生成する
		      1. 順列の組`([2])`を返す
		   1. 求めた順列の先頭にそれぞれ`3`をくっつける
		   1. 順列の組`([3, 2])`を返す
		3. 順列の組`([2, 3], [3, 2])`を返す
	2. 求めた順列の先頭にそれぞれ`1`をくっつける
	3. 順列の組`([1, 2, 3], [1, 3, 2])`を返す
2. `2`から始まる順列を生成する
   1. ...
3. `3`から始まる順列を生成する
   1. ...

**結果**

```python
(
  	[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.で取り出した数字をくっつける

ただし、1.で数字が1個しかないときは**要素数1の順列**を返します

要は、求める順列を**小さい単位に分割**して求めていく感じですね。

#### コード

実際にはこうやって実装しています。

```python
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                                   # 順列の組を返す
```

**実行結果**

```python
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個取り出したい**という場合は、このような実装になります。

```python
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
```

**実行結果**

```python
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]などを参照してみてください。

 ```python
 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
 ```

**実行結果**

```python
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. `{1, 2, 3}`から`1`を含む組合せを列挙
1. `{1, 2, 3}`から`2`を含む組合せを列挙

2.では`{2, 3}`から`2`を含む組合せを列挙すればいいわけですね。

（`1`かつ`2`を含む組合せはもう既に列挙されているからです）

#### コード

これを踏まえると、コードは次のようになります。

```python

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
```

**実行結果**

```python
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]]
```



## おわりに
あくまで一例ですので、重複順列なども条件を少し変えると実装することができます。
以上です。良い組合せライフを。




[^1]: [Pythonのイテレータとジェネレータ](https://qiita.com/tomotaka_ito/items/35f3eb108f587022fa09)
[^2]: [yieldの使い方](https://www.lifewithpython.com/2018/05/python-yield.html)