Say I have several List<T>s, I will put them into another list or other collections, so I don't know how many list<T> I have until I call List<List<T>>.size()
Take below List<Integer> as an example:
list1=[1,2]
list2=[3,4]
list3=[5,6]
....
listn=[2*n-1,2n];
How can I get the result of list1*list2*list3*...listn as a Cartesian product?
For example:
list1*list2*list3
should be:
[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]
You can use recursion to achieve it, your base case of recursion is when input is empty then return empty list, else process the remaining elements. E.g.
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class CartesianProduct {
public static <T> List<List<T>> calculate(List<List<T>> input) {
List<List<T>> res = new ArrayList<>();
if (input.isEmpty()) { // if no more elements to process
res.add(new ArrayList<>()); // then add empty list and return
return res;
} else {
// we need to calculate the cartesian product
// of input and store it in res variable
process(input, res);
}
return res; // method completes , return result
}
private static <T> void process(List<List<T>> lists, List<List<T>> res) {
//take first element of the list
List<T> head = lists.get(0);
//invoke calculate on remaining element, here is recursion
List<List<T>> tail = calculate(lists.subList(1, lists.size()));
for (T h : head) { // for each head
for (List<T> t : tail) { //iterate over the tail
List<T> tmp = new ArrayList<>(t.size());
tmp.add(h); // add the head
tmp.addAll(t); // and current tail element
res.add(tmp);
}
}
}
public static void main(String[] args) {
//we invoke the calculate method
System.out.println(calculate(Arrays.asList(
Arrays.asList(1, 2),
Arrays.asList(3, 4),
Arrays.asList(5, 6))));
}
}
Output
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
Thanks to @sol4me 's answer using tail recursion, here is another version which is not using tail recursion but I think is easier to understand.
public class CartesianProduct {
public static <T> List<List<T>> calculate(List<List<T>> input) {
List<List<T>> result = new ArrayList<List<T>>();
if (input.isEmpty()) { // If input an empty list
// add empty list and return
result.add(new ArrayList<T>());
return result;
} else {
// get the first list as a head
List<T> head = input.get(0);
// recursion to calculate a tail list
List<List<T>> tail = calculate(input.subList(1, input.size()));
// we merge every head element with every tail list.
for (T h : head) {
for (List<T> t : tail) {
List<T> resultElement = new ArrayList<T>();
resultElement.add(h);
resultElement.addAll(t);
result.add(resultElement);
}
}
}
return result;
}
public static void main(String[] args) {
List<List<Integer>> bigList = Arrays.asList(
Arrays.asList(1, 2),
Arrays.asList(3, 4),
Arrays.asList(5, 6),
Arrays.asList(7, 8));
System.out.println(calculate(bigList));
}
}
Prepare a list of lists List<List<T>> populated with a single empty value. This list is used further as a storage of intermediate results and as a final result.
Sequentially append the data from incoming lists List<List<T>> to the intermediate result and obtain the final result. Schematically, this iterative process looks as follows:
result0: [[]]
list1: [1,2]
-------
result1: [[1],[2]]
list2: [3,4]
-------
result2: [[1,3],[1,4],[2,3],[2,4]]
list3: [5,6]
-------
result3: [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
/**
* @param lists an arbitrary number of lists
* @param <T> the type of the elements
* @return the Cartesian product
*/
public static <T> List<List<T>> cartesianProduct(List<List<T>> lists) {
// check if incoming data is not null
if (lists == null) return Collections.emptyList();
// Cartesian product, intermediate result
List<List<T>> cp = Collections.singletonList(Collections.emptyList());
// iterate through incoming lists
for (List<T> list : lists) {
// non-null and non-empty lists
if (list == null || list.size() == 0) continue;
// intermediate result for next iteration
List<List<T>> next = new ArrayList<>();
// rows of current intermediate result
for (List<T> row : cp) {
// elements of current list
for (T el : list) {
// new row for next intermediate result
List<T> nRow = new ArrayList<>(row);
nRow.add(el);
next.add(nRow);
}
}
// pass to next iteration
cp = next;
}
// Cartesian product, final result
return cp;
}
public static void main(String[] args) {
List<List<Integer>> lists = prepareLists(3);
List<List<Integer>> cp = cartesianProduct(lists);
// output without spaces
System.out.println(lists.toString().replace(" ", ""));
System.out.println(cp.toString().replace(" ", ""));
}
// supplementary method, prepares lists for multiplication
public static List<List<Integer>> prepareLists(int n) {
List<List<Integer>> lists = new ArrayList<>(n);
for (int i = 1; i <= n; i++)
lists.add(Arrays.asList(i * 2 - 1, i * 2));
return lists;
}
Output:
[[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]