Binomial coefficient calculation algorithm

Question

I need a way to calculate combinations without running out of memory. Here is what I still have.

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

I marked it as C #, but ideally the solution should be language independent.

Answer 1

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

Answer 2

One of the best binomial coefficient calculation methods I've seen is suggested by Mark Dominus . This is much less likely to overflow with large values ​​for N and K than some other methods.

 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 3

Here is a solution that is very similar to Bob Biran, but tests two more prerequisites for speeding up the code.

  /// <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 nk, 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; } 

Answer 4

Looking at your code, it is not surprising that you will run out of memory quickly. Your divideFactorials method calls the factorial method and uses the numerator-denominator difference as an argument. This difference is likely to be very large according to your code, and you will be stuck in a very long loop in your factorial method.

If this is really just a nCk search (which I assume because your comment is in your code), simply use:

 public static long GetnCk(long n, long k) { long bufferNum = 1; long bufferDenom = 1; for(long i = n; i > Math.Abs(nk); i--) { bufferNum *= i; } for(long i = k; i => 1; i--) { bufferDenom *= i; } return (long)(bufferNom/bufferDenom); } 

Of course, using this method, you quickly run out of range, because long does not actually support very long numbers, so n and k must be less than 20.

Assuming that you are actually working with very large numbers, you can use doubles instead of longs, as the powers are becoming more significant.

Edit: If you use large numbers, you can also use the Stirling Formula:

As n becomes large ln (n!) → n * ln (n) - n.

Introducing this into code:

 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(nk)*Math.Log(Math.Abs(nk)) - Math.Abs(nk); return Math.Exp(buffern)/(Math.Exp(bufferk)*Math.Exp(bufferkn)); } 

I offer this answer only because, as you said, is language independent, C # code is simply used to demonstrate it. Since this requires using large numbers for n and k, I suggest this as a general way to find the binomial coefficient for large combinations.

In cases where n and k are both less than about 200-300, you should use the answer suggested by Victor Mukherjee, as it is.

Edit2: Edited my first code.

Answer 5

Simple to complete: the C standard math library has implementations like & Gamma; and ln? (called tgamma and lgamma ), where

& Gamma; (n) & is equal to; (P-1)!

Computing a library is, of course, faster and more accurate than adding logarithms. For more information, see Wikipedia and Mathworld .