Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.math.BigInteger;
- public class Question2858152 {
- final static int ncharacters = 256;
- final static int nsymbols = 256;
- final static int max = Math.max (nsymbols,ncharacters) + 1;
- final static BigInteger [] integers = new BigInteger [max];
- final static BigInteger [] powers = new BigInteger [max];
- final static BigInteger [] factorials = new BigInteger [max];
- static BigInteger maxEntropy = BigInteger.TWO.pow (nsymbols);
- static BigInteger permutationCount = BigInteger.ZERO;
- static BigInteger combinationCount = BigInteger.ZERO;
- static BigInteger fileCount = BigInteger.ZERO;
- public static void main (String [] args) {
- factorials [0] = BigInteger.ONE;
- for (int i = 1;i < max;i++) {
- integers [i] = BigInteger.valueOf (i);
- powers [i] = integers [i].pow (i);
- factorials [i] = factorials [i - 1].multiply (integers [i]);
- }
- recurse (BigInteger.ONE,ncharacters,factorials [nsymbols],factorials [ncharacters],nsymbols,ncharacters,"");
- System.out.println (combinationCount + " combinations");
- System.out.println (permutationCount + " permutations");
- System.out.println (fileCount + " files");
- int precision = 100000000;
- BigInteger nfiles = integers [nsymbols].pow (ncharacters);
- System.out.println (fileCount.multiply (BigInteger.valueOf (precision)).add (nfiles.divide (BigInteger.TWO)).divide (nfiles).doubleValue () / precision);
- }
- static long time = System.currentTimeMillis ();
- static void recurse (BigInteger entropy,int frequency,BigInteger symbolMultiplicity,BigInteger characterMultiplicity,int symbolsLeft,int charactersLeft,String prefix) {
- if (frequency == 1) {
- symbolMultiplicity = symbolMultiplicity.divide (factorials [charactersLeft]).divide (factorials [symbolsLeft - charactersLeft]);
- combinationCount = combinationCount.add (BigInteger.ONE);
- permutationCount = permutationCount.add (symbolMultiplicity);
- fileCount = fileCount.add (symbolMultiplicity.multiply (characterMultiplicity));
- }
- else
- for (int f = 0;charactersLeft >= 0;f++,charactersLeft -= frequency) {
- if (entropy.compareTo (maxEntropy) <= 0)
- recurse (entropy,frequency - 1,symbolMultiplicity.divide (factorials [f]),characterMultiplicity,symbolsLeft - f,charactersLeft,prefix + " ");
- else
- break;
- if (f == 0 && symbolsLeft == nsymbols) {
- long now = System.currentTimeMillis ();
- System.out.println ("done with maximal frequency " + frequency + " (" + (now - time) / 1000 + " seconds)");
- time = now;
- }
- entropy = entropy.multiply (powers [frequency]);
- characterMultiplicity = characterMultiplicity.divide (factorials [frequency]);
- }
- }
- }
Add Comment
Please, Sign In to add comment