2

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.

7
  • I coded it naively by evaluating the factorials through normal multiplication using BigIntegers and the dividing but the program hangs on boundary cases that is why I need it :( :( Feb 2, 2012 at 5:39
  • 1
    Well, there are LOTS of opportunities for reducing this fraction.
    – Ben Voigt
    Feb 2, 2012 at 5:43
  • I'd try the C library gmp (gmplib.org).
    – madth3
    Feb 2, 2012 at 5:43
  • I was asked to expand on my suggestion of how to reduce the fraction, so here goes. Since n <= 500, it's very possible to build an array of size n. Use the Sieve of Eratosthenes to find and store pairs of factors for all non-prime numbers up to n. Make another table of size n 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.
    – Ben Voigt
    Feb 2, 2012 at 6:01
  • Now, use a BigInteger-type class to multiply together the non-cancelled factors. No division operations are required at any point. Nor any fractions.
    – Ben Voigt
    Feb 2, 2012 at 6:01

1 Answer 1

2

You can do this in java by using

public class Permutation

designed to achieve a kind of your problem.

See this link for your reference

OR

like this :

private static Double calculatePermutationEntropy(List<Double> values, int baseOrder) {
 int valuesSize = values.size();
 if (baseOrder >= valuesSize + 1) {
   throw new RuntimeException("The size of the values is bigger than the order");
 }

 List<String> result = new ArrayList<String>();
 // iterate over the input
 for (int i = 0; i < valuesSize - baseOrder + 1; i++) {
   List<Double> neightbors = values.subList(i, i + baseOrder);

   List<Double> orderedValues = new ArrayList<Double>(neightbors);

   String window = "";
   for (int j = 0; j < neightbors.size(); j++) {
     // add the indexes in a string representation
     window += orderedValues.indexOf(neightbors.get(j));
   }
 result.add(window);
 }
 // use the shannon entropy calculation to get the result
 return calculateShannonEntropy(result);
}

source

3
  • can you explain what you have written Feb 2, 2012 at 5:49
  • Have you visited the links i have specified ??
    – Ved
    Feb 2, 2012 at 5:50
  • There should be no fractions in a number-of-combinations problem. Therefore no reason to use double.
    – Ben Voigt
    Feb 2, 2012 at 6:02

Not the answer you're looking for? Browse other questions tagged or ask your own question.