使用Java Stream实现多个集合的笛卡尔积

Question

目前我只能实现两个集合的笛卡尔积，以下是代码：

public static <T1, T2, R extends Collection<Pair<T1, T2>>>
R getCartesianProduct(
        Collection<T1> c1, Collection<T2> c2,
        Collector<Pair<T1, T2>, ?, R> collector) {
    return c1.stream()
            .flatMap(e1 -> c2.stream().map(e2 -> new Pair<>(e1, e2)))
            .collect(collector);
}

这段代码在IntelliJ中可以正常运行，但在Eclipse中无法运行。两者的编译器兼容性级别都是1.8：

The method collect(Collector<? super Object,A,R>)
in the type Stream<Object> is not applicable for
the arguments (Collector<Pair<T1,T2>,capture#5-of ?,R>)

这里是Pair.java：

public class Pair<T1, T2> implements Serializable {
    protected T1 first;
    protected T2 second;
    private static final long serialVersionUID = 1360822168806852921L;

    public Pair(T1 first, T2 second) {
        this.first = first;
        this.second = second;
    }

    public Pair(Pair<T1, T2> pair) {
        this(pair.getFirst(), pair.getSecond());
    }

    public T1 getFirst() {
        return this.first;
    }

    public T2 getSecond() {
        return this.second;
    }

    public void setFirst(T1 o) {
        this.first = o;
    }

    public void setSecond(T2 o) {
        this.second = o;
    }

    public String toString() {
        return "(" + this.first + ", " + this.second + ")";
    }

    @Override
    public boolean equals(Object o) {
        if(!(o instanceof Pair))
            return false;
        Pair p = (Pair) o;
        if(!this.first.equals(p.first))
            return false;
        if(!this.second.equals(p.second))
            return false;
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = hash * 31 + this.first.hashCode();
        hash = hash * 31 + this.second.hashCode();
        return hash;
    }
}

如何修复此错误？

是否有一种优雅的方式来实现多个集合的笛卡尔积？假设我们有类tuple。

- stanleyerror

Answer 1

Eclipse对于类型推断存在问题。如果你添加一个类型提示.<Pair<T1,T2>>flatMap，它就可以正常编译。

如果我可以建议一种不同的方法，请考虑让你的cartesianProduct不要处理整个流和集合，而只是成为flatMap的辅助程序：

static <T1, T2, R> Function<T1, Stream<R>> crossWith(
         Supplier<? extends Stream<T2>> otherSup, 
         BiFunction<? super T1, ? super T2, ? extends R> combiner
) {
    return t1 -> otherSup.get().map(t2 -> combiner.apply(t1, t2));
}

现在，只有在想要结果包含 Pair 时才需要创建一个Pair，您可以通过几次应用flatMap来进行高阶笛卡尔积：

List<String> letters = Arrays.asList("A", "B", "C");
List<Integer> numbers = Arrays.asList(1, 2, 3);

List<Pair<String, Integer>> board = letters.stream()
                .flatMap(crossWith(numbers::stream, Pair::new))
                .collect(toList());


List<String> ops = Arrays.asList("+", "-", "*", "/");

List<String> combinations = letters.stream()
                .flatMap(crossWith(ops::stream, String::concat))
                .flatMap(crossWith(letters::stream, String::concat))
                .collect(toList());   // triple cartesian product

- Misha

Answer 2

这里有一个解决方案，可以推广到所需的flatMap应用数量（即产品顺序）在编译时未知的情况。

BinaryOperator<Function<String,Stream<String>>> kleisli = (f,g) -> s -> f.apply(s).flatMap(g);

List<String> cartesian(int n, Collection<String> coll) {
    return coll.stream()
           .flatMap( IntStream.range(1, n).boxed()
                     .map(_any -> crossWith(coll::stream, String::concat)) // create (n-1) appropriate crossWith instances
                     .reduce(s -> Stream.of(s), kleisli)                   // compose them sequentially
                    )                                                      // flatMap the stream with the entire function chain
           .collect(toList());
}

您可以在我的博客上找到这个的详细信息。

- Sebastian

Answer 3

你可以将Supplier作为Collectors.toCollection方法的参数。这样可以简化代码并使其更通用。不同类型和数量的集合及其元素的笛卡尔积。

在线试用！

public static void main(String[] args) {
    Set<Integer> a = Set.of(1, 2);
    Set<Character> b = Set.of('*', '+');
    List<String> c = List.of("A", "B");

    Set<Set<Object>> cpSet = cartesianProduct(HashSet::new, a, b, c);
    List<List<Object>> cpList = cartesianProduct(ArrayList::new, a, b, c);

    // output, order may vary
    System.out.println(cpSet);
    System.out.println(cpList);
}

/**
 * @param nCol the supplier of the output collection
 * @param cols the input array of collections
 * @param <R>  the type of the return collection
 * @return the cartesian product of the multiple collections
 */
@SuppressWarnings("unchecked")
public static <R extends Collection<?>> R cartesianProduct(
        Supplier nCol, Collection<?>... cols) {
    // check if supplier is not null
    if (nCol == null) return null;
    return (R) Arrays.stream(cols)
        // non-null and non-empty collections
        .filter(col -> col != null && col.size() > 0)
        // represent each element of a collection as a singleton collection
        .map(col -> (Collection<Collection<?>>) col.stream()
            .map(e -> Stream.of(e).collect(Collectors.toCollection(nCol)))
            .collect(Collectors.toCollection(nCol)))
        // summation of pairs of inner collections
        .reduce((col1, col2) -> (Collection<Collection<?>>) col1.stream()
            // combinations of inner collections
            .flatMap(inner1 -> col2.stream()
                // concatenate into a single collection
                .map(inner2 -> Stream.of(inner1, inner2)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toCollection(nCol))))
            // collection of combinations
            .collect(Collectors.toCollection(nCol)))
        // otherwise an empty collection
        .orElse((Collection<Collection<?>>) nCol.get());
}

输出（顺序可能会有所不同）：

[[1,A,*],[1,B,*],[1,A,+],[A,2,*],[1,B,+],[2,B,*],[A,2,+],[2,B,+]]
[[2,+,A],[2,+,B],[2,*,A],[2,*,B],[1,+,A],[1,+,B],[1,*,A],[1,*,B]]

---

^{另请参阅较不通用的版本：在Java中查找笛卡尔积}

- user16497917

Answer 4

您可以使用一个更加通用的解决方案，它接受任何类型的Collection并允许您选择内部和外部返回集合的类型。

在线试用！

public static void main(String[] args) {
    List<Integer> a = List.of(1, 2);
    List<Long> b = List.of(3L, 4L);
    Set<Float> c = Set.of(5.5F, 6.6F);

    Set<List<Number>> cpListSet = cartesianProduct(
            HashSet::new, ArrayList::new, Set.of(a, b, c));

    List<Set<Number>> cpSetList = cartesianProduct(
            ArrayList::new, HashSet::new, List.of(a, b, c));

    // output, order may vary
    System.out.println(cpListSet);
    System.out.println(cpSetList);
}

/**
 * @param oCol,iCol outer/inner return collection supplier
 * @param cols      input collection of collections
 * @param <T>       supertype of the elements of collections
 * @param <U>       type of the inner return collection
 * @param <R>       type of the outer return collection
 * @return a Cartesian product of a multiple collections
 */
public static <T, U extends Collection<T>, R extends Collection<U>> R
cartesianProduct(Supplier<R> oCol, Supplier<U> iCol,
                 Collection<Collection<? extends T>> cols) {
    // check if suppliers are not null
    if (oCol == null || iCol == null) return null;
    return cols.stream()
        // non-null and non-empty collections
        .filter(col -> col != null && col.size() > 0)
        // represent each element of a collection as a singleton collection
        .map(col -> col.stream()
            .map(e -> Stream.of(e).collect(Collectors.toCollection(iCol)))
            .collect(Collectors.toCollection(oCol)))
        // summation of pairs of inner collections
        .reduce((col1, col2) -> col1.stream()
            // combinations of inner collections
            .flatMap(inner1 -> col2.stream()
                // concatenate into a single collection
                .map(inner2 -> Stream.of(inner1, inner2)
                    .flatMap(Collection::stream)
                    .collect(Collectors.toCollection(iCol))))
            // collection of combinations
            .collect(Collectors.toCollection(oCol)))
        // otherwise, an empty collection
        .orElse(oCol.get());
}

输出，顺序可能会有所不同：

[[2,3,6.6],[1,3,6.6],[2,4,6.6],[1,4,6.6],[1,4,5.5],[1,3,5.5],[2,4,5.5],[2,3,5.5]]
[[5.5,1,3],[6.6,1,3],[5.5,1,4],[6.6,1,4],[5.5,2,3],[6.6,2,3],[5.5,2,4],[6.6,2,4]]

---

^{还可以参考更具特定性的版本：多个列表的笛卡尔积}

- user16596785