Combinations are not calculated correctly

Question

I found on Wikipedia that C(n,k) = (n-k+1)/k * C(n, k-1). I did the evidence myself and got that it was correct. Then I implemented it in my function, which is suppose to calculate combinations using recursion without hitting the built-in limit in python. This worked great.. until I put in to great numbers. This is my function:

def choose(n, k):
    if not k: 
        return 1
    elif n < k: 
        return 0
    else:
        return int((((n - k + 1) / k)) * choose(n, (k - 1)))

It worked if you would use lower numbers such as choose(1000, 4), but if you try numbers such as choose(1000,800) it will return the first 13 number right, but then get everything wrong. How come this occurs and even more important, how do you solve it?

Is this relevant? https://stackoverflow.com/questions/538551/handling-very-large-numbers-in-python — OliverRadini, Sep 24 '18 at 10:33
If your goal is to calculate nCr is this relevent ? https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python ? — EMKAY, Sep 24 '18 at 10:35
This seems like the usual problem with `float`ing point precision. — Giacomo Alzetta, Sep 24 '18 at 10:38

score 2 · Answer 1 · answered Sep 24 '18 at 10:43

2

(n - k + 1) / k will often not be an integer, as k won't always divide n-k+1, though it divides choose(n, (k - 1)) * (n-k+1).

So, in order to always manipulate integers (whose size is unlimited), you must multiply first, then divide using integer division:

def choose(n, k):
    if k == 0: 
        return 1
    elif n < k: 
        return 0
    else:
        return (n - k + 1) * choose(n, (k - 1)) // k

answered Sep 24 '18 at 10:43

Thierry Lathuille

23,663
10
44
50

But this will return an error for example choose(1000,999). Any way of fixing it? @Thierry Lathuille – Sep 24 '18 at 11:48
You've hit the recursion limit, which is 1000 levels by default. Using recursion to calculate numbers of combinations is not a very efficient method anyway, as you can see. Use loops instead. – Thierry Lathuille Sep 24 '18 at 11:57
My task is to do it with specifically recursion @Thierry Lathuille – Sep 24 '18 at 12:24

Combinations are not calculated correctly

1 Answers1