计算二项式系数的算法

Question

我需要一种计算组合的方法，而不会耗尽内存。这是迄今为止我所拥有的。

public static long combination(long n, long k) // nCk 
{ 
    return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k)))))); 
} 

public static long factorial(long n) 
{ 
    long result; 
    if (n <= 1) return 1; 
    result = factorial(n - 1) * n; 
    return result; 
} 

public static long divideFactorials(long numerator, long denominator) 
{ 
    return factorial(Math.Abs((numerator - denominator))); 
} 

我已经将它标记为C＃，但解决方案理想情况下应该与语言无关。

Answer 1

public static long combination(long n, long k) 
    { 
     double sum=0; 
     for(long i=0;i<k;i++) 
     { 
      sum+=Math.log10(n-i); 
      sum-=Math.log10(i+1); 
     } 
     return (long)Math.pow(10, sum); 
    } 

Answer 2

看着你的代码，难怪你的内存会很快耗尽。您的方法divideFactorials将调用方法阶乘，并将差异“分母 - 分母”用作参数。根据您的代码，这种差异很可能会非常大，您将在阶乘方法中停留在一个很长的循环中。

如果真的只是寻找NCK（我假设，因为在你的代码的注释），只需使用：

public static long GetnCk(long n, long k) 
{ 
    long bufferNum = 1; 
    long bufferDenom = 1; 

    for(long i = n; i > Math.Abs(n-k); i--) 
    { 
     bufferNum *= i; 
    } 

    for(long i = k; i => 1; i--) 
    { 
     bufferDenom *= i; 
    } 

    return (long)(bufferNom/bufferDenom); 
} 

当然，使用这种方法，你会跑出射程非常快，因为long实际上并不支持非常长的数字，所以n和k必须小于20.

假设您实际上使用了非常大的数字，您可以使用双打而不是长时间，因为功率变得越来越重要。

编辑： 如果使用大量的你也可以使用Stirling公式：

当n变大LN - > N * LN（N） - N（N！）。

把这个放入代码：

public static double GetnCk(long n, long k) 
{ 
    double buffern = n*Math.Log(n) - n; 
    double bufferk = k*Math.Log(k) - k; 
    double bufferkn = Math.Abs(n-k)*Math.Log(Math.Abs(n-k)) - Math.Abs(n-k); 

    return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn)); 
} 

我只是提出这个答案，像你说的语言无关的C＃代码只是为了演示它。既然你需要使用n和k的大数来实现这个功能，我提出这个作为寻找大组合的二项式系数的一般方法。

对于n和k都小于200-300的情况，您应该使用Victor Mukherjee提出的答案，因为它确切无误。

编辑2： 编辑我的第一个代码。

Answer 3

刚刚完成的缘故：标准C数学库既有Γ和ln Γ（称为tgamma和lgamma）的实现中

Γ（N）等于; （N-1）！

图书馆计算肯定比求和对数更快，更准确。有关更多信息，请参见Wikipedia和Mathworld。

Answer 4

我见过的计算二项式系数的最好方法之一是Mark Dominus。与其他方法相比，N和K值较大时溢出的可能性要小得多。

public static long GetBinCoeff(long N, long K) 
{ 
    // This function gets the total number of unique combinations based upon N and K. 
    // N is the total number of items. 
    // K is the size of the group. 
    // Total number of unique combinations = N!/(K! (N - K)!). 
    // This function is less efficient, but is more likely to not overflow when N and K are large. 
    // Taken from: http://blog.plover.com/math/choose.html 
    // 
    long r = 1; 
    long d; 
    if (K > N) return 0; 
    for (d = 1; d <= K; d++) 
    { 
     r *= N--; 
     r /= d; 
    } 
    return r; 
} 

Answer 5

这是一个与Bob Byran非常相似的解决方案，但是检查了两个更多的先决条件来加速代码。

/// <summary> 
    /// Calculates the binomial coefficient (nCk) (N items, choose k) 
    /// </summary> 
    /// <param name="n">the number items</param> 
    /// <param name="k">the number to choose</param> 
    /// <returns>the binomial coefficient</returns> 
    public static long BinomCoefficient(long n, long k) 
    { 
     if (k > n) { return 0; } 
     if (n == k) { return 1; } // only one way to chose when n == k 
     if (k > n - k) { k = n - k; } // Everything is symmetric around n-k, so it is quicker to iterate over a smaller k than a larger one. 
     long c = 1; 
     for (long i = 1; i <= k; i++) 
     { 
      c *= n--; 
      c /= i; 
     } 
     return c; 
    }