Permutation with Repetition: Avoiding Overflow

Question

Background:

Given n balls such that:

'a' balls are of colour GREEN
'b' balls are of colour BLUE
'c' balls are of colour RED
...

(of course a + b + c + ... = n)

The number of permutations in which these balls can be arranged is given by:

perm = n! / (a! b! c! ..)

Question 1: How can I 'elegantly' calculate perm so as to avoid an integer overflow as as long as possible, and be sure that when I am done calculating, I either have the correct value of perm, or I know that the final result will overflow?

Basically, I want to avoid using something like GNU GMP.

Optionally, Question 2: Is this a really bad idea, and should I just go ahead and use GMP?

Answer 1

These are known as the multinomial coefficients, which I shall denote by m(a,b,...).

And you can efficiently calculate them avoiding overflow by exploiting this identity (which should be fairly simple to prove):

m(a,b,c,...) = m(a-1,b,c,...) + m(a,b-1,c,...) + m(a,b,c-1,...) + ...
m(0,0,0,...) = 1 // base case
m(anything negative) = 0 // base case 2

Then it's a simple matter of using recursion to calculate the coefficients. Note that to avoid an exponential running time, you need to either cache your results (to avoid recomputation) or use dynamic programming.

To check for overflow, just make sure the sums won't overflow.

And yes, it's a very bad idea to use arbitrary precision libraries to do this simple task.

Answer 2

If you have globs of cpu time, you can make lists out of all the factorials, then find the prime factorization of all the numbers in the lists, then cancel all the numbers on the top with those on the bottom, until the numbers are completely reduced.