java - 使用 Java Streams 的笛卡尔积

Question

我在 JavaScript 中有一个笛卡尔积函数:

function cartesianProduct(arr) {
    return arr.reduce(function(a,b) {
        return a.map(function(x) {
            return b.map(function(y) {
                return x.concat(y);
            });
        }).reduce(function(a,b) { return a.concat(b); }, []);
    }, [[]]);
}

所以如果我有一个 3D 数组:

var data = [[['D']], [['E'],['L','M','N']]];

cartesianProduct(data) 的结果将是二维数组:

[['D','E'], ['D','L','M','N']]

我想做的是使用 Streams 在 Java 中编写这个笛卡尔积函数。

到目前为止，我在 Java 中有以下内容:

public Collection<Collection<String>> cartesianProduct(Collection<Collection<Collection<String>>> arr) {

    return arr.stream().reduce(new ArrayList<Collection<String>>(), (a, b) -> {
        return a.stream().map(x -> {
            return b.stream().map(y -> {
                return Stream.concat(x.stream(), y.stream());
            });
        }).reduce(new ArrayList<String>(), (c, d) -> {
            return Stream.concat(c, d);
        });
    });
}

我有一个类型检查错误指出:

ArrayList<String> is not compatible with Stream<Stream<String>>

我对错误的猜测:

• 我需要在某处使用收集器(可能在 Stream.concat 之后)
• 身份数据类型错误

Answer 1

这可以通过一些函数式编程魔法实现。这是接受 Collection<Collection<Collection<T>>> 的方法并产生 Stream<Collection<T>> :

static <T> Stream<Collection<T>> cartesianProduct(Collection<Collection<Collection<T>>> arr)
{
    return arr.stream()
        .<Supplier<Stream<Collection<T>>>> map(c -> c::stream)
        .reduce((s1, s2) -> () -> s1.get().flatMap(
                a -> s2.get().map(b -> Stream.concat(a.stream(), b.stream())
                        .collect(Collectors.toList()))))
        .orElseGet(() -> () -> Stream.<Collection<T>>of(Collections.emptyList()))
        .get();
}

使用示例:

cartesianProduct(
    Arrays.asList(Arrays.asList(Arrays.asList("D")),
        Arrays.asList(Arrays.asList("E"), Arrays.asList("L", "M", "N"))))
            .forEach(System.out::println);

输出:

[D, E]
[D, L, M, N]

当然不是.forEach()您可以将结果收集到List如果你想返回 Collection<Collection<T>>相反，但返回 Stream对我来说似乎更灵活。

一些解释:

在这里，我们通过 map(c -> c::stream) 创建了一个流供应商流.该流的每个函数都可以按需生成相应集合元素的流。我们这样做是因为流一次关闭(否则流的流就足够了)。之后，我们减少了这个供应商流，为每一对创建一个新的供应商，它 flatMaps 两个流并将它们的元素映射到连接列表。 orElseGet部分是处理空输入所必需的。最后.get()只需调用最终的流供应商来获取结果流。