Generate all combinations from multiple lists

Question

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)

Spermatogonium

It wasn't, I had a momentary brain-lapse at work so instead of taking ages figuring this out on my own, I came here :) – Spermatogonium

If you talk about all the possible unique combinations, shouldn't there be more? For example, a unique combination that you have not reported in your final list is [A].. so it should be [A, B, C, W, X, Y, Z, AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ] – Sophia

Answer 1

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. You could implement 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, "");

Fere

It was mostly javaish. I removed the String.add and String.removeLastCharacter but in doing so changed your logic slightly (for the better hopefully). Feel free to revert. – Rainie

After a little editing so that it'd work with Lists of Doubles (I used Strings in my question as I thought it my be easier to explain), this worked perfectly, Thanks! – Spermatogonium

@armen tsirunyan would it be difficult to modify this to generate a list of lists result like : [[A,W],[A,X],[A,Y]] ? – Amino

@turbo2oh: It would require a trivial modification to the program, just add commas and brackets wherever you want. – Fere

It was being tested : with 2, 3 and 4 lists of Strings, it worked pretty fine...thanks a lot ! – Grandiloquent

This is a pretty clean elegant solution :) I like it! – Penetration

Answer 2

This operation is called cartesian product. Guava provides an utility function for that: Lists.cartesianProduct

Therontheropod

using a library is always better than reinventing the wheel. – Independency

this is so helpful. – Shieh

Answer 3

This topic came in handy. I've rewritten the previous solution fully in Java and more user friendly. Furthermore, I use collections and generics for more flexibility:

/**
 * Combines several collections of elements and create permutations of all of them, taking one element from each
 * collection, and keeping the same order in resultant lists as the one in original list of collections.
 * 
 * <ul>Example
 * <li>Input  = { {a,b,c} , {1,2,3,4} }</li>
 * <li>Output = { {a,1} , {a,2} , {a,3} , {a,4} , {b,1} , {b,2} , {b,3} , {b,4} , {c,1} , {c,2} , {c,3} , {c,4} }</li>
 * </ul>
 * 
 * @param collections Original list of collections which elements have to be combined.
 * @return Resultant collection of lists with all permutations of original list.
 */
public static <T> Collection<List<T>> permutations(List<Collection<T>> collections) {
  if (collections == null || collections.isEmpty()) {
    return Collections.emptyList();
  } else {
    Collection<List<T>> res = Lists.newLinkedList();
    permutationsImpl(collections, res, 0, new LinkedList<T>());
    return res;
  }
}

/** Recursive implementation for {@link #permutations(List, Collection)} */
private static <T> void permutationsImpl(List<Collection<T>> ori, Collection<List<T>> res, int d, List<T> current) {
  // if depth equals number of original collections, final reached, add and return
  if (d == ori.size()) {
    res.add(current);
    return;
  }

  // iterate from current collection and copy 'current' element N times, one for each element
  Collection<T> currentCollection = ori.get(d);
  for (T element : currentCollection) {
    List<T> copy = Lists.newLinkedList(current);
    copy.add(element);
    permutationsImpl(ori, res, d + 1, copy);
  }
}

I'm using guava library for collections creation.

Lanny

This code helps me a lot. I appreciate it, but can I know why you are using Lists.newLinkedList instead of List<T> copy = new LinkedList<>(); is this version anymore efficient. I still see the way I wrote above used more commonly. – Titi

The diamond operator was not available in the JDK version that I used at that time, so I used those factory classes (such as Lists, Sets or Maps) just for convenience and clarity of the code. They are not more efficient or anything like that. – Jacklight

Answer 4

Adding an iterator based answer to work for generic list of lists List<List<T>>, extending the idea from Ruslan Ostafiichuk's answer. 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());
    }
}

Prescott

Answer 5

Without recursion unique combinations:

String sArray[] = new String[]{"A", "A", "B", "C"};
//convert array to list
List<String> list1 = Arrays.asList(sArray);
List<String> list2 = Arrays.asList(sArray);
List<String> list3 = Arrays.asList(sArray);

LinkedList<List<String>> lists = new LinkedList<List<String>>();

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

Set<String> combinations = new TreeSet<String>();
Set<String> newCombinations;

for (String s : lists.removeFirst())
    combinations.add(s);

while (!lists.isEmpty()) {
    List<String> next = lists.removeFirst();
    newCombinations = new TreeSet<String>();
    for (String s1 : combinations)
        for (String s2 : next)
            newCombinations.add(s1 + s2);

    combinations = newCombinations;
}
for (String s : combinations)
    System.out.print(s + " ");

Scurvy

I don't think you want combinations and newCombinations to be Sets. He didn't specify any sort of uniqueness restrictions. I would just make them both Lists and then I believe it works. – Manumission

He said "all possible unique combinations". Result will be "AAA, AAA, ABA..." in my case {"A", "A", "B", "C"} after using lists instead of sets. – Scurvy

Ah you're right. His example made me think he didn't care though since he said "if we add a third list of length 3 then there will be 36" which isn't necessarily true if you care about uniqueness. Oh well, I +1'd already – Manumission

Answer 6

The operation that you need to implement called Cartesian Product. For more details see https://en.wikipedia.org/wiki/Cartesian_product

I recommend to use my open source library that can do exactly what you need: https://github.com/SurpSG/Kombi

There is example how to use it: https://github.com/SurpSG/Kombi#usage-for-lists-1

Note: The library was designed for high performance purposes. You can observe banchmarks results here

The library gives you pretty good throughput and constant memory usage

Resemble

Answer 7

• No recursion
• Ordered
• Possible to get a specific combination by its index (without building all other permutations)
• Supports parallel iteration

Class and main() method in the end:

public class TwoDimensionalCounter<T> {
    private final List<List<T>> elements;
    private final int size;

    public TwoDimensionalCounter(List<List<T>> elements) {
        //Need to reverse the collection if you need the original order in the answers
        this.elements = Collections.unmodifiableList(elements);
        int size = 1;
        for(List<T> next: elements)
            size *= next.size();
        this.size = size;
    }

    public List<T> get(int index) {
        List<T> result = new ArrayList<>();
        for(int i = elements.size() - 1; i >= 0; i--) {
            List<T> counter = elements.get(i);
            int counterSize = counter.size();
            result.add(counter.get(index % counterSize));
            index /= counterSize;
        }
        return result;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        TwoDimensionalCounter<Integer> counter = new TwoDimensionalCounter<>(
                Arrays.asList(
                        Arrays.asList(1, 2, 3),
                        Arrays.asList(1, 2),
                        Arrays.asList(1, 2, 3)
                ));
        for(int i = 0; i < counter.size(); i++)
            System.out.println(counter.get(i));
    }
}

PS: as it turned out Guava's Cartessian Product uses the same algorithm. But they also created special sub-classes to List to make it several times more efficient.

Harsho

Can i ask why you use index /= counterSize; ? Because its not necessery . – Schrock

You have three slots that may have values a, b, c, so the permutation will start with: aaa, aab, etc. The operation that you described let's the algorithm to first generate 3d letter, then move to 2nd letter and then move to 1st letter. – Harsho

I've been using this answer and it works really well! Just one minor thing: it'd be better to use a long as size to avoid integer overflow since the number of combinations could easily grow past the integer max value, at least in my case. – Goeselt

Answer 8

Use the nested loop solution provided by some other answers here to combine two lists.

When you have more than two lists,

1. Combine the first two into one new list.
2. Combine the resulting list with the next input list.
3. Repeat.

Hyunhz

Answer 9

Late to the party as usual, but here's a nicely explained example using arrays. It can easily be altered for lists. I needed all unique combinations of multiple arrays for my use case in a lexicographical order.

I posted it as none of the answers here give a clear algorithm, and I can't stand recursion. Are we not on stackoverflow after all?

String[][] combinations = new String[][] {
                 new String[] { "0", "1" },
                 new String[] { "0", "1" },
                 new String[] { "0", "1" },
                 new String[] { "0", "1" } };

    int[] indices = new int[combinations.length];
    
    int currentIndex = indices.length - 1;
    outerProcess: while (true) {

        for (int i = 0; i < combinations.length; i++) {
            System.out.print(combinations[i][indices[i]]);
        }
        System.out.println();

        while (true) {
            // Increase current index
            indices[currentIndex]++;
            // If index too big, set itself and everything right of it to 0 and move left
            if (indices[currentIndex] >= combinations[currentIndex].length) {
                for (int j = currentIndex; j < indices.length; j++) {
                    indices[j] = 0;
                }
                currentIndex--;
            } else {
                // If index is allowed, move as far right as possible and process next
                // combination
                while (currentIndex < indices.length - 1) {
                    currentIndex++;
                }
                break;
            }
            // If we cannot move left anymore, we're finished
            if (currentIndex == -1) {
                break outerProcess;
            }
        }
    }

The output;

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Radiograph

Answer 10

Generating combinations with Java 8 Stream map and reduce methods.

Try it online!

public static <T> List<List<T>> combinations(List<List<T>> lists) {
    // incorrect incoming data
    if (lists == null) return Collections.emptyList();
    return lists.stream()
            // non-null and non-empty lists
            .filter(list -> list != null && list.size() > 0)
            // represent each list element as a singleton list
            .map(list -> list.stream().map(Collections::singletonList)
                    // Stream<List<List<T>>>
                    .collect(Collectors.toList()))
            // summation of pairs of inner lists
            .reduce((list1, list2) -> list1.stream()
                    // combinations of inner lists
                    .flatMap(inner1 -> list2.stream()
                            // merge two inner lists into one
                            .map(inner2 -> Stream.of(inner1, inner2)
                                    .flatMap(List::stream)
                                    .collect(Collectors.toList())))
                    // list of combinations
                    .collect(Collectors.toList()))
            // otherwise an empty list
            .orElse(Collections.emptyList());
}

public static void main(String[] args) {
    List<String> list1 = Arrays.asList("A", "B", "C");
    List<String> list2 = Arrays.asList("W", "X", "Y", "Z");
    List<String> list3 = Arrays.asList("L", "M", "K");

    List<List<String>> lists = Arrays.asList(list1, list2, list3);
    List<List<String>> combinations = combinations(lists);

    // column-wise output
    int rows = 6;
    IntStream.range(0, rows).forEach(i -> System.out.println(
            IntStream.range(0, combinations.size())
                    .filter(j -> j % rows == i)
                    .mapToObj(j -> combinations.get(j).toString())
                    .collect(Collectors.joining(" "))));
}

Column-wise output:

[A, W, L] [A, Y, L] [B, W, L] [B, Y, L] [C, W, L] [C, Y, L]
[A, W, M] [A, Y, M] [B, W, M] [B, Y, M] [C, W, M] [C, Y, M]
[A, W, K] [A, Y, K] [B, W, K] [B, Y, K] [C, W, K] [C, Y, K]
[A, X, L] [A, Z, L] [B, X, L] [B, Z, L] [C, X, L] [C, Z, L]
[A, X, M] [A, Z, M] [B, X, M] [B, Z, M] [C, X, M] [C, Z, M]
[A, X, K] [A, Z, K] [B, X, K] [B, Z, K] [C, X, K] [C, Z, K]

---

^{See also: Cartesian product of an arbitrary number of sets}

Cocytus

Answer 11

Here is a sample using bit mask. No recursion and multiple lists

static List<Integer> allComboMatch(List<Integer> numbers, int target) {
    int sz = (int)Math.pow(2, numbers.size());
    for (int i = 1; i < sz; i++) {
        int sum = 0;
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int j = 0; j < numbers.size(); j++) {
            int x = (i >> j) & 1;
            if (x == 1) {
                sum += numbers.get(j);
                result.add(j);
            }
        }
        if (sum == target) {
            return result;
        }
    }
    return null;
}

Ohara

This code generates the sums of all subsets of numbers, it has nothing to do with the actual question. It also returns the indices of the elements that add up to a specific sum, which is equally unrelated. – Microbe