如何使用 Java 8 流制作笛卡尔积？

Question

我有以下集合类型：

 Map<String, Collection<String>> map;

我想从每个键的集合中的单个值创建每个 map.size() 的唯一组合。

例如，假设地图如下所示：

 A, {a1, a2, a3, ..., an}
B, {b1, b2, b3, ..., bn}
C, {c1, c2, c3, ..., cn}

我想得到的结果是 List<Set<String>> 结果，看起来类似于（排序并不重要，它只需要是包含所有可能组合的“完整”结果）：

 {a1, b1, c1},
{a1, b1, c2},
{a1, b1, c3},
{a1, b2, c1},
{a1, b2, c2},
{a1, b2, c3},
...
{a2, b1, c1},
{a2, b1, c2},
...
{a3, b1, c1},
{a3, b1, c2},
...
{an, bn, cn}

这基本上是一个计数问题，但我想看看是否可以使用 Java 8 流来解决这个问题。

原文由 Alex Paransky 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以使用递归 flatMap 链来解决这个问题。

首先，因为我们需要通过映射值来回移动，最好将它们复制到 ArrayList （这不是深拷贝，在你的情况下它是 ArrayList 3 个元素只有，所以额外的内存使用率很低）。

其次，为了维护以前访问过的元素的前缀，让我们创建一个不可变的帮助 Prefix 类：

 private static class Prefix<T> {
    final T value;
    final Prefix<T> parent;

    Prefix(Prefix<T> parent, T value) {
        this.parent = parent;
        this.value = value;
    }

    // put the whole prefix into given collection
    <C extends Collection<T>> C addTo(C collection) {
        if (parent != null)
            parent.addTo(collection);
        collection.add(value);
        return collection;
    }
}

这是非常简单的不可变链表，可以像这样使用：

 List<String> list = new Prefix<>(new Prefix<>(new Prefix<>(null, "a"), "b"), "c")
                          .addTo(new ArrayList<>()); // [a, b, c];

接下来，让我们创建链接 flatMaps 的内部方法：

 private static <T, C extends Collection<T>> Stream<C> comb(
        List<? extends Collection<T>> values, int offset, Prefix<T> prefix,
        Supplier<C> supplier) {
    if (offset == values.size() - 1)
        return values.get(offset).stream()
                     .map(e -> new Prefix<>(prefix, e).addTo(supplier.get()));
    return values.get(offset).stream()
            .flatMap(e -> comb(values, offset + 1, new Prefix<>(prefix, e), supplier));
}

看起来像递归，但更复杂：它不直接调用自己，而是传递调用外部方法的lambda。参数：

• 值：原始值的 List new ArrayList<>(map.values) （在你的例子中是—）。
• 偏移量：此列表中的当前偏移量
• 前缀：长度偏移的当前前缀（或 null 如果 offset == 0 ）。它包含当前从集合中选择的元素 list.get(0) ， list.get(1) 直到 list.get(offset-1) 。
• 供应商：创建结果集合的工厂方法。

当我们到达值列表的末尾时 ( offset == values.size() - 1 )，我们使用供应商将最后一个集合的元素从值映射到最终组合。否则我们使用 flatMap 它为每个中间元素扩大前缀并为下一个偏移再次调用 comb 方法。

最后是使用此功能的公共方法：

 public static <T, C extends Collection<T>> Stream<C> ofCombinations(
        Collection<? extends Collection<T>> values, Supplier<C> supplier) {
    if (values.isEmpty())
        return Stream.empty();
    return comb(new ArrayList<>(values), 0, null, supplier);
}

用法示例：

 Map<String, Collection<String>> map = new LinkedHashMap<>(); // to preserve the order
map.put("A", Arrays.asList("a1", "a2", "a3", "a4"));
map.put("B", Arrays.asList("b1", "b2", "b3"));
map.put("C", Arrays.asList("c1", "c2"));

ofCombinations(map.values(), LinkedHashSet::new).forEach(System.out::println);

我们再次将各个组合收集到 LinkedHashSet 以保留顺序。您可以改用任何其他集合（例如 ArrayList::new ）。

原文由 Tagir Valeev 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

带有 forEach 的 Java 8 中的笛卡尔积：

 List<String> listA = Arrays.asList("0", "1");
List<String> listB = Arrays.asList("a", "b");

List<String> cartesianProduct = new ArrayList<>();
listA.forEach(a -> listB.forEach(b -> cartesianProduct.add(a + b)));

System.out.println(cartesianProduct);
// Output: [0a, 0b, 1a, 1b]

原文由 Miklos Toth 发布，翻译遵循 CC BY-SA 4.0 许可协议