nhaa123 - 6 months ago 27

C++ 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`

`unsigned long long`

Answer

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.