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

Question

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

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.

Rewrite the explicit term for C(n,m). The one you have in your question is generally the most convenient to work with in theory, but when you actually have to compute it there is one that doesn't overflow as quickly. — us2012, Mar 27 '13 at 19:40

taocp · Accepted Answer · 2013-03-27T19:57:13.667

5

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.

edited Mar 27 '13 at 19:57

answered Mar 27 '13 at 19:46

taocp

23,276
10
49
62

should it be j in the second for as a condition or am i missing a point? – Kudayar Pirimbaev Mar 27 '13 at 19:49
@KudayarPirimbaev sorry, typo, the second loop variable should be j, not i. I updated the code. good catch, thanks! – taocp Mar 27 '13 at 19:50
ok, thanks, can't believe that i haven't figured out this different approach – Kudayar Pirimbaev Mar 27 '13 at 19:53
I like those funky little `←` symbols. – Peter Wood Mar 27 '13 at 20:05

score 0 · Answer 2 · edited May 23 '17 at 11:59

0

Factorials are quite big numbers (they don't fit into a 64 bits word). So you need to use bignums (arbitrary precision arithmetic) to compute them in full. Consider using GMPlib for that purpose (or code in a language and implementation, e.g. Common Lisp with SBCL, which gives them natively)

See also this and that answers to a question very similar to yours.

edited May 23 '17 at 11:59

Community

1
1

answered Mar 27 '13 at 19:25

Basile Starynkevitch

223,805
18
296
547

so what if i can't use external libraries and must write it in c++? since i was writing it in TopCoder, i have some restrictions – Kudayar Pirimbaev Mar 27 '13 at 19:35
@KudayarPirimbaev: TopCoder lets you use C++, Java, C#, and VB at least. 3 of the 4 of those have arbitrary-length integers built into their standard library, if you wanted to go that route. – cHao Mar 27 '13 at 19:57
since i know only c++, i can't simply change language to solve one question, but i know that they are built, thanks, just for extending my scope of programming i have asked with constraints, for learning new things, you know – Kudayar Pirimbaev Mar 27 '13 at 23:41

score 0 · Answer 3 · answered Mar 27 '13 at 19:49

0

Instead of using a recursive approach for calculating factorials which might lead to stack overflow, use iterative approach! This could save you overflow even for larger numbers.

answered Mar 27 '13 at 19:49

Arslan Ali

17,418
8
58
76

3

numbers are overflowing, not stack – Kudayar Pirimbaev Mar 27 '13 at 19:50

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

3 Answers3