How to iterate all combinations of List>

Question

I have a List<List<T>> the length of both list dimensions varies.
Using recursion I can calculate all the combinations

Some example List<List<T>> and their combinations

[
 [1],
 [2, 3],
 [4, 5, 6]
] 
// [1, 2, 4], [1, 2, 5], [1, 2, 6], [1, 3, 4], [1, 3, 5], [1, 3, 6]

[ 
 [0, 4],
 [3, 4, 1, 2]
]
// [0, 3], [0, 4], [0, 1], [0, 2], [4, 3], [4, 4], [4, 1], [4, 2]

[ 
 ["A", "B", "B"],
 ["C"]
]
// ["A", "C"], ["B", "C"], ["B, "C"]

The amount of combinations can grow rapidly and using recursion becomes a memory and performance issue.
How can I implement an iterator to iterate through the combinations as they are calculated?

Doing some reading I might be able to use a factorial or combinatorial number system, but im not sure how I would apply it in this situation.

Answer 1

You could implement an Iterator<List<T>> that only holds a reference to the original elements as a list of lists and the current positions for each sub-list, generating new combinations as needed:

class Combinations<T> implements Iterator<List<T>> {

    final List<List<T>> elements;
    final int[] indices;

    public Combinations(List<List<T>> elements) {
        this.elements = elements;
        this.indices = new int[elements.size()];
    }

    @Override
    public boolean hasNext() {
        // has first index not yet reached max position?
        return indices[0] < elements.get(0).size();
    }

    @Override
    public List<T> next() {
        // get next
        List<T> result = new ArrayList<>(indices.length);
        for (int i = 0; i < indices.length; i++) {
            result.add(elements.get(i).get(indices[i]));
        }
        // increase indices
        for (int i = indices.length - 1; i >= 0; i--) {
            indices[i]++;
            if (indices[i] >= elements.get(i).size() && i > 0) {
                indices[i] %= elements.get(i).size();
            } else {
                break;
            }
        }
        return result;
    }
}

The part to increase the indices is a bit tricky. I guess that's the part where the factorial numbering system comes into play, as you basically have to "+1" a number (the combined indices) where each digit has a different base (the number of elements in the respective sublists). But you can just as well do it with a simple loop, without using any special libraries.

I tried this for your examples and it seems to work:

List<List<Integer>> elements = Arrays.asList(Arrays.asList(1), Arrays.asList(2, 3), Arrays.asList(4, 5, 6));
Iterator<List<Integer>> combinations = new Combinations<>(elements);
combinations.forEachRemaining(System.out::println);

Output:

[1, 2, 4]
[1, 2, 5]
[1, 2, 6]
[1, 3, 4]
[1, 3, 5]
[1, 3, 6]

Note: This uses a List<List<T>> instead of List<Set<T>> because you need to index into the nested collections, but you could easily change it to accept List<Collection<T>> and convert to List in the constructor.

Answer 2

Editing this answer to work for List<List<T>>. tobias_k's answer uses an iterator to get the next combination by iterating over the indices of the lists. This does something similar, without an iterator-based approach. The idea I followed was:

     * List 1: [1 2]
     * List 2: [4 5]
     * List 3: [6 7]
     * 
     * Take each element from list 1 and put each element 
     * in a separate list.
     * combinations -> [ [1] [2] ]
     * 
     * Set up something called newCombinations that will contains a list
     * of list of integers
     * Consider [1], then [2]
     * 
     * Now, take the next list [4 5] and iterate over integers
     * [1]
     *  add 4   -> [1 4]
     *      add to newCombinations -> [ [1 4] ]
     *  add 5   -> [1 5]
     *      add to newCombinations -> [ [1 4] [1 5] ]
     * 
     * [2]
     *  add 4   -> [2 4]
     *      add to newCombinations -> [ [1 4] [1 5] [2 4] ]
     *  add 5   -> [2 5]
     *      add to newCombinations -> [ [1 4] [1 5] [2 4] [2 5] ]
     * 
     * point combinations to newCombinations
     * combinations now looks like -> [ [1 4] [1 5] [2 4] [2 5] ]
     * Now, take the next list [6 7] and iterate over integers
     *  ....
     *  6 will go into each of the lists
     *      [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] ]
     *  7 will go into each of the lists
     *      [ [1 4 6] [1 5 6] [2 4 6] [2 5 6] [1 4 7] [1 5 7] [2 4 7] [2 5 7]]

Now the code. I used a Set simply to get rid of any duplicates. Can be replaced with a List. Everything should work seamlessly. :)

public static <T> Set<List<T>> getCombinations(List<List<T>> lists) {
    Set<List<T>> combinations = new HashSet<List<T>>();
    Set<List<T>> newCombinations;

    int index = 0;

    // extract each of the integers in the first list
    // and add each to ints as a new list
    for(T i: lists.get(0)) {
        List<T> newList = new ArrayList<T>();
        newList.add(i);
        combinations.add(newList);
    }
    index++;
    while(index < lists.size()) {
        List<T> nextList = lists.get(index);
        newCombinations = new HashSet<List<T>>();
        for(List<T> first: combinations) {
            for(T second: nextList) {
                List<T> newList = new ArrayList<T>();
                newList.addAll(first);
                newList.add(second);
                newCombinations.add(newList);
            }
        }
        combinations = newCombinations;

        index++;
    }

    return combinations;
}

A little test block..

public static void main(String[] args) {
    List<Integer> l1 = Arrays.asList(1,2,3);
    List<Integer> l2 = Arrays.asList(4,5);
    List<Integer> l3 = Arrays.asList(6,7);

    List<List<Integer>> lists = new ArrayList<List<Integer>>();
    lists.add(l1);
    lists.add(l2);
    lists.add(l3);

    Set<List<Integer>> combs = getCombinations(lists);
    for(List<Integer> list : combs) {
        System.out.println(list.toString());
    }

}