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

How can I make Cartesian product with Java 8 streams?

提问by Alex Paransky

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.

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

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

我想得到的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}

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

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

采纳答案by Tagir Valeev

You can solve this using the recursive flatMapchain.

您可以使用递归flatMap链解决此问题。

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 ArrayListof 3 elements only, so the additional memory usage is low).

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

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

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

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:

接下来，让我们创建链接 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:

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

• values: the Listof original values (new ArrayList<>(map.values)in your case).
• offset: the current offset within this list
• prefix: the current prefix of length offset (or nullif 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.

• 值：List原始值的值（new ArrayList<>(map.values)在您的情况下）。
• 偏移量：此列表中的当前偏移量
• prefix：长度偏移的当前前缀（或nullif offset == 0）。它包含当前从集合中选择的元素list.get(0)，list.get(1)最多list.get(offset-1).
• 供应商：创建结果集合的工厂方法。

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 flatMapwhich for each intermediate element enlarges the prefix and calls the combmethod again for the next offset.

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

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 LinkedHashSetagain to preserve the order. You can use any other collection instead (e.g. ArrayList::new).

我们LinkedHashSet再次收集个人组合以保留订单。您可以改用任何其他集合（例如ArrayList::new）。

回答by Marco13

A solution that mainly operates on lists, making things a lot simpler. It does a recursive call in flatMap, keeping track of the elements that have already been combined, and the collections of elements that are still missing, and offers the results of this nested recursive construction as a stream of lists:

一个主要对列表进行操作的解决方案，使事情变得更简单。它在 中进行递归调用flatMap，跟踪已组合的元素以及仍然缺失的元素集合，并将此嵌套递归构造的结果作为列表流提供：

import java.util.*;
import java.util.stream.Stream;

public class CartesianProduct {

    public static void main(String[] args) {
        Map<String, Collection<String>> map = 
            new LinkedHashMap<String, Collection<String>>();
        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()).forEach(System.out::println);
    }

    public static <T> Stream<List<T>> ofCombinations(
        Collection<? extends Collection<T>> collections) {
        return ofCombinations(
            new ArrayList<Collection<T>>(collections), 
            Collections.emptyList());        
    }       

    private static <T> Stream<List<T>> ofCombinations(
        List<? extends Collection<T>> collections, List<T> current) {
        return collections.isEmpty() ? Stream.of(current) :
            collections.get(0).stream().flatMap(e -> 
            {
                List<T> list = new ArrayList<T>(current);
                list.add(e);
                return ofCombinations(
                    collections.subList(1, collections.size()), list);
            });
    }
}

回答by Miklos Toth

Cartesian product in Java 8 with forEach:

Java 8 中使用 forEach 的笛卡尔积：

List<String> listA = new ArrayList<>();
listA.add("0");
listA.add("1");
List<String> listB = new ArrayList<>();
listB.add("a");
listB.add("b"); 

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

cartesianProduct.forEach(System.out::println);
//Output : 0a 0b 1a 1b 

回答by Jurgen Vinju

A simpler answer, for a simpler situation where you just want to have the cartesian product of the elements of two collections.

一个更简单的答案，对于更简单的情况，您只想拥有两个集合元素的笛卡尔积。

Here's some code which uses flatMapto generate the cartesian product of two short lists:

这是一些flatMap用于生成两个短列表的笛卡尔积的代码：

    public static void main(String[] args) {
      List<Integer> aList = Arrays.asList(1,2,3);
      List<Integer> bList = Arrays.asList(4,5,6);

      Stream<List<Integer>> product = aList.stream().flatMap(a -> 
          bList.stream().flatMap(b ->
            Stream.of(Arrays.asList(a, b)))
          );

      product.forEach(p -> { System.out.println(p); });

// prints:
//              [1, 4]
//              [1, 5]
//              [1, 6]
//              [2, 4]
//              [2, 5]
//              [2, 6]
//              [3, 4]
//              [3, 5]
//              [3, 6]
    }

If you want to add more collections, just nest the streams a litter further:

如果您想添加更多集合，只需将流进一步嵌套：

        aList.stream().flatMap(a -> 
          bList.stream().flatMap(b ->
            cList.stream().flatMap(c ->
               Stream.of(Arrays.asList(a, b, c))))
          );

回答by Marin

Here is another solution, which does not use as many features from Streamsas Tagir's example; however I believe it to be more straight-forward:

这是另一个解决方案，它没有使用StreamsTagir 示例中那么多的特性；但是我认为它更直接：

public class Permutations {

    transient List<Collection<String>> perms;

    public List<Collection<String>> list(Map<String, Collection<String>> map) {

        SortedMap<String, Collection<String>> sortedMap = new TreeMap<>();
        sortedMap.putAll(map);

        sortedMap.values().forEach((v) ->  perms = expand(perms, v));

        return perms;
    }

    private List<Collection<String>> expand(List<Collection<String>> list, Collection<String> elements) {

        List<Collection<String>> newList = new LinkedList<>();

        if (list == null) {
            elements.forEach((e) -> {
                SortedSet<String> set = new TreeSet<>();
                set.add(e);
                newList.add(set);
            });
        } else {
            list.forEach((set) ->
                elements.forEach((e) -> {
                    SortedSet<String> newSet = new TreeSet<>();
                    newSet.addAll(set);
                    newSet.add(e);
                    newList.add(newSet);
                }));
        }

        return newList;
    }
}

You can remove the Sortedprefix if you are not interested in ordering of elements; though, I think it's easier to debug if everything is sorted.

Sorted如果您对元素的排序不感兴趣，可以删除前缀；不过，我认为如果一切都经过排序，调试会更容易。

Usage:

用法：

Permutations p = new Permutations();
List<Collection<String>> plist = p.list(map);
plist.forEach((s) -> System.out.println(s));

Enjoy!

享受！

回答by David Lilljegren

While it's not a Stream solution, Guava's com.google.common.collect.Sets does that for you

虽然它不是 Stream 解决方案，但 Guava 的 com.google.common.collect.Sets 可以为您做到这一点

Set<List<String>> result = Sets.cartesianProduct(Set.of("a1","a2"), Set.of("b1","b2"), Set.of("c1","c2" ))

回答by ravthiru

In loop create combined list

在循环中创建组合列表

List<String> cartesianProduct(List<List<String>> wordLists) {

 List<String> cp = wordLists.get(0);

 for (int i = 1; i < wordLists.size(); i++) 
 {      
     List<String> secondList = wordLists.get(i);
     List<String> combinedList = cp.stream().flatMap(s1 -> secondList.stream().map(s2 -> s1 + s2))
                    .collect(Collectors.toList());
        cp = combinedList;

    }
        return cp;
}

回答by ominug

I wrote a class implementing Iterable, and holding only the current item in memory. The Iterableas well as the Iteratorcan be converted to a Streamif desired.

我写了一个实现Iterable, 并且只在内存中保存当前项目的类。 的Iterable以及在Iterator可转化为一个Stream，如果需要的话。

class CartesianProduct<T> implements Iterable<List<T>> {
    private final Iterable<? extends Iterable<T>> factors;

    public CartesianProduct(final Iterable<? extends Iterable<T>> factors) {
        this.factors = factors;
    }

    @Override
    public Iterator<List<T>> iterator() {
        return new CartesianProductIterator<>(factors);
    }
}

class CartesianProductIterator<T> implements Iterator<List<T>> {
    private final List<Iterable<T>> factors;
    private final Stack<Iterator<T>> iterators;
    private final Stack<T> current;
    private List<T> next;
    private int index = 0;

    private void computeNext() {
        while (true) {
            if (iterators.get(index).hasNext()) {
                current.add(iterators.get(index).next());
                if (index == factors.size() - 1) {
                    next = new ArrayList<>(current);
                    current.pop();
                    return;
                }
                index++;
                iterators.add(factors.get(index).iterator());
            } else {
                index--;
                if (index < 0) {
                    return;
                }
                iterators.pop();
                current.pop();
            }
        }
    }

    public CartesianProductIterator(final Iterable<? extends Iterable<T>> factors) {
        this.factors = StreamSupport.stream(factors.spliterator(), false)
                .collect(Collectors.toList());
        if (this.factors.size() == 0) {
            index = -1;
        }
        iterators = new Stack<>();
        iterators.add(this.factors.get(0).iterator());
        current = new Stack<>();
        computeNext();
    }

    @Override
    public boolean hasNext() {
        if (next == null && index >= 0) {
            computeNext();
        }
        return next != null;
    }

    @Override
    public List<T> next() {
        if (!hasNext()) {
            throw new IllegalStateException();
        }
        var result = next;
        next = null;
        return result;
    }
}

回答by Olufemi

Use a Consumer Function Class, a List and a foreach

使用消费者函数类、列表和 foreach

    public void tester(){

        String[] strs1 = {"2","4","9"};
        String[] strs2 = {"9","0","5"};

        //Final output is {"29", "49, 99", "20", "40", "90", "25", "45", "95"}
        List<String> result = new ArrayList<>();
        Consumer<String> consumer = (String str) -> result.addAll(Arrays.stream(strs1).map(s -> s+str).collect(Collectors.toList()));
        Arrays.stream(strs2).forEach(consumer);

        System.out.println(result);

}