数年前に上のような記事を書きましたが、ライブラリを使わない場合の計算について書いてなかったので記事にしました
組み合わせとは
いくつかの要素の中から、順番を区別せずにいくつかの要素を選ぶ方法
具体的なそれぞれの組み合わせを得たい場合、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]
