Form every unique combination of the items of a list of lists

Question

I've tried looking some stuff up. I thought it was transposition first, but looking at this, that's not exactly it.

I hacked this code together in about 3 hours, stopping frequently due to frustration and I'm pretty sure there's some bad practices in there, I'm just too glad right now I actually got it to work. If anyone could point out a better way of doing this, or a part of it, that would be appreciated.

The idea is you have a variable amount of lists with each a variable amount of items. For instance, lists of String, which I used in my code, which can look like this:

• List1["a","b","c"]
• List2["d"]
• List3["e","f"]

And the result would be:

• List1["a","d","e"]
• List2["a","d","f"]
• List3["b","d","e"]
• List4["b","d","f"]
• List5["c","d","e"]
• List6["c","d","f"]

I left in the sysout statements in case somebody wants to execute it and follow what's happening.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.google.common.collect.Lists;

public class Main {

    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        list1.add("a");
        list1.add("b");
        list1.add("c");

        List<String> list2 = new ArrayList<String>();
        list2.add("d");

        List<String> list3 = new ArrayList<String>();
        list3.add("e");
        list3.add("f");

        List<List<String>> group = Lists.newArrayList(list1,list2,list3);
        System.out.println(Arrays.toString(group.toArray()));

        List<List<String>> end = makeList(group);

        System.out.println(Arrays.toString(end.toArray()));
    }

    /**
     * Take the original list and output all unique combinations.
     * This method is called recursively.
     */
    private static List<List<String>> makeList(List<List<String>> group) {
        if (group.size() == 1) {
            return splitToSingleItemsLists(group.get(0));
        } else {
            List<List<String>> subList = makeList(group.subList(1, group.size()));
            System.out.println(Arrays.toString(subList.toArray()));
            System.out.println(Arrays.toString(group.toArray()));
            System.out.println("=====");
            List<List<String>> tmpList = Lists.newArrayList();

            List<List<String>> splitToSingleItemsLists = splitToSingleItemsLists(group.get(0));
            System.out.println(Arrays.toString(splitToSingleItemsLists.toArray()));
            System.out.println("----");

            List<String> result = new ArrayList<String>();
            for (List<String> string : subList) {
                result = new ArrayList<String>();
                result.addAll(string);
                for (List<String> tmp : splitToSingleItemsLists) {
                    List<String> result2 = new ArrayList<>();
                    result2.addAll(result);
                    for (String tmp2 : tmp) {
                        result2.add(tmp2);

                        tmpList.add(result2);
                    }
                }
            }

            return tmpList;
        }
    }

    /**
     * Split a list of strings to a list of lists with 1 item of the original list each time.
     */
    private static List<List<String>> splitToSingleItemsLists(List<String> list) {
        List<List<String>> result = Lists.newArrayList();

        for (String str : list) {
            List<String> tmp = new ArrayList<String>();
            tmp.add(str);
            result.add(tmp);
        }

        return result;
    }
}

Answer 1

This seems more complicated than it needs to be. Consider the following code

        int currentIndex = current.size();
        for (String s : factors.get(currentIndex)) {
            current.add(s);
            multiply(factors, current, results);
            current.remove(currentIndex);
        }

This code adds and removes an element to the current list. In between, it calls itself recursively. Then consider

        if (current.size() >= factors.size()) {
            // Don't really need to make a deeper copy with String values
            // but might as well in case we change types later.
            List<String> result = new ArrayList<>();
            for (String s : current) {
                result.add(new String(s));
            }
            results.add(result);

            return;
        }

When we find that we've processed an entire result, we add to the results and return.

Note that we could optimize that a bit by switching from a deep copy to a shallow copy. With strings, that shouldn't make a difference. I did the deep copy because we aren't restricted to strings with this kind of operation.

        if (current.size() >= factors.size()) {
            results.add(new ArrayList<>(current));

            return;
        }

That's the shallow version.

The whole thing:

    private static void multiply(List<List<String>> factors, List<String> current, List<List<String>> results) {
        if (current.size() >= factors.size()) {
            // Don't really need to make a deeper copy with String values
            // but might as well in case we change types later.
            List<String> result = new ArrayList<>();
            for (String s : current) {
                result.add(new String(s));
            }
            results.add(result);

            return;
        }

        int currentIndex = current.size();
        for (String s : factors.get(currentIndex)) {
            current.add(s);
            multiply(factors, current, results);
            current.remove(currentIndex);
        }
    }

    private static List<List<String>> multiply(List<List<String>> factors) {
        List<List<String>> results = new ArrayList<>();
        multiply(factors, new ArrayList<String>(), results);
        return results;
    }

I added the second method so that I could call it like

        System.out.println(Arrays.toString(multiply(group).toArray()));

Otherwise I would have needed to use more lines in the caller.

This version outputs the products in the same order as shown in your question, where your code outputs them in reverse order. I don't know if this matters or not.

I find this to be more straightforward than your version. It builds up to the answer. Your version builds the answer on its way back from the recursion, which is why the results are backwards.

It also avoids some things that I didn't like about your version:

            for (List<String> string : subList) {

I'm not sure exactly what it is, but it's not a string. It's a List. I'd have probably called it something like strings or pieces in lieu of a better name.

                        result2.add(tmp2);

I'm not a fan of numbered variables. I find it especially confusing here, as result and result2 are the same type but tmp and tmp2 are not.

I'm not crazy about your use of tmp for a loop index variable. It seems like there should have been a better name. That variable is no more temporary than any other.

            List<String> result = new ArrayList<String>();
            for (List<String> string : subList) {
                result = new ArrayList<String>();

You could just say

            for (List<String> string : subList) {
                List<String> result = new ArrayList<>();

The first initialization doesn't do anything before it is overwritten and result is never used beyond a single loop iteration.