How to find cartesian product of an arbitrary number of ArrayLists - Java

Question

I'm trying to figure out how to output the cartesian product of two or more lists in a java method such that I have a List of List's as the output.

For example, if i have: a = [1,2] , b = [3,4] , c = [5,6] Then the output would be: [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6].....]

I have managed to write the code such that it works for two lists but when it becomes three or more it doesnt work. In my code, i have initially added the cartesian product of the first two lists to a larger list. And from there i tried adding the remaining elements into those such lists, but i am presented with an infinite loop for some reason.

public static List<List<Integer>> cartprod(List<Entry> entries) {
    // TODO: implement this
    List<List<Integer>> cartprod = new ArrayList<List<Integer>>();
    Entry first = entries.get(0);

    for (int i =0; i < first.getValues().size(); i++) {
        int element = first.getValues().get(i);
        for (int j = 1; j < entries.size(); j++) {
            Entry entry = entries.get(j);
            for (int k =0; k < entry.getValues().size(); k++) {
                int entry_element = entry.getValues().get(k);
                List<Integer> product = new ArrayList<Integer>();
                product.add(element);
                product.add(entry_element);
                cartprod.add(product);
            }

        }
    } 
    //HELP WITH THIS CODE BLOCK 
    // ###################################
    // int entries_size = entries.size(); 
    // for (int i=2; i< entries.size(); i++) {
    //  List<Integer> nextList = entries.get(i).getValues();
    //  for (int j=0; j< cartprod.size(); j++) {
    //      List<Integer> element = cartprod.get(j);
    //      for (int k=0; k < nextList.size(); k++) {
    //          System.out.println(nextList);
    //          List<Integer> newList = element;
    //          int numToAdd = nextList.get(k);
    //          System.out.println(numToAdd+"\n");
    //          newList.add(numToAdd);
    //          cartprod.add(newList);
    //      }
    //  }
    // }
    return cartprod;
}

Answer 1

It's a lot easier to calculate Cartesian Products using recursion. Here is a recursive code:

public List<List<Integer>> calculateCartesianProduct(List<List<Integer>> inputLists) {
    List<List<Integer>> cartesianProducts = new ArrayList<>();
    if (inputLists != null && inputLists.size() > 0) {
        // separating the list at 0th index
        List<Integer> initialList = inputLists.get(0);
        // recursive call
        List<List<Integer>> remainingLists = calculateCartesianProduct(inputLists.subList(1, inputLists.size()));
        // calculating the cartesian product
        initialList.forEach(element -> {
            remainingLists.forEach(remainingList -> {
                ArrayList<Integer> cartesianProduct = new ArrayList<>();
                cartesianProduct.add(element);
                cartesianProduct.addAll(remainingList);
                cartesianProducts.add(cartesianProduct);
            });
        });
    } else {
        // Base Condition for Recursion (returning empty List as only element)
        cartesianProducts.add(new ArrayList<>());
    }
    return cartesianProducts;
}

Here he is how I tested it:

List<Integer> a = Arrays.asList(1, 2);
List<Integer> b = Arrays.asList(3, 4);
List<Integer> c = Arrays.asList(5, 6);
List<List<Integer>> inputLists = Arrays.asList(a, b, c);

System.out.println(calculateCartesianProduct(inputLists));

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]]

Answer 2

this question sounds a lot like homework/interview question...but i'll give you a hint anyway. you are going about it the wrong way, nested loops will not help you in this case, because you want to be able to work with any number of lists. think of it this way: every element in the cartesian product of lists L1,L2,...Ln is made up of one element from L1, and the rest is the cartesian product of L2...Ln as such:

{L1[0] + cartesian(L2,L3,...Ln)} , {L1[1] + cartesian(L2,L3,...,Ln)} and so on up to the length of L1.

i hope you get where i'm going with this, good luck!

P.S. if this question is indeed not homework, i'll post the java code later.

P.P.S. extra points if you calculate cartesian(Lk,...,Ln) only once for each k where n > k > 1 ;)