Generate all combinations from multiple lists

Question

Given an unknown amount of lists, each with an unknown length, I need to generate a singular list with all possible unique combinations. For example, given the following lists:

X: [A, B, C] 
Y: [W, X, Y, Z]

Then I should be able to generate 12 combinations:

[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

If a third list of 3 elements were added, I'd have 36 combinations, and so forth.

Any ideas on how I can do this in Java?
(pseudo code would be fine too)

Answer 1

You need recursion:

Let's say all your lists are in lists, which is a list of lists. Let result be the list of your required permutations. You could implement it like this:

void generatePermutations(List<List<Character>> lists, List<String> result, int depth, String current) {
    if (depth == lists.size()) {
        result.add(current);
        return;
    }

    for (int i = 0; i < lists.get(depth).size(); i++) {
        generatePermutations(lists, result, depth + 1, current + lists.get(depth).get(i));
    }
}

The ultimate call will be like this:

generatePermutations(lists, result, 0, "");