組合せの数

折角BigIntegerを用意したのでいろいろ検証．

入山徳夫氏によるnCrを高速に求めるアルゴリズムはかなり速い．
n!/((n-r)!r!)は必ず整数になるので，先に約分を行って分母を消してから残りを掛け合わせる．

public static BigInteger Combination(int n, int r)
{
    if (n < 0 || r < 0 || r > n) throw new ArgumentException("不正な引数です．");

    if (n - r < r) r = n - r;
    if (r == 0) return 1;
    if (r == 1) return n;

    int[] numerator = new int[r];
    int[] denominator = new int[r];

    for (int k = 0; k < r; k++)
    {
        numerator[k] = n - r + k + 1;
        denominator[k] = k + 1;
    }

    for (int p = 2; p <= r; p++)
    {
        int pivot = denominator[p - 1];
        if (pivot > 1)
        {
            int offset = (n - r) % p;
            for (int k = p - 1; k < r; k += p)
            {
                numerator[k - offset] /= pivot;
                denominator[k] /= pivot;
            }
        }
    }

    BigInteger result = BigInteger.One;
    for (int k = 0; k < r; k++)
    {
        if (numerator[k] > 1) result *= numerator[k];
    }

    return result;
}

比較的高速な階乗計算アルゴリズムを用いて構成したアルゴリズムと比較をした結果．
Combination(n, r)を求めるまでの平均時間(秒)

(n,r)	(50000, 25000)	(100000, 50000)
入山氏版	0.3767	1.0643
階乗版	10.5325	50.6878

圧倒的だった．