Calculating the Amount of Combinations

Question

Cheers,

I know you can get the amount of combinations with the following formula (without repetition and order is not important):

// Choose r from n  n! / r!(n - r)!

However, I don't know how to implement this in C++, since for instance with

n = 52  n! = 8,0658175170943878571660636856404e+67

the number gets way too big even for unsigned __int64 (or unsigned long long). Is there some workaround to implement the formula without any third-party "bigint" -libraries?

Answer 1

Here's an ancient algorithm which is exact and doesn't overflow unless the result is to big for a long long

unsigned long long choose(unsigned long long n, unsigned long long k) {     if (k > n) {         return 0;     }     unsigned long long r = 1;     for (unsigned long long d = 1; d <= k; ++d) {         r *= n--;         r /= d;     }     return r; } 

This algorithm is also in Knuth's "The Art of Computer Programming, 3rd Edition, Volume 2: Seminumerical Algorithms" I think.

UPDATE: There's a small possibility that the algorithm will overflow on the line:

r *= n--; 

for very large n. A naive upper bound is sqrt(std::numeric_limits<long long>::max()) which means an n less than rougly 4,000,000,000.