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 with C++, since for instance with

n = 52

n! = 8,0658175170943878571660636856404e+67

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

Answer 1

for use big int see :
http://stackoverflow.com/questions/1188939/representing-128-bit-numbers-in-c
http://stackoverflow.com/questions/1055661/bigint-bigbit-library
http://stackoverflow.com/questions/238343/big-number-in-c

Answer 2

Remember that

n! / ( n - r )! = n * ( n - 1) * .. * (n - r + 1 )

so it's way smaller than n!. So the solution is to evaluate n* ( n - 1 ) * ... * ( n - r + 1) instead of first calculating n! and then dividing it .

Of course it all depends on the relative magnitude of n and r - if r is relatively big compared to n, then it still won't fit.

Answer 3

Simplify the formula first though. You don't wanna do long division.

Answer 4

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.

Answer 5

Well, I have to answer to my own question. I was reading about Pascal's triangle and by accident noticed that we can calculate the amount of combinations with it:

#include <iostream>
#include <boost/cstdint.hpp>

boost::uint64_t Combinations(unsigned int n, unsigned int r)
{
        if (r > n)
                return 0;

        /** We can use Pascal's triange to determine the amount
          * of combinations. To calculate a single line:
          *
          * v(r) = (n - r) / r
          *
          * Since the triangle is symmetrical, we only need to calculate
          * until r -column.
          */

        boost::uint64_t v = n--;

        for (unsigned int i = 2; i < r + 1; ++i, --n)
                v = v * n / i;

        return v;
}

int main()
{
        std::cout << Combinations(52, 5) << std::endl;
}

Answer 6

If you want to be 100% sure that no overflows occur so long as the final result is within the numeric limit, you can sum up Pascal's Triangle row-by-row:

for (int i=0; i<n; i++) {
    for (int j=0; j<=i; j++) {
        if (j == 0) current_row[j] = 1;
        else current_row[j] = prev_row[j] + prev_row[j-1];
    }
    prev_row = current_row; // assume they are vectors
}
// result is now in current_row[r-1]

However, this algorithm is much slower than the multiplication one. So perhaps you could use multiplication to generate all the cases you know that are 'safe' and then use addition from there. (.. or you could just use a BigInt library).