3

I need to find the value of n choose r- the number of ways of selecting r objects out of n.

if i first find the numerator then the denominator. i get an exception.

i am using java.

how to do it for example for 44 choose 42

Rohit Banga
  • 18,458
  • 31
  • 113
  • 191
  • You'll find many good answers here: http://stackoverflow.com/questions/2201113/combinatoric-n-choose-r-in-java-math – aioobe Jan 25 '11 at 08:18

1 Answers1

4

You can use the fact that NcR is equal to Nc(N-R). The formula is:

 N * (N - 1) * ... * (N - R + 1)
---------------------------------
         1 * 2 * ... * R

You can observe that product of K consecutive numbers is always divisible by K. So, the loop would look like

  • multiply two numbers from nominator
  • divide by 2
  • multiply by the 3rd number from nominator
  • divide by 3
  • ...
  • multiply by the last number from the nominator
  • divide by R

Alternatively, just use java.math.BigInteger.

  • 1
    +1. Good solution. You get NcK in the process, so you can do memoization if needed. –  May 22 '10 at 21:31