如何使用 Java 8 流制作笛卡尔积? [英] How can I make Cartesian product with Java 8 streams?

问题描述

我有以下集合类型:

Map<String, Collection<String>> map;

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

I would like to create unique combinations of each of map.size() from a single value in the collection for each Key.

例如假设地图如下所示:

For example suppose the map looks like the following:

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

我想得到的结果是一个 List> 结果，看起来类似于(排序并不重要，它只需要是一个完整"的结果，包括所有可能的组合):

The result I would like to get would a List<Set<String>> result, looking similar to (ordering is not important, it just needs to be a 'complete' result consisting of all possible combinations):

{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 流来解决.

This is basically a counting problem, but I would like to see if a solution is possible using Java 8 streams.

推荐答案

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

You can solve this using the recursive flatMap chain.

首先，因为我们需要根据地图值来回移动，最好将它们复制到 ArrayList(这不是深层复制，在您的情况下它是 ArrayListcode>只有3个元素，所以额外的内存使用量很低).

First as we need to move back and forth by the map values, it's better to copy them to the ArrayList (this is not the deep copy, in your case it's ArrayList of 3 elements only, so the additional memory usage is low).

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

Second, to maintain a prefix of previously visited elements, let's create a helper immutable Prefix class:

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

这是一个非常简单的不可变链表，可以这样使用:

This is very simple immutable linked list which can be used like this:

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

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

Next, let's create the internal method which chains 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.参数:

Looks like recursion, but it's more complex: it doesn't call itself directly, but passed lambda which calls the outer method. Parameters:

• values:原始值的 List(在您的情况下为 new ArrayList<>(map.values)).
• offset:此列表中的当前偏移量
• prefix:长度偏移的当前前缀(如果offset == 0，则为null).它包含当前从集合 list.get(0)、list.get(1) 到 list.get(offset-1).
• supplier:创建结果集合的工厂方法.

• values: the List of original values (new ArrayList<>(map.values) in your case).
• offset: the current offset within this list
• prefix: the current prefix of length offset (or null if offset == 0). It contains currently selected elements from the collections list.get(0), list.get(1) up to list.get(offset-1).
• supplier: the factory method to create the resulting collection.

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

When we reached the end of the values list (offset == values.size() - 1), we map the elements of the last collection from the values to the final combination using the supplier. Otherwise we use the flatMap which for each intermediate element enlarges the prefix and calls the comb method again for the next offset.

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

Finally here's public method to use this feature:

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).

We collect individual combinations to the LinkedHashSet again to preserve the order. You can use any other collection instead (e.g. ArrayList::new).

这篇关于如何使用 Java 8 流制作笛卡尔积?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！