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