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

问题描述

我有以下集合类型：

  Map< String，Collection< String>>地图; 
  

我想创建每个 map.size（）的唯一组合来自每个Key的集合中的单个值。

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

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

结果我想获得列表< 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 str使用递归的 flatMap 链来解决这个问题。

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

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

 私有静态类前缀< T> {
最终T值; 
 final前缀< T>父母; 
 
前缀（前缀< T> parent，T值）{
 this.parent = parent; 
 this.value = value; 
} 
 
 //将整个前缀放入给定的集合
< C extends Collection< T>> C addTo（C collection）{
 if（parent！= null）
 parent.addTo（collection）; 
 collection.add（value）; 
退货收藏; 
} 
} 
  

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

  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>>流< c取代;梳子（
列表<？extends Collection< T>>值，int offset，前缀< T>前缀，
供应商< C>供应商）{
 if（offset == values.size （） -  1）
返回values.get（offset）.stream（）
 .map（e  - > new Prefix<>（prefix，e）.addTo（supplier.get（）） ）; 
返回values.get（offset）.stream（）
 .flatMap（e  - > comb（values，offset + 1，new Prefix<>（prefix，e），supplier））; 
} 
  

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

• 值：原始值的 List （新的ArrayList<>（map.values）在您的情况下）。


• offset：此列表中的当前偏移量


• 前缀：长度偏移的当前前缀（或 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>>流< c取代; ofCombinations（
 Collection<？extends Collection< T>> value，Supplier< C> supplier）{
 if（values.isEmpty（））
 return Stream.empty（）; 
返回comb（new ArrayList<>（values），0，null，supplier）; 
} 
  

一个用法示例：

  Map< String，Collection< String>> map = new LinkedHashMap<>（）; //保留订单
 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 ）。

I have the following collection type:

Map<String, Collection<String>> map;

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}

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}

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

解决方案

You can solve this using the recursive flatMap chain.

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

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

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

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

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

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

A usage example:

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

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屋！