組合せと組合せの数
$n$ 個の異なったものから $k$ 個のものを取り出して一組にしたものを「$n$ 個から $k$ 個とった 組合せ」と定義します。その選び方の総数は
\[\displaystyle{}_{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() で組合せを取得する
標準ライブラリに収められている itertoolsモジュールの combinations() を使うと組み合わせをイテレータの形で得ることができます。
第 1 引数に組み合わせたい要素の入ったイテラブルオブジェクトを指定し、r には取りだす数を指定します。得られたイテレータからすべての要素を呼び出してリストに格納し、len() で要素の個数を求めると組合せの数が得られることになります。ただし、組合せの数だけを得たいときにこの方法を使うと処理が遅くなります。
# PYTHON_COMBINATION_01
# itertoolsモジュールからcombinations()をインポート
from itertools import combinations
my_list = ["赤", "青", "緑"]
# 赤、青、緑の3種の色から2色を選ぶ方法
x = combinations(my_list, 2)
# イテレータからすべての要素を取り出してリストに格納
list_x = list(x)
len_y = len(list_x)
print("組合せ：{}".format(list_x))
print("組合せの数：{}".format(len_y))組合せ：[('赤', '青'), ('赤', '緑'), ('青', '緑')]
組合せの数：3
Pythonで組合せの数を計算する
Scipyパッケージがインストールされている環境であれば、scipy.special.comb を使って組合せの数を計算できます。Scipy が使えない場合は関数を自作するという方法もあります。
scipy.special.comb
scipy.special をインポートすると以下の記法で n 個から k 個を選ぶ 組合せの数 を計算することができます。
非常に大きな n が指定された場合、組合せの数の正確な値を求めるまで長い時間を要することもあります。そこで、正確さを犠牲にして処理時間を節約したいと考えるプログラマーのためにオプション引数 exact が用意されています。この引数が False であれば、scipy.special.comb() は float型の近似値を返してきます。デフォルトで False に設定されているので、正確な値を int型でほしいと思うのであれば、この引数に True を指定してください。
# PYTHON_COMBINATION_02
# scipy.specialモジュールをインポート
from scipy import special
# 10個から3個をとって並べる組合せの数
x = special.comb(10, 3)
y = special.comb(10, 3, True)
print("x = {}".format(x))
print("y = {}".format(y))x = 120.0 y = 120
組合せの数を求めるアルゴリズム
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}{k-1}\,\frac{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_COMBINATION_03
# 有理数クラスをインポート
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
my_list = [comb(7, 3), comb(5, 0), comb(3, -2)]
print(my_list)[35, 1, 0]