Merge list of lists

Question

We have list of lists:

List<List<String>> source = List.of(
                List.of("a", "b"),
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));

source.size() can be random, and each sublists size is random too.

And algorithm should transform it to one single List<String> in further order:

List<String> transform(List<List<String>> source) {
    // ... Implementation ...
    return List.of ("aA1", "aA2", "aA3", "aA4",
                    "aB1", "aB2", "aB3", "aB4",
                    "aC1", "aC2", "aC3", "aC4",
                    "bA1", "bA2", "bA3", "bA4",
                    "bB1", "bB2", "bB3", "bB4",
                    "bC1", "bC2", "bC3", "bC4");;
}

How to implement the transform method to get the result list as described above?

This is more than a merge. This is some sort of cross product. — Old Dog Programmer, Jun 14 '22 at 17:35
Does this answer your question? [How can I make Cartesian product with Java 8 streams?](https://stackoverflow.com/questions/32131987/how-can-i-make-cartesian-product-with-java-8-streams) — Eritrean, Jun 14 '22 at 17:57
@Pavel, Michael, I, and others expect you to show what you have tried, even if it isn't working. — Old Dog Programmer, Jun 14 '22 at 23:21

score 2 · Answer 1 · answered Jun 14 '22 at 16:44

I'm sure there's a better way to do it, but here's how I did it:

public static Collection<String> allPermutations(List<List<String>> source) {
    
    Set<String> allPermutations = new TreeSet<>();

    for (List<String> list : source) {
        if (allPermutations.isEmpty()) {
            allPermutations.addAll(list);
        } else {
            Set<String> newValues = new HashSet<>();
            for (String s : allPermutations) {
                for (String v : list) {
                    newValues.add(s+v);
                }
            }
            allPermutations.clear();
            allPermutations.addAll(newValues);
        }
    }

    return allPermutations;
}

score 1 · Accepted Answer · answered Jun 14 '22 at 16:36

It can be done with a bit of recursion, provided you don't have too many items in source and also don't get a combinatorial explosion from how long each sublist is.

import java.util.ArrayList;
import java.util.List;

public class AllCombinations {

    static void AddCombination(List<List<String>> source, int depth, 
            String prefix, List<String> output) {
        for (String layer : source.get(depth)) {
            String str = prefix + layer;
            if (depth < source.size() - 1) {
                AddCombination(source, depth + 1, str, output);
            } else {
                output.add(str);
            }
        }
    }
    
    public static void main(String[] args) {
        List<List<String>> source = List.of(
                List.of("a", "b"),
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));
        
        List<String> output = new ArrayList<>();
        
        AddCombination(source, 0, "", output);
        
        output.forEach(System.out::println);
    }
}

Old Dog Programmer · Answer 3 · 2022-06-14T23:36:16.173

I normally would have waited for the O/P to show more involvement before posting my solution. But,seeing as there are already two answers, here is my "Old dog" solution. It's similar to the one from Ryan:

package cartesianproduct;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class CartesianProduct {
        
    public static Collection<String> 
        cartesianProduct (Collection<String> product,
                          Collection<String> m1,
                          Collection<String> m2) {
            
            product.clear ();
            if (m1.isEmpty() ) { 
                product.addAll(m2);
                return product;
            } 
            if (m2.isEmpty()) {
                product.addAll (m1);
                return product;
            }
            for (String str1: m1) {
                for (String str2: m2) {
                    product.add (str1.concat(str2));
                }
            }            
            return product;
        }  

    public static void main(String[] args) {
        List<List<String>> source = List.of(
                List.of("a", "b"), 
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));
        
        Collection<String> theProduct = new LinkedList<> ();  
        for (List<String> a: source) {      
              theProduct = (LinkedList<String>) cartesianProduct 
                      (new LinkedList<> (), theProduct, a);
        }
        System.out.println (theProduct.toString());
    }   
}

Here is the output: [aA1, aA2, aA3, aA4, aB1, aB2, aB3, aB4, aC1, aC2, aC3, aC4, bA1, bA2, bA3, bA4, bB1, bB2, bB3, bB4, bC1, bC2, bC3, bC4]

Part of the solution in the above is in main. To take the loop out of main, you can add this method:

public static Collection<String> cartesianProduct (
        Collection<String> destination,
        List<List<String>> source ) {
        Collection<String> product = new LinkedList<> ();
        for (Collection<String> s :source) {
            product = cartesianProduct (new LinkedList<> (), 
                       product, s);
        }
        destination.clear();
        destination.addAll(product);
        return destination; 
}

and replace the loop in main with

    theProduct = cartesianProduct(theProduct, source);

.

Merge list of lists

3 Answers3