唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

組み合わせの個数(二項係数)を計算する

python

数年前に上のような記事を書きましたが、ライブラリを使わない場合の計算について書いてなかったので記事にしました

組み合わせとは

いくつかの要素の中から、順番を区別せずにいくつかの要素を選ぶ方法

具体的なそれぞれの組み合わせを得たい場合、Pythonならitertools.combinationsで引数に与えたiterableの組み合わせを返すイテレータが得られます
C++ならnext_permutationが使えますが、あらかじめソートしておかないといけないので注意が必要です

組み合わせの数

\(n\)個の要素の中から、\(k\)個要素を選ぶ方法の個数は以下のように階乗(!)を使って計算できます
$${\binom nk} = \frac{n!}{k!(n-k)!}=\frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}$$
昔中学校か何かで勉強した時は次のCを使った表記で習いました
$${}_n\mathrm{C}_k$$
Cを使った表記は国によって(？)書き方が違ったりするらしいです

\(C(n, k), {}_n C_k, {}^n C_k, C^k_n, C^n_k,C_{n,k}\)

http://en.wikipedia.org/wiki/Binomial_coefficient

最近は上で書いたようなカッコを使った表記で見かけることが多いです

上の式に代入すればわかるように以下の関係が成り立つので、計算が楽になる
$${\binom nk} = {\binom n{n-k}}$$
組み合わせの数は\((x + y)^n\)を展開した時の\(x^{n - k}y^k\)の係数になっていて、二項係数とも呼ばれます

単純に計算する方法

\(\mathrm{O}(k)\)回のループである特定の二項係数を計算できる
先に\(n!\)を全部乗算してから割ろうとすると、言語によってはオーバーフローしてしまうので、逐次割っていったほうがよい

$${\binom nk} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n-(i-1)}{i}$$

def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in xrange(1, k + 1):
        m = m * (n - i + 1) / i    
    return m

動的計画法による方法

次のような関係式を利用することで、ある\(n, k\)までの二項係数を順番に求めることができる

$$\binom n0 = \binom nn = 1$$
\(1 \le n\)かつ\(1\le k \le n - 1\)である\(n,k\)について
$$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$
この関係はパスカルの三角形として知られている

この関係式を使えば以下のコードのように、\(\mathrm{O}(n^2)\)回のループで\(\binom nn\)までのすべての二項係数を求めておくことができる
ただし\(\mathrm{O}(n^2)\)のメモリを使うので注意が必要

def make_comb_dp(n):
    dp = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(n + 1):
        dp[i][0] = 1
        dp[i][i] = 1
    for i in xrange(2, n + 1):
        for j in xrange(1, i):
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    return dp
if __name__ == '__main__':
    for line in make_comb_dp(5):
        print line

出力

[1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0]
[1, 2, 1, 0, 0, 0]
[1, 3, 3, 1, 0, 0]
[1, 4, 6, 4, 1, 0]
[1, 5, 10, 10, 5, 1]

参考

上のStack Overflowの記事では厳密に計算する方法以外にも
フーリエ変換やスターリングの公式を使って近似的に計算する方法が書いてあるみたいです

二項係数の剰余の計算いろいろ

D問題で\(\binom nk \div 2^n\)の計算の話が出てくる
ちなみに自分が解いたときはPythonだったのであまりオーバーフローの心配がなかったので素朴にパスカルの三角形を計算して対数とかを使って無理やり計算した

'); jQuery.noConflict(true);