『Python数値計算ノート』ではアフィリエイトプログラムを利用して商品を紹介しています。

組み合わせの数（重複ありと重複なし）

2018.10.07

【Python】組み合わせの数

$n$ 個の異なったものから $k$ 個のものを取り出して一組にしたものを「$n$ 個から $k$ 個とった組み合わせ」と定義します。その選び方の総数は
 \[{}_{n}\mathrm{C}_k=\binom{n}{k}=\frac{n!}{k!\,(n-k)!}\]
によって計算できます。これを「$n$ 個から $k$ 個とった組み合わせの数」といいます。また、$n$ 種類のものから重複を許して $r$ 個選ぶ組み合わせを重複組み合わせとよび、その選び方の総数は
 \[_n\mathrm{H}_r=\:{}_{n+r-1}\mathrm{C}_r\]
という式で計算できます。

itertools.combinations()

Python の標準ライブラリに収められている itertools モジュールの combinations() を使うと組み合わせをイテレータの形で得ることができます。

itertools.combinations(iterable, r=None)

第 1 引数に組み合わせたい要素の入ったイテラブルオブジェクトを指定し、r には取りだす数を指定します。得られたイテレータからすべての要素を呼び出してリストに格納し、len() で要素の個数を求めると組み合わせの数が得られます。ただし、組み合わせの数だけを得たいときにこの方法を使うと処理が遅くなります。

# PYTHON_ITERTOOLS_COMBINATIONS

# In[1]

from itertools import combinations

my_list = ["赤", "青", "緑"]

# 赤、青、緑の3種の色から2色を選ぶ方法
x = combinations(my_list, 2)

# イテレータからすべての要素を取り出してリストに格納
list_x = list(x)
len_x = len(list_x)

print("組み合わせ：{}".format(list_x))
print("組み合わせの数：{}".format(len_x))
# 組み合わせ：[('赤', '青'), ('赤', '緑'), ('青', '緑')]
# 組み合わせの数：3

scipy.special.comb

Scipy のサブパッケージ scipy.special をインポートすると、comb() 関数を使って、n 個から k 個を選ぶ 組み合わせの数 を計算することができます。

scipy.special.comb(n, k, exact=False)

非常に大きな n が指定された場合、組み合わせの数の正確な値を求めるまで長い時間を要することもあります。そこで、正確さを犠牲にして処理時間を節約するために、オプション引数 exact が用意されています。この引数が False であれば、scipy.special.comb() は float型の近似値を返してきます。デフォルトでは False に設定されているので、正確な値を int 型でほしいと思うのであれば、この引数に True を指定してください。

# SCIPY_SPECIAL_COMB

# In[1]

# scipy.specialモジュールをインポート
from scipy import special

# 50個から25個をとって並べる組合わせの数をfloat型近似値で取得
val = special.comb(50, 25)
print(val)
# 126410606437752.05

# In[2]

# 50個から25個をとって並べる組合わせの数をint型で取得
val = special.comb(50, 25, True)
print(val)
# 126410606437752

組み合わせの数を求めるアルゴリズム

Scipyパッケージがなければ、標準ライブラリの itertoolsモジュールの combinations() で得られたタプルの長さをとるという方法もありますが、組み合わせの数だけ欲しい場合には相当に無駄な処理を含むことになります。一般的には自分で関数を作ったほうが実用的です。ただし、組み合わせの数を計算する公式
 \[\binom{n}{k}=\frac{n!}{k!\,(n-k)!}\]
をそのまま使ってしまうと、巨大数の除算が実行されて、大きな引数が与えられると OverflowError を発生してしまいます。そこで上の式を $k$ 個の分数の積に分けるという工夫をします。最初に具体例として
 \[\binom{7}{3}=\frac{7!}{3!\,(7-3)!}\]
を計算してみます。
 \[\binom{7}{3}=\frac{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{(3\cdot 2\cdot 1)(4\cdot 3\cdot 2\cdot 1)}=\frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}\]
分子・分母ともに $k=3$ 個の数の積となっています（後述するように、これは一般の $n,\ k$ でも成り立ちます）。したがって上の式は $3$ 個の分数の積
 \[\binom{7}{3}=\frac{7}{3}\cdot\frac{6}{2}\cdot\frac{5}{1}\]
で計算することができます。一般の $n,\ k$ で計算してみます。
 \[\begin{align*}\binom{n}{k}&=\frac{n!}{k!\,(n-k)!}\\[6pt]&=\frac{n(n-1)(n-2)\\cdots\ 2\ \cdot\ 1}{\{k(k-1)(k-2)\ \cdots\ 2\ \cdot\ 1\}\{(n-k)(n-k-1)(n-k-2)\\cdots\ 2\ \cdot\ 1\}}\\[6pt]&=\frac{n(n-1)(n-2)\ \cdots\ (n-k+2)(n-k+1)}{(n-k)(n-k-1)(n-k-2)\ \cdots\ 2\ \cdot\ 1}\end{align*}\]
分子は $n-(n-k+1)+1=k$ 個の数の積であり、分母も $k$ 個の数の積となっています。つまり上の式は $k$ 個の分数の積で表すことができます：
 \[\binom{n}{k}=\frac{n-k+1}{1}\,\frac{n-k+2}{2}\,\frac{n-k+3}{3}\ \cdots\ \frac{n-1}{n-k-1}\,\frac{n}{n-k}\]
変数 $s$ を導入すると、組み合わせの総数 $\displaystyle{}_{n}\mathrm{C}_k=\binom{n}{k}$ は
 \[\frac{n-s+1}{s}\]
について、$s$ を $1$ から $k$ まで変えながら積をとれば計算できることになります。人間にとっては煩わしい手法ですが、コンピュータにはこのような計算法のほうが合っています。

まだ少し問題が残っています。$n=7,\ k=3$ の例でみたように、$7/3$ のような除算で僅かな丸め誤差が生じ、それをいくつも掛け合わせると誤差が積み重なります。大きな s が与えられると、s による除算でオーバーフローする可能性も残っています。また本来は整数で得られるはずの組み合わせの数が float で返ってくるというのも、あまり気持ちのよいものではありません。そこで標準ライブラリの fractionsモジュールをインポートして、Fraction型（分数）で計算させます。Fraction型は分数を 2 つの整数の組として表しているので除算が行われません。こういう場面でとても重宝するクラスです。

# PYTHON_COMBINATIONS_ALGORITHM

# In[1]

# 有理数クラスをインポート
from fractions import Fraction

# 組合せの総数
def comb(n, k):
    
    if n < 0 or k < 0:
        pdt = 0
    
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    
    # 戻り値をint型にするために分子を取り出す
    return pdt.numerator

# 7個から3個選ぶ組合せの総数を計算
print(comb(7, 3))
# 35

コメント