将列表映射转换为映射列表

Question

我有一张列表地图，例如：

Map("a" -> [1,2,3], "b" -> [4,5,6], "c" -> [7])

我需要制作：

[
Map("a" -> 1, "b" -> 4, "c" -> 7),
Map("a" -> 1, "b" -> 5, "c" -> 7),
Map("a" -> 1, "b" -> 6, "c" -> 7),
Map("a" -> 2, "b" -> 4, "c" -> 7),
Map("a" -> 2, "b" -> 5, "c" -> 7),
Map("a" -> 2, "b" -> 6, "c" -> 7),
Map("a" -> 3, "b" -> 4, "c" -> 7),
Map("a" -> 3, "b" -> 5, "c" -> 7),
Map("a" -> 3, "b" -> 6, "c" -> 7),
]

我正在为我的容器类型使用名为 Vavr 的 Java 库，但我不介意看到以任何语言完成的实现。

Answer 1

这是一种方法：

public static void main(String[] args) {
    Map<String, List<Integer>> map = new HashMap<>();
    map.put("a", Arrays.asList(1, 2, 3));
    map.put("b", Arrays.asList(4, 5, 6));
    map.put("c", Arrays.asList(7));

    List<Map.Entry<String, List<Integer>>> list =
            new ArrayList<>(map.entrySet());

    List<Map<String, Integer>> result = new ArrayList<>();
    combine(list, 0, new HashMap<>(), result);
    System.out.println(result);
}

static void combine(List<Map.Entry<String, List<Integer>>> list, int n,
                    Map<String, Integer> part,
                    List<Map<String, Integer>> result) {
    if (n >= list.size()) {
        result.add(new HashMap<>(part));
    } else {
        Map.Entry<String, List<Integer>> e = list.get(n);
        for (Integer i : e.getValue()) {
            part.put(e.getKey(), i);
            combine(list, n + 1, part, result);
        }
        part.remove(e.getKey());
    }
}

输出：（已编辑格式）

[
  {a=1, b=4, c=7}, {a=1, b=5, c=7}, {a=1, b=6, c=7},
  {a=2, b=4, c=7}, {a=2, b=5, c=7}, {a=2, b=6, c=7},
  {a=3, b=4, c=7}, {a=3, b=5, c=7}, {a=3, b=6, c=7}
]

Answer 2

这是一个使用递归的解决方案：

public static void main(String[] args) {
    Map<String, int[]> map = new HashMap<>();
    map.put("a", new int[]{1, 2, 3});
    map.put("b", new int[]{4, 5, 6});
    map.put("c", new int[]{7});
    List<Map<String, Integer>> combinations = new ArrayList<>();
    System.out.println(getCombinations(
            map, combinations, 0,
            new HashMap<String, Integer>(), map.values().size()));
}

private static List<Map<String, Integer>> getCombinations(
        Map<String, int[]> map, List<Map<String, Integer>> combinations, int i,
        Map<String, Integer> current, int len) {
    if (i >= len) {
        combinations.add(current);
    } else {
        String key = (String) map.keySet().toArray()[i];
        int[] value = map.get(key);
        for (int num : value) {
            current.put(key, num);
            getCombinations(map, combinations, i + 1,
                    new HashMap<>(current), len);
        }
    }
    return combinations;
}

输出：

[
  {a=1, b=4, c=7}, {a=1, b=5, c=7}, {a=1, b=6, c=7}, 
  {a=2, b=4, c=7}, {a=2, b=5, c=7}, {a=2, b=6, c=7}, 
  {a=3, b=4, c=7}, {a=3, b=5, c=7}, {a=3, b=6, c=7}
]

Answer 3

我最终采用了与此处答案不同的方式。

我已经有一个 class 用于执行笛卡尔积，例如：

public class CartesianProduct {
    public static <T> Seq<Seq<T>> on(Seq<Seq<T>> sets) {
        if (sets.size() >= 1) {
            var javaList = sets.map(Value::toJavaList).toJavaList();
            var out = computeCombinations(javaList);
            return Vector.ofAll(out.stream().map(Vector::ofAll));
        }
        return Vector.empty();
    }

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

    private static <T> List<List<T>> computeCombinations(List<List<T>> lists) {
        List<List<T>> currentCombinations = List.of(List.of());
        for (List<T> list : lists) {
            currentCombinations = appendElements(currentCombinations, list);
        }
        return currentCombinations;
    }
}

所以我做了：

Seq<Seq<Integer>> allValuesProduct = CartesianProduct.on(mapOfLists.values());
Seq<Map<String, Integer>> listOfMaps =
        allValuesProduct.map(values -> HashMap.tabulate(
                values.length(),
                i -> Tuple.of(
                        mapOfLists.keySet().toList().get(i),
                        values.get(i))));

虽然我确信一定有一种更干净的方法，完全不涉及突变。

Answer 4

您可以先遍历地图条目并将列表元素表示为 Map<String,Integer> 并获得 地图列表流 ，然后 reduce 这个流到单个列表。

Try it online!

Map<String, List<Integer>> mapOfLists = new LinkedHashMap<>();
mapOfLists.put("a", List.of(1, 2, 3));
mapOfLists.put("b", List.of(4, 5, 6));
mapOfLists.put("c", List.of(7));

List<Map<String, Integer>> listOfMaps = mapOfLists.entrySet().stream()
        // Stream<List<Map<String,Integer>>>
        .map(entry -> entry.getValue().stream()
                // represent list elements as Map<String,Integer>
                .map(element -> Map.of(entry.getKey(), element))
                // collect a list of maps
                .collect(Collectors.toList()))
        // intermediate output
        //[{a=1}, {a=2}, {a=3}]
        //[{b=4}, {b=5}, {b=6}]
        //[{c=7}]
        .peek(System.out::println)
        // reduce a stream of lists to a single list
        // by sequentially multiplying the list pairs
        .reduce((list1, list2) -> list1.stream()
                // combinations of elements,
                // i.e. maps, from two lists
                .flatMap(map1 -> list2.stream()
                        .map(map2 -> {
                            // join entries of two maps
                            Map<String, Integer> map =
                                    new LinkedHashMap<>();
                            map.putAll(map1);
                            map.putAll(map2);
                            return map;
                        }))
                // collect into a single list
                .collect(Collectors.toList()))
        .orElse(null);

// output
listOfMaps.forEach(System.out::println);
//{a=1, b=4, c=7}
//{a=1, b=5, c=7}
//{a=1, b=6, c=7}
//{a=2, b=4, c=7}
//{a=2, b=5, c=7}
//{a=2, b=6, c=7}
//{a=3, b=4, c=7}
//{a=3, b=5, c=7}
//{a=3, b=6, c=7}

^{另请参阅：

• Generate all possible string combinations by replacing the hidden # number sign

•}

Answer 5

这就是我要解决的方法

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class molToLom {

    public static void main(String[] args) {
        //This is what we have: A map of lists (mol)
        TreeMap<String, List<Integer>> mol = new TreeMap<String, List<Integer>>();
        mol.put("a", List.of(1, 2, 3));
        mol.put("b", List.of(4, 5, 6));
        mol.put("c", List.of(7));
        //we want a list of maps (lom)
        ArrayList<Map<String, Integer>> lom = new ArrayList<>();
        //Add an empty element. We'll need that later
        lom.add(new TreeMap<String, Integer>());
        //Now run through our map
        mol.forEach((tag, list) -> {
            //We rebuild our lom on every iteration. Otherwise we would get incomplete maps in our list
            ArrayList<Map<String, Integer>> tLom = new ArrayList<>();
            //Run through our list of maps and ...
            lom.forEach(map -> {
                //... combine every element in this list with every element in the list from our initial map entry
                list.forEach(i -> {
                    Map<String, Integer> m = new TreeMap<>(map);
                    m.put(tag, i);
                    tLom.add(m);
                });
            });
            //replace our last lom with the newly created one. Could be lom = tLom if lom was a field
            lom.clear();
            lom.addAll(tLom);
        });
        System.out.println(lom);
    }
}

将列表映射转换为映射列表

Convert a map of lists into a list of maps

java

combinations

dictionary

list

combinatorics