如何计算大数的二项式系数

Question

我需要在C#中计算n!/(n-r)!r!。对于小数值来说，使用阶乘函数很容易计算，但是当数字变得更大，如100时，它就不起作用了。有没有其他方法可以计算更大的数字组合？

- Jay

---

你用什么来存储这个数字？在100选10中，这个数字的数量级约为10^13，因此普通的整数/长整数很快就会耗尽空间。你可以尝试使用BigInteger，但我不知道它们能有多大。你也可以制作一个n位数组，并将数字保存为二进制数，但需要更多的计算。 - twain249

“它不好用”是什么意思？ - cadrell0

阶乘变得很大，int64无法容纳它。 - Jay

Answer 1

首先，我注意到你正在尝试计算二项式系数，所以我们称它为二项式系数。

以下是一些计算方法。如果您使用BigInteger，就不必担心溢出：

方法一：使用阶乘：

static BigInteger Factorial(BigInteger n)
{
    BigInteger f = 1;
    for (BigInteger i = 2; i <= n; ++i)
        f = f * i;
    return f;
}

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    return Factorial(n) / (Factorial(n-k) * Factorial(k));
}

方法二：使用递归：

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    if (n == 0) return 1;
    if (k == 0) return 0;
    return BinomialCoefficient(n-1, k-1) + BinomialCoefficient(n-1, k)
}

除非你使用记忆化结果，否则这种方法速度不快。

第三种方法：更加聪明地减少乘法的次数和早期的除法。这可以保持数字的小大小：

static BigInteger BinomialCoefficient(BigInteger n, BigInteger k)
{
    // (n C k) and (n C (n-k)) are the same, so pick the smaller as k:
    if (k > n - k) k = n - k;
    BigInteger result = 1;
    for (BigInteger i = 1; i <= k; ++i)
    {
        result *= n - k + i;
        result /= i;
    }
    return result;
}

举个例子，如果你要计算 (6 C 3)，不用计算 (6 x 5 x 4 x 3 x 2 x 1) / ((3 x 2 x 1) x (3 x 2 x 1))，而是计算 (((4 / 1) * 5) / 2) * 6) / 3，这样可以尽可能保持数字小。

- Eric Lippert

---

很好的答案。虽然最后的实现对于BC(0,10)返回了错误的结果...它返回1，但应该返回0。添加与您上面相同的检查if(k == 0)...可以解决这个问题。 - LBushkin

@LBushkin 我认为是方法二出了问题。当 k==0 时应该得到结果 1。| 方法三能够工作非常有趣。对我来说，不明显的是除以 i 不会留下余数。 - CodesInChaos

当你这样思考时，它会变得明显：假设我们有(((n) / 1) * (n+1)) / 2。显然，n或n+1中的一个数是可以被2整除的。再假设我们有((((n) / 1) * (n+1)) / 2) * (n+2) / 3——我们已经解决了2的因子。显然，n、n+1或者n+2中的一个数是可以被3整除的。以此类推，每次我们都是将当前或前面的项中必须出现的一个值作为因子来进行除法运算。 - Eric Lippert

Answer 2

根据Eric所说，早期划分非常有帮助，您可以通过从高到低进行划分来改进它。这样一来，只要最终结果适合Long类型，就可以计算出任何结果。以下是我使用的代码（抱歉是Java，但转换应该很容易）：

public static long binomialCoefficient(int n, int k) {
   // take the lowest possible k to reduce computing using: n over k = n over (n-k)
   k = java.lang.Math.min( k, n - k );

   // holds the high number: fi. (1000 over 990) holds 991..1000
   long highnumber[] = new long[k];
   for (int i = 0; i < k; i++)
      highnumber[i] = n - i; // the high number first order is important
   // holds the dividers: fi. (1000 over 990) holds 2..10
   int dividers[] = new int[k - 1];
   for (int i = 0; i < k - 1; i++)
      dividers[i] = k - i;

   // for every divider there always exists a highnumber that can be divided by 
   // this, the number of highnumbers being a sequence that equals the number of 
   // dividers. Thus, the only trick needed is to divide in reverse order, so 
   // divide the highest divider first trying it on the highest highnumber first. 
   // That way you do not need to do any tricks with primes.
   for (int divider: dividers) 
      for (int i = 0; i < k; i++)
         if (highnumber[i] % divider == 0) {
            highnumber[i] /= divider;
            break;
         }

   // multiply remainder of highnumbers
   long result = 1;
   for (long high : highnumber)
      result *= high;
   return result;
}

- Jeroen Vuurens

Answer 3

对于 .net 4.0 及以上版本，请使用 BigInteger 类代替 int/long。

对于其他 .net 版本，请使用自定义的大数字类，例如来自 IntX：http://www.codeplex.com/IntX/

- Serj-Tm

Answer 4

我认为这将是高效的
它是O(k)

注意 n! / r!，r! 只会消去 n 的最后一个 r
所以 7 3

7 x 6 x 5 x 4 x 3 x 2 x 1 
over 
            4 x 3 x 2 x 1 

public static uint BinomialCoeffient(uint n, uint k)
{
    if (k > n)
        return 0;

    uint c = n;
    for (uint i = 1; i < k; i++)
    {
        c *= n - i;
        c /= i + 1;
    }
    return c;
}

- paparazzo