python 組み合わせを計算

組み合わせの総数を計算する方法を説明します。

また、実行時間の比較を示します。比較の結果は下記です。

正確な値、近似した値共にscipy.special.combの実行時間が短いです。

組み合わせの総数
参考

組み合わせの総数

math.comb

math.combはpython3.8で追加されました。
math — 数学関数 — Python 3.9.4 ドキュメント

import math
print(math.comb(3, 2))
"""出力
3
"""

math.factorial

下記、公式の計算をmath.factorialを使用して行う方法(*1)です。
$$\frac{n!}{r!(n-r)!}$$
公式は、下記を参照してください。
【3分で分かる！】順列と組み合わせの違いと公式をわかりやすく（練習問題つき） | 合格サプリ

(*1)math.factorialは、階乗をを整数で返します。math — 数学関数 — Python 3.9.4 ドキュメント

def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)
print(nCr(3, 2))
"""出力
3
"""

scipy.special.comb

scipy.special.comb — SciPy v1.7.1 Manualを使用した方法です。

from scipy.special import comb
print(comb(3, 2, exact=True))
"""出力
3
"""

引数のexactがFalseの場合は計算結果が浮動小数点精度で近似された値となり、Trueの場合は計算結果が整数となります(近似されていない)。
正確な値を算出したい場合は、exactをTrueにする必要があります。

from scipy.special import comb
# for r in range(40,50):
#     print(comb(100, r, exact=False))
"""出力
1.3746234145802806e+28
2.011644021336996e+28
2.825880887116256e+28
3.811653289598673e+28
4.93782357970737e+28
6.144847121413616e+28
7.347099819081498e+28
8.441348728306404e+28
9.320655887504988e+28
9.891308288780802e+28
"""
for r in range(40,50):
    print(comb(100, r, exact=True))
"""出力
13746234145802811501267369720
20116440213369968050635175200
28258808871162574166368460400
38116532895986727945334202400
49378235797073715747364762200
61448471214136179596720592960
73470998190814997343905056800
84413487283064039501507937600
93206558875049876949581681100
98913082887808032681188722800
"""

exact=Falseの出力に「1.3746234145802806e+28」(*1)がありますが、exact=Trueの対応する出力は「13746234145802811501267369720」となっております。太文字部を見ると、exact=Falseの場合は近似値になっていることがわかります。

(*1)：e+28は10の28乗

実行時間の比較

math.comb 、 math.factorial 、 scipy.special.combの実行時間を比較しました。条件は下記です。

nは10000固定
rは1から10000まで300刻みで増加。 ※1, 301, 601, …

正確な値、近似した値共にscipy.special.combの実行時間が短いです。

import matplotlib.pyplot as plt
import math
import timeit
from scipy.special import comb

def nCr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

n = 10**4
num = 10
time_nCr = []
time_mathComb = []
time_scipiSpecialComb = []

#ステップ数が300である理由は右記：計算時間の短縮、グラフの点の間隔を調整
r_list = [x for x in range(1, n, 300)]
for r in r_list:
    #nCr
    result = timeit.timeit("nCr(n, r)", number = num, globals=globals())
    #resultはnCrをnum回繰り返した時の値になっているので、nで割ります。
    time_nCr.append(result/num)
    #math.comb
    result = timeit.timeit("math.comb(n, r)", number = num, globals=globals())
    time_mathComb.append(result/num)
    #scipy.special.comb
    result = timeit.timeit("comb(n, r, exact=True)", number = num, globals=globals())
    time_scipiSpecialComb.append(result/num)

plt.plot(r_list, time_nCr, marker='o', color='r', linestyle='-', label='nCr')
plt.plot(r_list, time_mathComb, marker='o', color='g', linestyle='-', label='math.comb')
plt.plot(r_list, time_scipiSpecialComb, marker='o', color='b', linestyle='-', label='scipy.special.comb')

plt.xlabel('r', fontsize=18)
plt.ylabel('time(sec)[log]', fontsize=18)
plt.legend(loc='upper left')
plt.yscale('log')
plt.show()

scipy.special.combのexactがTrueの時です。