如何用Java8流制作笛卡尔积？

Question

我有以下收藏类型：

Map<String, Collection<String>> map;

我希望根据集合中每个键的单个值为每个map.size()创建唯一的组合。

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

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

Answer 1

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

首先，由于我们需要通过映射值来回移动，所以最好将它们复制到arraylist（这不是深度复制，在您的示例中，它只有3个元素的arraylist，因此额外的内存占用很少）。

其次，为了维护先前访问的元素的前缀，让我们创建一个helper不可变的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));
}

null

当我们到达values列表的末尾(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)。