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.

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
AnkitSablok
  • 3,021
  • 7
  • 35
  • 52
  • 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 :( :( – AnkitSablok Feb 02 '12 at 05:39
  • 1
    Well, there are LOTS of opportunities for reducing this fraction. – Ben Voigt Feb 02 '12 at 05:43
  • I'd try the C library gmp (http://gmplib.org/). – madth3 Feb 02 '12 at 05: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 02 '12 at 06: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 02 '12 at 06:01
  • (That was supposed to be an answer, but the question got closed) – Ben Voigt Feb 02 '12 at 06:02
  • Demonstration of my method: http://ideone.com/Weeg6 – Ben Voigt Feb 02 '12 at 06:40

1 Answers1

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

Ved
  • 8,577
  • 7
  • 36
  • 69