snippetjavaMinor

Generate Cartesian product of List in Java

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

javaproductgeneratecartesianlist

Problem

My code, which generates Cartesian product of all lists given as arguments:

public static  List> cartesianProduct(List... lists) {

    List> product = new ArrayList>();

    for (List list : lists) {

        List> newProduct = new ArrayList>();

        for (T listElement : list) {

            if (product.isEmpty()) {

                List newProductList = new ArrayList();
                newProductList.add(listElement);
                newProduct.add(newProductList);
            } else {

                for (List productList : product) {

                    List newProductList = new ArrayList(productList);
                    newProductList.add(listElement);
                    newProduct.add(newProductList);
                }
            }
        }

        product = newProduct;
    }

    return product;
}

Can this code be simplified?

Solution

-
You should read about the diamond operator. You don't need to write the types on the right hand side in some circumstances.

-
I avoid varargs because they confuse the type system. My guess is that you are not using an IDE because mine (Netbeans) flags both the diamond operators and the varargs.

-
You can indeed shorten your code because you don't really need to do a conditional check on the empty list if you start with the right conditions:

public static  List> computeCombinations2(List> lists) {
    List> combinations = Arrays.asList(Arrays.asList());
    for (List list : lists) {
        List> extraColumnCombinations = new ArrayList<>();
        for (List combination : combinations) {
            for (T element : list) {
                List newCombination = new ArrayList<>(combination);
                newCombination.add(element);
                extraColumnCombinations.add(newCombination);
            }
        }
        combinations = extraColumnCombinations;
    }
    return combinations;
}

Note that the scanning order changed: the first element stays fixed until all other combinations of the other elements are exhausted. I prefer that order actually.

-
It think it would be cleaner to split this in two methods. There is a sub-task of adding one list of elements to an existing set of combinations and the main task which must call the sub-task on all lists:

public static  List> computeCombinations3(List> lists) {
    List> currentCombinations = Arrays.asList(Arrays.asList());
    for (List list : lists) {
        currentCombinations = appendElements(currentCombinations, list);
    }
    return currentCombinations;
}

and the sub-task (using Java 8):

public static  List> appendElements(List> combinations, List extraElements) {
    return combinations.stream().flatMap(oldCombination
            -> extraElements.stream().map(extra -> {
                List combinationWithExtra = new ArrayList<>(oldCombination);
                combinationWithExtra.add(extra);
                return combinationWithExtra;
            }))
            .collect(Collectors.toList());
}

Actually, for this method, Java 8 does not make it shorter and makes it less readable than the old style. I am leaving it nonetheless so you (and others) can get more familiar with Java 8.

-
Minor point: I think you use too many blank lines in your code.

Code Snippets

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

Context

StackExchange Code Review Q#67804, answer score: 5

Revisions (0)

No revisions yet.