1
\$\begingroup\$

This is one result of my work on Project Euler to learn Java. I'm interested in how well this conforms to best practices as well as any recommendations on efficiency. (I'm pretty sure this code is a lot more efficient than it is readable, but it's not deliberately obfuscated, I swear! :) )

import java.util.ArrayList;
import java.util.Arrays;


public class Combinatorics {
    private static ArrayList<Long> factorialList = new ArrayList<Long>(Arrays.asList(1L,1L));

    public static long factorial(int n) {
        if (n < 0) {
            return -1L;
        } else if (n < factorialList.size()) {
            return factorialList.get(n);
        } else {
            int currSize = factorialList.size();
            long currNum = factorialList.get(currSize - 1);
            while (currSize <= n) {
                currNum *= currSize;
                factorialList.add(currNum);
                currSize++;
            }
            return currNum;
        }
    }

    public static boolean factNisLessThanK(int n, long k) {
        if (n < 0) return false;
        if (n < factorialList.size()) return (factorialList.get(n) < k);

        int currSize = factorialList.size();
        long currNum = factorialList.get(currSize - 1);
        while (currSize <= n) {
            currNum *= currSize;
            factorialList.add(currNum);
            currSize++;
            if (currNum >= k) return false;
        }
        return true;
    }

    public static int[] lexicographicPermutation(int digits, long rank) {
        if ((rank < 1) || factNisLessThanK(digits, rank)) {
            int result[] = {-1};
            return result;
            //return "Error";
        }
        rank--;        //using 0 based ranking makes the math easier.
        int result[] = new int[digits];
        int index = 0;
        while (index < result.length) {
            result[index] = (int) (rank / factorial(digits - 1));
            rank %= factorial(digits - 1);
            index++;
            digits--;
        }
        for (int i = result.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < result.length; j++) {
                if (result[j] >= result[i]) result[j]++;
            }
        }
        //return Arrays.toString(result);
        return result;
    }
}

The key to this whole program (actually, class) is the last method: lexicographicPermutation, which returns an int array containing the rankth permutation of a set of digits numbers—the numbers 0 through digits-1, in fact.

So, for example

System.out.println(Arrays.toString(Combinatorics.lexicographicPermutation(4, 11L)));

Prints [1, 3, 0, 2] because:

permutation 1: 0123
permutation 2: 0132
permutation 3: 0213
permutation 4: 0231
permutation 5: 0312
permutation 6: 0321
permutation 7: 1023
permutation 8: 1032
permutation 9: 1203
permutation 10: 1230
permutation 11: 1302

The code also includes a memoized factorial method and a factNisLessThanK method which lazily extends the factorial list only as much as needed to give the answer. So a call like factNisLessThanK(17, 100L) would only compute up to 5! before returning false (since 5! = 120) instead of computing up to 17!

(I used it to solve Project Euler problem 24, calling lexicographicPermutation(10, 1000000L).)

https://projecteuler.net/problem=24

\$\endgroup\$
1
\$\begingroup\$

This is nicely written, readable and efficient.


The most significant improvement I can suggest is to rewrite this as a for loop:

int index = 0;
while (index < result.length) {
    result[index] = (int) (rank / factorial(digits - 1));
    rank %= factorial(digits - 1);
    index++;
    digits--;
}

Because this is essentially a counting loop, and index is not needed outside of it anyway. That is:

for (int index = 0; index < result.length; ++index) {
    result[index] = (int) (rank / factorial(digits - 1));
    rank %= factorial(digits - 1);
    digits--;
}

It's recommended to declare variables using their interfaces, so instead of:

private static ArrayList<Long> factorialList = new ArrayList<Long>(Arrays.asList(1L,1L));

This is better:

private static List<Long> factorialList = new ArrayList<>(Arrays.asList(1L, 1L));

Lastly, a couple of nitpicks:

  • In lexicographicPermutation, int result[] = {-1} is a redundant local variable
  • It's recommended to use braces with single-statement if too
  • There are some redundant parentheses here and there, for example if ((rank < 1) || ...)
\$\endgroup\$
  • \$\begingroup\$ Thanks! That's reassuring indeed given this is one of the first bits of code I ever wrote in Java. :) Good catch on the while loop; I also noticed I can decrement digits at the start for the same reason as decrementing rank. Couple follow ups: (1) When I was writing the code, I tried to return {-1} anonymously for the error condition (i.e. without creating a local variable) and I couldn't figure out how to get the syntax correct to do so. How can I do this? \$\endgroup\$ – Wildcard Oct 24 '15 at 2:35
  • \$\begingroup\$ (2) For braces with single statement if, is it acceptable/good style to keep it all on one line or should the conditionally executed command be on its own line in addition to being in braces? \$\endgroup\$ – Wildcard Oct 24 '15 at 2:35
  • 1
    \$\begingroup\$ The syntax is return new int[]{ -1 }, no shorter way. For the if with braces, yes the body inside the braces should be on its own line. In general, one statement per line is more readable \$\endgroup\$ – janos Oct 24 '15 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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