計算二項式係數的算法

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; 
    }