Michael Hillman Michael Hillman - 3 months ago 38
Java Question

Generate all combinations from multiple lists

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

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: Do 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, EmptyString);
Comments