how to calculate combination of large numbers

Question

I calculated permutation of numbers as:-

nPr = n!/(n-r)!

where n and r are given . 1<= n,r <= 100

i find p=(n-r)+1
and 
for(i=n;i>=p;i--)
  multiply digit by digit and store in array.

But how will I calculate the nCr = n!/[r! * (n-r)!] for the same range.?

I did this using recursion as follow :-

#include <stdio.h>
typedef unsigned long long i64;
i64 dp[100][100];
i64 nCr(int n, int r)
{
if(n==r) return dp[n][r] = 1;
if(r==0) return dp[n][r] = 1;
if(r==1) return dp[n][r] = (i64)n;
if(dp[n][r]) return dp[n][r];
return dp[n][r] = nCr(n-1,r) + nCr(n-1,r-1);
}

int main()
{
int n, r;
while(scanf("%d %d",&n,&r)==2)
{
    r = (r<n-r)? r : n-r;
    printf("%llu\n",nCr(n,r));
}
return 0;
}

but range for n <=100 , and this is not working for n>60 .

look at wikipedia page on combination, the solution is there. — didierc, Jan 28 '13 at 06:31
*Remark:* For n = 100, r = 50, you have nCr = 100891344545564193334812497256 which does not fit into a 64-bit variable. — Martin R, Jan 28 '13 at 06:34
see [this other question](http://stackoverflow.com/questions/12983731/algorithm-for-calculating-binomial-coefficient). — didierc, Jan 28 '13 at 06:49

score 2 · Answer 1 · answered Jan 28 '13 at 14:22

Consider using a BigInteger type of class to represnet your big numbers. BigInteger is available in Java and C# (version 4+ of the .NET Framework). From your question, it looks like you are using C++ (which you should always add as a tag). So try looking here and here for a usable C++ BigInteger class.

One of the best methods for calculating the binomial coefficient I have seen suggested is by Mark Dominus. It is much less likely to overflow with larger values for N and K than some other methods.

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
   //
   if (K > N) return 0;
   long r = 1;
   long d;
   for (d = 1; d <= K; d++)
   {
      r *= N--;
      r /= d;
   }
   return r;
}

Just replace all the long definitions with BigInt and you should be good to go.

Offhand, I don't see how. Do you have a suggestion for an improvement? — Bob Bryan, Sep 10 '15 at 23:08

how to calculate combination of large numbers

1 Answers1

Linked