組合せ (コンビネーション) を求めるプログラム

今日の TopCoder SRM において組合せ (コンビネーション; いわゆる nCm と書くやつ) を求める必要があったものの、ぱっと処理を書くことができなかったので反省を込めてメモを。

組合せを求める

組合せ $nCm$ を求める式は以下のようになります。

$nCm = \frac{n!}{m!(n-m)!} = \frac{ n \cdot (n-1) \cdots 1}{\{ m \cdot (m-1) \cdots 1 \}\{ ( n - m ) \cdot ( n - m - 1) \cdots 1 \}} = \frac{ n \cdot (n-1) \cdots ( n - m + 1)}{ m \cdot (m-1) \cdots 1 }$

簡単に実装できそうな感じですが、分子と分母をどういう順番で掛ければ良いかでちょっと悩んでしまいました。分子と分母を別々に計算して最後に分子を分母で割る、という方法では分子および分母の値があっという間に大きくなってしまいますし、1 個ずつ分子を分母で割ってから掛け合わせる、という方法では丸め誤差が発生してしまうし。。

で、どうしたらいいんだろう、と悩んだんですが、前 (数の大きい方) から掛けるんじゃなくて、後ろのほうから分子、分母を順番に計算していけば問題ないんですね。 Java で書くとこんな感じでしょうか。

/**
 * 組合せ (nCm) を求めるメソッド.
 * n は任意の非負整数, m は 0 以上 m 以下の整数.
 * 値によってはオーバーフローする可能性がある.
 */
long calcCombination( int n, int m ) {
    if( n < m || m < 0 ) {
        throw new IllegalArgumentException( "引数の値が不正です ( n : " + n + ", m : " + m + ")" );
    }
    long c = 1;
    m = ( n - m < m ? n - m : m );
    for( int ns = n - m + 1, ms = 1; ms <= m; ns ++, ms ++ ) {
        c *= ns;
        c /= ms;
    }
    return c;
}