A common interview problem for programming is to generate all of the possible locker numbers without repeats.

This is a little silly in the physical world… but the basic idea is:
– You have the numbers 0-9 (so, 10 numbers).
– You can choose any of the 10 for digit 1.
– You can choose any of the remaining 9 for digit 2.
– And the pattern continues.

So, this is a combinations problem… how many ways can you choose N numbers out of 10 numbers?

Calculating it Directly

• Basically, its a limited factorial.
• If N = 4, we have 10 options for #1, 9 for #2, 8 for #3 and 7 for #4 = 10 * 9 * 8 * 7 = 5,040 combinations.

Listing and Counting Them in Java

This problem can be expressed very easily and directly in a functional manner. In this case, that means that we continually build up our solutions immutably, as opposed to, say, trying to keep a character array that we modify as we go.

public class LockerNumberNoRepeats {
    public static void main(String[] args) {
        System.out.println("Total combinations = " +
            permutations(4));
    }

    public static int permutations(int targetLength) {
        return permutations("", "0123456789", targetLength);
    }

    private static int permutations(String c, String r,
            int targetLength) {

        //Print the result if we've reached a full locker
        //combo of the target length.  Also, return 1 so we
        //can sum up all found combinations.
        if (c.length() == targetLength) {
            System.out.println(c);
            return 1;
        }

        //Use sum to count all the permutations we see.  Also
        //cycle through all remaining letters (r) and add each
        //to our current string (c).  Then recursively call this
        //function to continue.
        int sum = 0;
        for (int i = 0; i < r.length(); ++i) {
            sum += permutations(c + r.charAt(i),
                r.substring(0,i) + r.substring(i + 1),
                targetLength);
        }
        return sum;
    }
}

Output

9874
9875
9876
Total combinations = 5040