Approach 1:
C(n,r) = n!/(n-r)!r!
Approach 2:
In the book Combinatorial Algorithms by wilf, i have found this:
C(n,r) can be written as C(n-1,r) + C(n-1,r-1)
.
e.g.
C(7,4) = C(6,4) + C(6,3)
= C(5,4) + C(5,3) + C(5,3) + C(5,2)
. .
. .
. .
. .
After solving
= C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)
As you can see, the final solution doesn't need any multiplication. In every form C(n,r), either n==r or r==1.
Here is the sample code i have implemented:
int foo(int n,int r)
{
if(n==r) return 1;
if(r==1) return n;
return foo(n-1,r) + foo(n-1,r-1);
}
See output here.
In the approach 2, there are overlapping sub-problems where we are calling recursion to solve the same sub-problems again. We can avoid it by using Dynamic Programming.
I want to know which is the better way to calculate C(n,r)?.
Both approaches will save time, but the first one is very prone to integer overflow.
Approach 1:
This approach will generate result in shortest time (in at most
n/2
iterations), and the possibility of overflow can be reduced by doing the multiplications carefully:This code will start multiplication of the numerator from the smaller end, and as the product of any
k
consecutive integers is divisible byk!
, there will be no divisibility problem. But the possibility of overflow is still there, another useful trick may be dividingn - r + i
andi
by their GCD before doing the multiplication and division (and still overflow may occur).Approach 2:
In this approach, you'll be actually building up the Pascal's Triangle. The dynamic approach is much faster than the recursive one (the first one is
O(n^2)
while the other is exponential). However, you'll need to useO(n^2)
memory too.Then you can look up any
C(n, r)
inO(1)
time.If you need a particular
C(n, r)
(i.e. the full triangle is not needed), then the memory consumption can be madeO(n)
by overwriting the same row of the triangle, top to bottom.The inner loop is started from the end to simplify the calculations. If you start it from index 0, you'll need another variable to store the value being overwritten.
I think your recursive approach should work efficiently with
DP
. But it will start giving problems once the constraints increase. See http://www.spoj.pl/problems/MARBLES/Here is the function which i use in online judges and coding contests. So it works quite fast.
It is an efficient implementation for your Approach #1
Using dynamic programming you can easily find the nCr here is the solution
Your Recursive Approach is fine but using DP with your approach will reduce the overhead of solving subproblems again.Now since we already have two Conditions-
Now we can easily build a DP solution by storing our subresults in a 2-D array-
Now if you want to further otimise, Getting the prime factorization of the binomial coefficient is probably the most efficient way to calculate it, especially if multiplication is expensive.
The fastest method I know is Vladimir's method. One avoids division all together by decomposing nCr into prime factors. As Vladimir says you can do this pretty efficiently using Eratosthenes sieve.Also,Use Fermat's little theorem to calculate nCr mod MOD(Where MOD is a prime number).