I have to evaluate the following formula for permutations with repeated objects
n!/(r1! * r2! * r3! * ......... * rn!)
wheren <= 500
and 1 <= ri <= 10
(there are n objects in total out of which r1 are alike of 1 kind , r2 are alike of 2nd kind and so on and the formula indicates the number of permutations of such objects).
I need an efficient coding solution for this because working with big integers in Java doesn't prove to be fruitful for large cases.
Thanks in advance.
n <= 500
, it's very possible to build an array of sizen
. Use the Sieve of Eratosthenes to find and store pairs of factors for all non-prime numbers up ton
. Make another table of sizen
which represents the exponent of each factor. Now, iterate each factorial. Break each factor into prime factors using the sieve table, incrementing the exponent table for the factorial in the numerator and decrementing it for each factorial in the denominator. No entry will ever end up negative.BigInteger
-type class to multiply together the non-cancelled factors. No division operations are required at any point. Nor any fractions.