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

问题描述 投票：25回答：9

我有以下集合类型：

Map<String, Collection<String>> map;

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

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

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流解决方案。

java java-8 java-stream cartesian-product
9个回答
15
投票

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

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

其次，为了维护以前访问过的元素的前缀，让我们创建一个帮助器不可变的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：长度偏移量的当前前缀（如果null，则为offset == 0）。它包含当前从list.get(0)，list.get(1)到list.get(offset-1)的集合中选择的元素。
  • supplier：用于创建结果集合的工厂方法。

当我们到达值列表的末尾（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）。

8
投票

一种主要在列表上运行的解决方案，使事情变得更加简单。它在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);
            });
    }
}
5
投票

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
3
投票

这是另一个解决方案，它不使用Streams中的许多功能作为Tagir的例子;但我相信它更直接：

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

请享用！

1
投票

虽然它不是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" ))
1
投票

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

这里有一些代码使用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))))
          );
0
投票

使用消费者函数类，列表和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);

}
0
投票

在循环中创建组合列表

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;
}
0
投票

我写了一个实现Iterable的类，并且只保存内存中的当前项。如果需要，The Iterable以及the 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;
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.