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)

Solution 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, "");

Solution 2

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

Solution 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.

Solution 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());
    }
}

Solution 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 + " ");

View more solutions