Generate all combinations from multiple lists
JavaListAlgorithmCombinationsCartesian ProductJava Problem Overview
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)
Java Solutions
Solution 1 - Java
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 - Java
This operation is called cartesian product. Guava provides an utility function for that: Lists.cartesianProduct
Solution 3 - Java
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 - Java
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 - Java
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 + " ");
Solution 6 - Java
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
Solution 7 - Java
Use the nested loop solution provided by some other answers here to combine two lists.
When you have more than two lists,
- Combine the first two into one new list.
- Combine the resulting list with the next input list.
- Repeat.
Solution 8 - Java
- 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.
Solution 9 - Java
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
Solution 10 - Java
Generating combinations with Java 8 Stream map
and reduce
methods.
[Try it online!][1]
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][2]
[1]: https://tio.run/##rVVbb9owFH7nV5xFWpVMkBYq7aEFpK7aw7SiPQxpN@3BhAN15tiR7RTRqb@d@RLAWbho0vLgOLa/833H55KcPJGeKJHn81@bDS1KITXkZjGtNGXpm9tOa01piaSwW52ymjGaQcaIUjAhlMPvDpinXleaaPMaTsfwQJUeumE6HkMmihnlZlNwFTe3mJmopLZjn8tLoDwTUmKm3aygfAlzosnuCF1A7HAwGgGvGEtAoq4kh3vBmMFZnhSLUq8tT5zc7qD1OYeuPYuT3W6ggQves6aB8Ln7cOY8sHU@XVCmUTpR0PNOwSuvDS4u3Heq6DPGCYzh6iChxFKiQq4BSfboTSDDwq4QBQSUuQeGWnj1bQ0FKRsCdu65neBmbm52puz1tNUEqj47G8NGzMZHAWnmWbZsQqpUCx@D5KDXqioKlxcgFlASKpWdUM5RHrtrifMqw9j52u@6U4Nk63T/eFAD1jAfz/HtY8yInpibdIf7W8LBecKAuEC5RNArEVKauRYgOJ614CLpkAPL74OTikWtqeutDs5LaTllY2Tywhn8B/jJeJ8MgctUc/VhKP5jXgn9iHJFFZr6hX3ptrNJyPdMYXykcdSd46VzoM09CTqHwjTB2MTBFNSPn0DkstHLXMX43To9YQR3UpK1SolyFNFd1IXonR3uo6BRtaCDNvSLRX21wzc7fD@Jv27jHyxqYoePFtrEhgbqNt2yEJagf13/LaFpplF4o@Z/wf8JAhmuUFlV8J4LpKh0We0jaIoGpFhZM2/3nB@4rqtCEr7E@KrrDiXpwgTa9NWYusJZK42mcCqdlkaZZjxuZcYBS6Hcup0nJ/qF/yfkljCH17XYEdATGFPfU/FplntUg2@JOs4Tk/b@Mk9SHyiXXFBuYRFEtjS3ef2y2fwB "Java (OpenJDK 8) – Try It Online" [2]: https://stackoverflow.com/a/67174557/15675591
Solution 11 - Java
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;
}