All possible combinations of 4 lists of strings

Question

So I have 4 list of strings with me:

List<String> a={"abc","def"};
List<String> b={"abc","def"};
List<String> c={"abc","def"};
List<String> d={"abc","def"};

What is the best way to generate all the possible combinations of strings from these 4 lists?

So far, I have implemented this by using very basic code:

for(String i:a) {
    for(String j:b) {
        for(String k:c) {
            for(String l:d) {
                //do work
            }
        }
    }
}

That's not a list of 4 strings, they are just 2. Also, why doesn't the language matter, the solution would be very different depending on which language it is. — Iharob Al Asimi, Jul 01 '15 at 10:54
Do you want the strings from the first list to always appear before strings from the second list, string from the second list to always appear before those of the third etc.? of do you want to generate the combinations where the strings from the other lists appear first as well? — Dor Mesica, Jul 01 '15 at 10:57
...and this is called tag spamming, This indicates, you're essentially asking "gimmetehcodez", which is not likely to be very well-received here. :-) — Sourav Ghosh, Jul 01 '15 at 10:58
So there are 4 lists with any number of strings. Or we can say the number of lists are n and have a solution for it. — Gaurav Arora, Jul 01 '15 at 10:58

score 5 · Answer 1 · answered Jul 01 '15 at 11:03

You could use a recursive approach.

At each step, you deal with one list only, "guess" which element to add to the so far solution, and recurse on a "smaller" problem, with one fewer list:

public static <T> void getCombination(List<T>... lists) {
    if (lists == null) return;
    getCombinations(new ArrayList<T>(), 0, lists);
}
private static <T> void getCombinations(List<T> soFar, int i, List<T> ... lists) {
    if (i == lists.length) { //no more lists left:
        //do work on soFar, for example:
        System.out.println(soFar);
    }
    else { 
        for (T t : lists[i]) {
            soFar.add(t); //"guess" item
            getCombinations(soFar, i+1, lists); //recurse on rest of lists
            soFar.remove(soFar.size()-1); //cleanup
        }
    }
}

Invoke the above with:

public static void main(String args[]) {
    List<String> a= Arrays.asList("abc","def");
    List<String> b= Arrays.asList("abc","def");
    List<String> c=Arrays.asList("abc","def");
    List<String> d=Arrays.asList("abc","def");
    getCombination(a,b,c,d);
}

and you will get:

[abc, abc, abc, abc]
[abc, abc, abc, def]
[abc, abc, def, abc]
[abc, abc, def, def]
[abc, def, abc, abc]
[abc, def, abc, def]
[abc, def, def, abc]
[abc, def, def, def]
[def, abc, abc, abc]
[def, abc, abc, def]
[def, abc, def, abc]
[def, abc, def, def]
[def, def, abc, abc]
[def, def, abc, def]
[def, def, def, abc]
[def, def, def, def]

This approach can handle any number of such lists, and the lists can be of any size, but be advised that the size of the solution (and running time) is exponential in the number of lists, but that's to be expected, since any solution that will try to path through all combinations will have to go through exponential number of such.

All possible combinations of 4 lists of strings

1 Answers1