【Python】組み合わせ(nCr) 計算の高速化


＊ 以下の項目における各手法の評価はあくまで個人的なものです。

# 目次
- [既存ツールを用いた手法１（評価 ☆）](#既存ツールを用いた手法１評価-)
- [既存ツールを用いた手法２（評価 ☆☆）](#既存ツールを用いた手法２評価-)
- [既存ツールを用いた手法３（評価 ☆☆☆）](#既存ツールを用いた手法３評価-)
- [ユーザ定義型１（評価 ☆☆）](#ユーザ定義型１評価-)
- [ユーザ定義型２（評価 ☆☆☆）](#ユーザ定義型２評価-)
- [ユーザ定義型３（評価 ☆☆）](#ユーザ定義型３評価-)
- [番外編](#番外編)
- [計算時間の比較](#計算時間の比較)
- [まとめ](#まとめ)

# 既存ツールを用いた手法１（評価 ☆）
itertools.combinations()で組み合わせのリスト作ってその大きさを求める。

```sample.py
import itertools
a = len(list(itertools.combinations(range(n), r)))
```

#### メリット
思いつきません...

#### デメリット
- 遅い
- メモリを圧迫する

# 既存ツールを用いた手法２（評価 ☆☆）
math.factorial()を使う

```sample.py
from math import factorial
a = factorial(n) / factorial(r) / factorial(n - r)
```

#### メリット
- それなりに速い

#### デメリット
- nとrの値によってはエラーになる (どこでエラーになるか分かりにくい)
 - n = 200, r <= 51 → エラー
 - n = 200, r > 51 → 成功
 - n = 1000, r <= 896 → エラー
 - n = 1000, r > 896 → 成功


# 既存ツールを用いた手法３（評価 ☆☆☆）
外部ライブラリ scipy ~~の scipy.misc.comb()~~ を使う。

(2018/08/12 追記)
scipyの仕様が変わって、現在は scipy.special.comb() が推奨されているようです。

```sample.py
from scipy.special import comb
# a = comb(n, r)
a = comb(n, r, exact=True)
```

#### メリット
- 速い

#### デメリット
- 外部モジュールが使えない環境（競プロなど）では不可
- ~~答えが大きすぎる場合には戻り値が "inf" になる~~

（2019/01/10追記）
引数に`exact=True`を指定することで戻り値が"inf"になるのを回避できるようです。また，デフォルトの状態ではfloat型で近似された値が返されるので，正確な値を求めたい場合にも，この引数が必要になります。（その分若干遅くなります。）


# ユーザ定義型１（評価 ☆☆）
辞書と再帰を利用

```sample.py
# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

a = cmb(n,r)
```

#### メリット
- ムダな計算を行わない
- 計算回数が多い場合に有効

#### デメリット
- 一回目の計算が遅い
- nが大きい場合にはメモリを圧迫する


# ユーザ定義型２（評価 ☆☆☆）
operator と functools の関数を利用

```sample.py
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a = cmb(n, r)
```

#### メリット
- 安定した速さ（nの値によって極端に遅くなることはない）

#### デメリット（？）
- import文が増える


# ユーザ定義型３（評価 ☆☆）
「[組み合わせの数](http://d.hatena.ne.jp/kadzus/20081211/1229023326)」 にある方法をPythonで実装

```sample.py
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a = cmb(n,r)
```


#### メリット
- n の値がとても大きい場合に有効

#### デメリット
- n の値が小さい場合には遅い
- コード量が多い

# 番外編
競技プログラミングでよく目にする「10^9+7で割った余り」を求める場合は以下のようなやり方ができるそうです。

```sample.py
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a = cmb(n,r,mod)
```

#### メリット
- nが大きい場合も高速

#### デメリット
- フェルマーの小定理を用いているので，「10^9(素数でない値)で割った余り」とかはできない

# 計算時間の比較
- rはnの半分の値に設定
- 最速値は太字，2位は斜体

### 10回実行した時
|n|scipy|ユーザ１|ユーザ2|ユーザ3|
|---|---|---|---|---|
|10|**0.000007**|0.000023|*0.000017*|0.000063|
|100|**0.000061**|0.002005|*0.000116*|0.000730|
|1000|*0.001784*|0.313290|**0.001653**|0.004810|
|10000|0.126295|over 60sec|*0.114638*|**0.047322**|


### 100回実行した時
|n|scipy|ユーザ１|ユーザ2|ユーザ3|
|---|---|---|---|---|
|10|**0.000043**|*0.000059*|0.000141|0.000507|
|100|**0.000535**|0.001821|*0.000750*|0.004292|
|1000|*0.018275*|0.306701|**0.017078**|0.043484|
|10000|1.225358|over 60sec|*1.161715*|**0.497158**|


### 1000回実行した時
|n|scipy|ユーザ１|ユーザ2|ユーザ3|
|---|---|---|---|---|
|10|**0.000385**|*0.000430*|0.001337|0.004979|
|100|*0.005945*|**0.003403**|0.007389|0.040263|
|1000|**0.165513**|0.281874|*0.179260*|0.458516|
|10000|12.191156|over 60sec|*11.926124*|**5.118705**|


# まとめ
scipyは安定して速いですが，条件によってはユーザ定義型の方が高速に計算できることもあるようです。ただし，ユーザ定義型はそれぞれ一長一短なので，条件（想定される n の大きさや計算回数）に応じて使い分ける必要がありそうです。

# 参考
[python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。](https://qiita.com/cof/items/05f6ffc6d4e5b062aaa9)
[Python3で組み合わせ計算を高速化](http://muromura.hatenablog.com/entry/2017/07/02/020846)
[組み合わせの数](http://d.hatena.ne.jp/kadzus/20081211/1229023326)