Как составить комбинацию из значений LinkedHashMap‹String, ArrayList‹ArrayList››

Следующее рекурсивное решение основано на ответе Филиппа Мейстера на аналогичный вопрос о построении Декартово произведение:

static List<List<Integer>> merge(List<List<List<Integer>>> lists) {
    List<List<Integer>> resultLists = new ArrayList<>();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList<>());
    } else {
        List<List<Integer>> firstList = lists.get(0);
        List<List<Integer>> remainingLists = merge(lists.subList(1, lists.size()));
        for (List<Integer> first : firstList) {
            for (List<Integer> remaining : remainingLists) {
                List<Integer> resultList = new ArrayList<>();
                resultList.addAll(first);
                resultList.addAll(remaining);
                resultLists.add(resultList);
            }
        }
    }
    return resultLists;
}  

Основное отличие заключается в типе возврата и добавлении всех элементов списка first во вложенный список в соответствии с требованиями.

Тестовая настройка

private static void testCombinations(Map<String, List<List<Integer>>> map) {
    System.out.println("input map: " + map);
    
    List<List<Integer>> list = merge(new ArrayList<>(map.values()));
    
    list.forEach(System.out::println);
}

// --------
Map<String, List<List<Integer>>> map1 = new LinkedHashMap<>();

map1.put("SFO", Arrays.asList(Arrays.asList(1)));
map1.put("SEA", Arrays.asList(Arrays.asList(2), Arrays.asList(3), Arrays.asList(4)));
map1.put("PHX", Arrays.asList(Arrays.asList(5), Arrays.asList(6)));

testCombinations(map1);
        
Map<String, List<List<Integer>>> map2 = new LinkedHashMap<>();

map2.put("FRA", Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3, 4)));
map2.put("MEL", Arrays.asList(Arrays.asList(5, 6)));
testCombinations(map2);

Вывод:

input map: {SFO=[[1]], SEA=[[2], [3], [4]], PHX=[[5], [6]]}
[1, 2, 5]
[1, 2, 6]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
input map: {FRA=[[1, 2], [3, 4]], MEL=[[5, 6]]}
[1, 2, 5, 6]
[3, 4, 5, 6]

Решение может быть реализовано с использованием потоков и рекурсивной цепочки flatMap (на основе ответа Marco13):

static <T extends List> Stream<List<T>> ofCombinations(List<? extends Collection<T>> mapValues, List<T> current) {
    return mapValues.isEmpty() ? Stream.of(current) :
        mapValues.get(0).stream().flatMap(list -> {
            List<T> combination = new ArrayList<T>(current);
            combination.addAll(list);
            return ofCombinations(mapValues.subList(1, mapValues.size()), combination);
        });
}

private static void testStreamCombinations(Map<String, List<List<Integer>>> map) {
    System.out.println("input map: " + map);
    
    ofCombinations(new ArrayList<>(map.values()), Collections.emptyList())
        .forEach(System.out::println);   
}

// invoking test method
testStreamCombinations(map1);
testStreamCombinations(map2);

Тестовый вывод: такой же, как указано выше.