List of all possible combinations with unique element from each list without duplicate elements

Question

Suppose I have a list of n lists of string:

For instance when n = 3

list1 = ["M","G"]; 

list2 = ["VP","P"];

list3 = ["E"]

The output must be a list of all possible combinations with the constraint that each combination must contain one element from each list.

The output of the same example above must be:

2*2*1 = 4 combinations with each combination must contain 3 string exactly (one from each input list).

lists= [ ["M","VP","E"], ["M","P","E"], ["G","VP","E"], ["G","P","E"] ]

I have tried a recursive function but what I noticed is that the current list below can't keep the old version during the recursivity:

lists -> contains all input lists (E.g., list1, list2, and list3)

result -> contains all output lists (all combinations)

current -> is the current combination

public static void combination(ArrayList<ArrayList<String>> lists, ArrayList<ArrayList<String>> result, ArrayList<String> current, int k){
    if(k==lists.size()){
        result.add(current);
        current = new ArrayList<String>();
        System.out.println("(if) || k="+k+" || current"+current);
        return;
    }
    for(int t=0;t<lists.get(k).size();t++){
        current.add(lists.get(k).get(t));
        System.out.println("(for) || k="+k+" || current"+current);
        combination(lists, result, current, k+1);
    }
}

The output of this function when called with the same example above:

public static void main(String[] args){
    ArrayList<String> l1 = new ArrayList<String>();l1.add("M");l1.add("G");
    ArrayList<String> l2 = new ArrayList<String>();l2.add("VP");l2.add("P");
    ArrayList<String> l3 = new ArrayList<String>();l3.add("E");
    ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
    ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    ArrayList<String> current = new ArrayList<String>();

    lists.add(l1);lists.add(l2);lists.add(l3);
    combination(lists, result, current, 0);

    for(int i=0;i<result.size();i++){
        System.out.println(result.get(i));
    }

}

The output is:

(for) || k=0 || current[M]

(for) || k=1 || current[M, VP]

(for) || k=2 || current[M, VP, E]

(if) || k=3 || current[]

(for) || k=1 || current[M, VP, E, P]

(for) || k=2 || current[M, VP, E, P, E]

(if) || k=3 || current[]

(for) || k=0 || current[M, VP, E, P, E, G]

(for) || k=1 || current[M, VP, E, P, E, G, VP]

(for) || k=2 || current[M, VP, E, P, E, G, VP, E]

(if) || k=3 || current[]

(for) || k=1 || current[M, VP, E, P, E, G, VP, E, P]

(for) || k=2 || current[M, VP, E, P, E, G, VP, E, P, E]

(if) || k=3 || current[]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

[M, VP, E, P, E, G, VP, E, P, E]

For instance:

This line : (for) || k=1 || current[M, VP, E, P] must be : (for) || k=1 || current[M, VP]

But current doesn't keep its old version inside the recursive function that called it.

You're not dealing with the fact that Java is always [pass-by-value](https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value). When you do `current = new ArrayList();` you're not modifying the `current` list of the previous recursive call, but only the value of the "current" list inside the method. — Narmer, Dec 01 '17 at 10:39
Have a look here: https://stackoverflow.com/questions/17192796/generate-all-combinations-from-multiple-lists — diginoise, Dec 01 '17 at 11:00

score 0 · Answer 1 · answered Dec 01 '17 at 11:16

An alternative approach, maybe much easier:

public static List<List<String>> combination(List<List<String>> lists){
    if (lists.size() == 1) {
        return lists;
    } else {
        List<List<String>> subcombs = combination(lists.subList(1, lists.size()));
        List<List<String>> result = new ArrayList<>();
        for (String s : lists.get(0)) {
            for (List<String> subcomb : subcombs) {
                List<String> list = new ArrayList<>();
                list.add(s);
                list.addAll(subcomb);
                result.add(list);
            }
        }
        return result;
    }
}

public static void main(String[] args){
    List<String> l1 = Arrays.asList("M", "G");
    List<String> l2 = Arrays.asList("VP", "P");
    List<String> l3 = Arrays.asList("E");
    System.out.println(combination(Arrays.asList(l1, l2, l3)));
    // Output: [[M, VP, E], [M, P, E], [G, VP, E], [G, P, E]]
}

On each recursive step just calculate the sub-combinations and prepend each string of the current list

Your approach is not working in the case of 4 lists for instance! — mc7alazoun, Dec 02 '17 at 22:01
Are you sure about that? It should work for any number of lists, it is not specific to 3 lists... can you provide a test case where my approach doesn’t work? — Oneiros, Dec 03 '17 at 20:36

DavidPi · Answer 2 · 2017-12-04T10:34:00.543

I think this 2 methods can do the job:

public static void main(String[] args) {

    List<String> list1 = Arrays.asList("M,G".split(","));
    List<String> list2 = Arrays.asList("VP,P".split(","));
    List<String> list3 = Arrays.asList("E".split(""));

    List<List<String>> mainList = new ArrayList<>();

    mainList.add(list1);
    mainList.add(list2);
    mainList.add(list3);

    combination(mainList, new ArrayList<>());
}

public static void combination(List<List<String>> remainingListsToUse, ArrayList<String> current)
{
    if(remainingListsToUse.isEmpty())
    {
        System.out.println(current.toString());
        return;
    }

    for(List<String> remainingListToUse : remainingListsToUse)
    {
        List<List<String>> listsToKeepGoingWith = new ArrayList<>();
        listsToKeepGoingWith.addAll(remainingListsToUse);
        listsToKeepGoingWith.remove(remainingListToUse);

        remainingListToUse.forEach(listUsed->{
            ArrayList<String> newCurrent = new ArrayList<>();
            newCurrent.addAll(current);
            newCurrent.add(listUsed);
            combination(listsToKeepGoingWith, newCurrent);
        });
    }
}

I considered that the different lists can be permutted...

Here is the result:

 [M, VP, E] 
 [M, P, E]
 [M, E, VP]
 [M, E, P]
 [G, VP, E]
 [G, P, E]
 [G, E, VP]
 [G, E, P]
 [VP, M, E]
 [VP, G, E]
 [VP, E, M]
 [VP, E, G]
 [P, M, E]
 [P, G, E]
 [P, E, M]
 [P, E, G]
 [E, M, VP]
 [E, M, P]
 [E, G, VP]
 [E, G, P]
 [E, VP, M]
 [E, VP, G]
 [E, P, M]
 [E, P, G]

Hope it will help you ! :)

EDIT:

If order and unicity maters you may prefer this method:

public static void combination(List<List<String>> remainingListsToUse, ArrayList<String> current)
{
    // If all the lists have been used
    if(remainingListsToUse.isEmpty())
    {
        System.out.println(current.toString());
        return;
    }

    if(!remainingListsToUse.isEmpty())
    {
        List<String> listCurrentlyUsed = remainingListsToUse.get(0);
        List<List<String>> newRemainingListToUse = new ArrayList<>();
        newRemainingListToUse.addAll(remainingListsToUse);
        newRemainingListToUse.remove(listCurrentlyUsed);

        listCurrentlyUsed.forEach(listElementUsed->{
            ArrayList<String> newCurrent = new ArrayList<>();
            newCurrent.addAll(current);
            newCurrent.add(listElementUsed);
            combination(newRemainingListToUse, newCurrent);
        });
    }
}

It gives this as a result:

[M, VP, E]
[M, P, E]
[G, VP, E]
[G, P, E]

This is not what I was asking for because order and unicity are important constraints in my case. — mc7alazoun, Dec 02 '17 at 22:00
Ok, I didn't know. I'll take time to correct my answer later :) — DavidPi, Dec 04 '17 at 10:16

List of all possible combinations with unique element from each list without duplicate elements

2 Answers2