Python 組み合わせ(combination)

はじめに

異なるn個のものの中からr個を選ぶ場合の数を組み合わせと呼ぶことにし、以下のようにあらわす。

{}_n C _r = \frac{n!}{r!(n-r)!}

pythonで${}_n C _r$を求める方法をいくつか取り上げる。

mathモジュールから自作

mathモジュールには組み合わせを直接求める関数がないため、上にあげた定義に基づき関数を作成する。

combination_1.py

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
base = comb(5,3)
print(base) # 10

scipyの組み込み関数

組み合わせの数を最も簡単に求められる方法。
scipy.special.comb — SciPy v1.3.0 Reference Guide
https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html

combination_2.py

from scipy.special import comb
base = comb(5, 3, exact=True)
print(base) # 10

itertoolsの組み込み関数

組み合わせをそのものを具体的に用意し、組み合わせの数を調べ${}_n C _r$を得る。組み合わせの数のみを求める場合はやや非効率。

combination_3.py

from itertools import combinations
base = list(combinations("abcde",3))
print(base)        #[('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'c', 'd'), ('a', 'c', 'e'), ('a', 'd', 'e'), ('b', 'c', 'd'), ('b', 'c', 'e'), ('b', 'd', 'e'), ('c', 'd', 'e')]
print(len(base))   # 10

nを固定してrの変化を求める場合

nを固定し$(0\leq\ r \leq\ n)$でrを変化させ複数の${}_n C _r$を求めるとき、連続する${}_n C _r$、${}_n C _{r+1}$$(0\leq\ r \leq\ n-1)$の二項間漸化式としてそれぞれを求める方法を考える。

{}_n C _r = \frac{n!}{r!(n-r)!}\\
{}_n C _{r+1} = \frac{n!}{(r+1)!(n-r-1)!}\\
\frac{{}_n C _{r+1}}{{}_n C _r} = \frac{n!}{(r+1)!(n-r-1)!} \frac{r!(n-r)!}{n!} = \frac{n-r}{r+1}\\
{}_n C _{r+1} = {}_n C _r \frac{n-r}{r+1}

combination_4.py

n = 5
nCr = 1
print(nCr)
for r in range(n):
    nCr_1 = nCr * (n - r) // (r + 1)
    nCr = nCr_1
    print(nCr_1)
# 1 5 10 10 5 1

これは${}_n C _r$$(0\leq\ r \leq\ n)$を個別に計算するよりも軽快に求まる。

#参考記事
https://www.haya-programming.com/entry/2018/04/14/185828