Find permutation of a specified lexicographic rank

Question

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

Answer 1

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) || ...)