2

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

Kaushik Mahadevan
  • 69
  • 7
  • Please check this related question: https://stackoverflow.com/questions/9330915/number-of-combinations-n-choose-r-in-c – jmizv Aug 12 '20 at 12:49

3 Answers3

1

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.

cigien
  • 57,834
  • 11
  • 73
  • 112
  • Thanks a lot! I figured the problem might be related to integer division but I must not have thought too hard. I thought changing the return-type of the function would help, but that didn't do much. – Kaushik Mahadevan Aug 12 '20 at 14:48
  • No problem, happy to help :) By the way, in case you are not aware, you can only accept one answer, so you should pick the one that is most satisfactory to you. However, you can upvote all the answers that you found useful as well. – cigien Aug 12 '20 at 14:55
  • Yup! I figured it out! I'm new to stackoverflow, so I'm still working out the kinks. Thanks again for your help! – Kaushik Mahadevan Aug 12 '20 at 14:57
1

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

Dominique
  • 16,450
  • 15
  • 56
  • 112
  • This is not a good idea. floating-point calculations can lead to results like `0.999` when you want `1`, and this will break the code. You don't need to do any conversion to `double` for this problem. – cigien Aug 12 '20 at 13:24
  • @cigien: this can be handled rounding the result to the nearest integer. Do you know if this is done by `Round()` or `(int)` typecast? – Dominique Aug 12 '20 at 13:27
  • Sure there are ways to do this, but seems unnecessary to add that complexity when it's not needed. – cigien Aug 12 '20 at 13:39
0

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;
}
BEAGLE
  • 343
  • 3
  • 10
  • While this may work, the OP's question is why their implementation of their formula is not working. This doesn't answer that question. – cigien Aug 12 '20 at 13:06
  • I did come across this formula too, but I spent quite a bit of time on the formula I used, but couldn't figure out where I was going wrong. It was more of a curiosity thing rather than problem solving. But I appreciate the help! Thank you! – Kaushik Mahadevan Aug 12 '20 at 14:52