Skip to content

Instantly share code, notes, and snippets.

@max333
Created October 27, 2014 12:42
Show Gist options
  • Save max333/3cfafa146aeee29bee2a to your computer and use it in GitHub Desktop.
Save max333/3cfafa146aeee29bee2a to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
/**
* Answer to http://codereview.stackexchange.com/questions/67804
*
* Builds all combinations of the given elements.
*/
public class CodeReviewCombinations {
public static <T> List<List<T>> computeCombinationsOriginal(List<List<T>> lists) {
List<List<T>> combinations = new ArrayList<>();
for (List<T> list : lists) {
List<List<T>> extraColumnCombinations = new ArrayList<>();
for (T element : list) {
if (combinations.isEmpty()) {
extraColumnCombinations.add(Arrays.asList(element));
} else {
for (List<T> productList : combinations) {
List<T> newProductList = new ArrayList<>(productList);
newProductList.add(element);
extraColumnCombinations.add(newProductList);
}
}
}
combinations = extraColumnCombinations;
}
return combinations;
}
public static <T> List<List<T>> computeCombinations2(List<List<T>> lists) {
List<List<T>> combinations = Arrays.asList(Arrays.asList());
for (List<T> list : lists) {
List<List<T>> extraColumnCombinations = new ArrayList<>();
for (List<T> combination : combinations) {
for (T element : list) {
List<T> newCombination = new ArrayList<>(combination);
newCombination.add(element);
extraColumnCombinations.add(newCombination);
}
}
combinations = extraColumnCombinations;
}
return combinations;
}
public static <T> List<List<T>> appendElements(List<List<T>> combinations, List<T> extraElements) {
return combinations.stream().flatMap(oldCombination
-> extraElements.stream().map(extra -> {
List<T> combinationWithExtra = new ArrayList<>(oldCombination);
combinationWithExtra.add(extra);
return combinationWithExtra;
}))
.collect(Collectors.toList());
}
public static <T> List<List<T>> computeCombinations3(List<List<T>> lists) {
List<List<T>> currentCombinations = Arrays.asList(Arrays.asList());
for (List<T> list : lists) {
currentCombinations = appendElements(currentCombinations, list);
}
return currentCombinations;
}
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(1, 2, 3);
List<Integer> list2 = Arrays.asList(13, 21);
List<Integer> list3 = Arrays.asList(65, 73);
System.out.println("Lists: " + Arrays.asList(list1, list2, list3));
System.out.println("");
System.out.println("Original: " + computeCombinationsOriginal(Arrays.asList(list1, list2, list3)));
System.out.println("Shorter: " + computeCombinations2(Arrays.asList(list1, list2, list3)));
System.out.println("Split: " + computeCombinations3(Arrays.asList(list1, list2, list3)));
}
}
@max333
Copy link
Author

max333 commented Oct 27, 2014

The output is:

Lists: [[1, 2, 3], [13, 21], [65, 73]]

Original: [[1, 13, 65], [2, 13, 65], [3, 13, 65], [1, 21, 65], [2, 21, 65], [3, 21, 65], [1, 13, 73], [2, 13, 73], [3, 13, 73], [1, 21, 73], [2, 21, 73], [3, 21, 73]]
Shorter: [[1, 13, 65], [1, 13, 73], [1, 21, 65], [1, 21, 73], [2, 13, 65], [2, 13, 73], [2, 21, 65], [2, 21, 73], [3, 13, 65], [3, 13, 73], [3, 21, 65], [3, 21, 73]]
Split: [[1, 13, 65], [1, 13, 73], [1, 21, 65], [1, 21, 73], [2, 13, 65], [2, 13, 73], [2, 21, 65], [2, 21, 73], [3, 13, 65], [3, 13, 73], [3, 21, 65], [3, 21, 73]]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment