7
\$\begingroup\$

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

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

    List<List<T>> product = new ArrayList<List<T>>();

    for (List<T> list : lists) {

        List<List<T>> newProduct = new ArrayList<List<T>>();

        for (T listElement : list) {

            if (product.isEmpty()) {

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

                for (List<T> productList : product) {

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

        product = newProduct;
    }

    return product;
}

Can this code be simplified?

\$\endgroup\$
5
\$\begingroup\$
  • 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 <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;
    }
    

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

    and the sub-task (using Java 8):

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

    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.

\$\endgroup\$
  • \$\begingroup\$ See this gist for the code with a running example. \$\endgroup\$ – toto2 Oct 27 '14 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.