Merge list of lists-CodePudding

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?

CodePudding user response：

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

CodePudding user response：

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