Combinatoric 'N Choose R' In Java Math?
Answer :
The Formula
It's actually very easy to compute N choose K without even computing factorials.
We know that the formula for (N choose K) is:
N! -------- (N-K)!K! Therefore, the formula for (N choose K+1) is:
N! N! N! N! (N-K) ---------------- = --------------- = -------------------- = -------- x ----- (N-(K+1))!(K+1)! (N-K-1)! (K+1)! (N-K)!/(N-K) K!(K+1) (N-K)!K! (K+1) That is:
(N choose K+1) = (N choose K) * (N-K)/(K+1) We also know that (N choose 0) is:
N! ---- = 1 N!0! So this gives us an easy starting point, and using the formula above, we can find (N choose K) for any K > 0 with K multiplications and K divisions.
Easy Pascal's Triangle
Putting the above together, we can easily generate Pascal's triangle as follows:
for (int n = 0; n < 10; n++) { int nCk = 1; for (int k = 0; k <= n; k++) { System.out.print(nCk + " "); nCk = nCk * (n-k) / (k+1); } System.out.println(); } This prints:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 BigInteger version
Applying the formula for BigInteger is straightforward:
static BigInteger binomial(final int N, final int K) { BigInteger ret = BigInteger.ONE; for (int k = 0; k < K; k++) { ret = ret.multiply(BigInteger.valueOf(N-k)) .divide(BigInteger.valueOf(k+1)); } return ret; } //... System.out.println(binomial(133, 71)); // prints "555687036928510235891585199545206017600" According to Google, 133 choose 71 = 5.55687037 × 1038.
References
- Wikipedia/Binomial coefficient
- Wikipedia/Pascal's triangle
- Wikipedia/Combination
The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils
The recursive definition gives you a pretty simple choose function which will work fine for small values. If you're planning on running this method a lot, or on large values, it would pay to memoize it, but otherwise works just fine.
public static long choose(long total, long choose){ if(total < choose) return 0; if(choose == 0 || choose == total) return 1; return choose(total-1,choose-1)+choose(total-1,choose); } Improving the runtime of this function is left as an exercise for the reader :)
Comments
Post a Comment