Search code examples
c++algorithmcombinatoricsfactorial

C++: Combination/multiset functions (factorial overflow)

I must implement a problem that computes combinations and multisets of m elements from a set of n elements. The formulas for them are the following ones:

enter image description here

enter image description here

The problem is that with factorial it is easy to overflow, so basically what solutions can be for this problem?

Since it is a subproblem of a problem in TopCoder, I have following constraints:

1) A program must be written in C++.

2) I cannot load external libraries.

Solution

  • You don't really need to calculate n! directly, which may easily get overflowed. Since 

    C(n,m) = C(n-1, m-1) + C(n-1,m)
C(n,0) = C(n,n) =1

    You can build a table with size (n+1,m+1) and use dynamic programming to build up the table in bottom up manner.

    Algorithm pseudocode may like the following:

    for i ← 0 to n do  // fill out the table row wise
      for j = 0 to min(i, m) do
          if j==0 or j==i then C[i, j] ← 1 
          else C[i, j] ← C[i-1, j-1] + C[i-1, j] 
return C[n, m]

    If you declare c(n,m) to be long double and n is not that big, this way should work. Otherwise, you need to define your own BigInteger class to avoid overflow and define how the + operator works for BigIntegers, which are usually represented as array of chars or string.