What's wrong with this function that I wrote to find calculate NCR?

user_11913587 0
Viewed 99

I tried using this relationship to recursively find the value of nCr:

nCr = (n - r + 1) / r * nC(r-1)

int comb(int n, int r){
    if(r == 0) return 1;
    return ((n - r + 1) / r) * comb(n , r - 1);
}

For a call of 6C2 I get 12 instead of 15. I have tried to trace, but I'm getting the right answer. Any input is appreciated! Thank you

combinatorics recursion function c++
3 Answers

Consider what happens when you do comb(6, 2). In the first recursive call, the return expression becomes:

return (5 / 2) * comb(6, 1);

The (5 / 2) is going to do integer division and give 2 which is not correct.

Since the final answer of nCr is actually guaranteed to have a result that is an integer, you can fix the equation by simply computing all the numerators before dividing it by any of the denominators, like this:

return (n - r + 1) * comb(n , r - 1) / r ;

Here's a demo.

Note that if you are concerned with the numerator value overflowing an int, you can restructure the equation, or use another formula where it's easier to cancel out terms earlier.

user_83728530

The typical pitfall of dividing integers:

How much is:

(3/2)*(4/3)

In reality it is 2, in C++ this is 1:

Integer division of 3/2 equals 1.
Integer division of 4/3 equals 1.

Hence, you need to force floating point division, e.g. by doing:

int comb(int n, int r){
    if(r == 0) return 1;
    return ((double)(n - r + 1) / r) * comb(n , r - 1);
}

Good luck

user_42791550

use this formula.

nCr = ( n / r ) * n-1Cr-1;

Your code changes to,

int comb(int n, int r)
{
    if(r > 0)
        return (n/r)*comb(n-1,r-1);
    else 
        return 1;
}
user_72683080
Related