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

Question

我有以下集合类型:

Map<String, Collection<String>> map;

我想map.size()从每个Key的集合中的单个值创建每个组的唯一组合.

例如,假设地图如下所示:

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

我希望获得的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}

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

Answer 1

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

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

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

看起来像递归,但它更复杂:它不直接调用自身,但传递lambda调用外部方法.参数:

• 值:List原始值(new ArrayList<>(map.values)在您的情况下).
• offset:此列表中的当前偏移量
• prefix:长度偏移量的当前前缀(或nullif offset == 0).它包含集合中当前选定的元素list.get(0),list.get(1)最多包含list.get(offset-1).
• supplier:用于创建结果集合的工厂方法.

当我们到达值list(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).

Answer 2

一种主要在列表上运行的解决方案,使事情变得更加简单.它执行递归调用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);
            });
    }
}

Answer 3

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

这是一些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]
}

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

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

Answer 4

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 

Answer 5

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

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

Answer 6

这是另一个解决方案，它没有使用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;
    }
}

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

用法：

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

享受！