CODEWITHSUNDEEP
coverflowpermutationinteger-overflow
ArjunShankar
ArjunShankar

Reputation: 23680

Permutation with Repetition: Avoiding Overflow

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?

Upvotes: 7

Views: 1144

Answers (5)

Mihai Manole
Mihai Manole

Reputation: 195

Notations: n! = prod(1,n) where prod you may guess what does.

It's very easy, but first you must know that for any 2 positive integers (i, n > 0) that expression is a positive integer: 

prod(i,i+n-1)/prod(1,n)

Thus the idea is to slice the computation of n! in small chunks and to divide asap.

With a, than with b and so on. 

perm = (a!/a!) * (prod(a+1, a+b)/b!) * ... * (prod(a+b+c+...y+1,n)/z!)

Each of these factors is an integer, so if perm will not overflow, neither one of its factors will do.

Though, in the calculation of a such factor could be an overflow in numerator or denominator but that's avoidable doing a multiplication in numerator then a division in alternance:

prod(a+1, a+b)/b! = (a+1)(a+2)/2*(a+3)/3*..*(a+b)/b

In that way every division will yield an integer.

Upvotes: -2

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

According to this link, you can calculate multinomial coefficients as a product of several binomial coefficients, controlling integer overflow on the way.

This reduces original problem to overflow-controlled computation of a binomial coefficient.

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183888

The overflow-safest way is the way Dave suggested. You find the exponent with which the prime p divides n! by the summation

m = n;
e = 0;
do{
    m /= p;
    e += m;
}while(m > 0);

Subtract the exponents of p in the factorisations of a! etc. Do that for all primes <= n, and you have the factorisation of the multinomial coefficient. That calculation overflows if and only if the final result overflows. But the multinomial coefficients grow rather fast, so you will have overflow already for fairly small n. For substantial calculations, you will need a bignum library (if you don't need exact results, you can get by a bit longer using doubles).

Even if you use a bignum library, it is worthwhile to keep intermediate results from getting too large, so instead of calculating the factorials and dividing huge numbers, it is better to calculate the parts in sequence,

n!/(a! * b! * c! * ...) = n! / (a! * (n-a)!) * (n-a)! / (b! * (n-a-b)!) * ...

and to compute each of these factors, let's take the second for illustration,

(n-a)! / (b! * (n-a-b)!) = \prod_{i = 1}^b (n-a+1-i)/i

is calculated with

prod = 1
for i = 1 to b
    prod = prod * (n-a+1-i)
    prod = prod / i

Finally multiply the parts. This requires n divisions and n + number_of_parts - 1 multiplications, keeping the intermediate results moderately small.

Upvotes: 3

tskuzzy
tskuzzy

Reputation: 36466

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.

Upvotes: 6

Dave
Dave

Reputation: 11162

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.

Upvotes: 5

Related Questions