Menu
Is there a built in method in a java library that can compute 'N choose R' for any N, R?
498
For NO repetitions, the formula is: n! / (n – r)! N is the number of things you are choosing from, r is the number of items.
and we choose r of them, no repetition, order doesn't matter. It is often called "n choose r" (such as "16 choose 3")
We use the size() method to get the number of elements in the list. We set a constant value 2 to r, i.e., the number of items being chosen at a time. After that, we use the combination formula, i.e., fact(n) / (fact(r) * fact(n-r)) and store the result into the result variable.
The n choose k formula is also known as combinations formula (as we call a way of choosing things to be a combination). This formula involves factorials. The n Choose k Formula is: C (n , k) = n! / [ (n-k)! k! ]
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.
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 versionApplying 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.
79
The apache-commons "Math" supports this in org.apache.commons.math4.util.CombinatoricsUtils
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
