通过 Java Stream 实现多个集合的笛卡尔积
Implement Cartesian product of several collections by Java Stream
目前只能实现两个集合的笛卡尔积，代码如下：
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;
}
}
如何解决这个错误？
有没有一种优雅的方式来实现多个集合的笛卡尔积？假设我们有 class tuple.
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
这是一个解决方案，适用于在编译时未知所需的 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());
}
您将在 my own blog.
找到有关其工作原理的详细信息
您可以使用 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]]
另见不太通用的版本：Finding cartesian product in Java
您可以使用 更通用的 解决方案，它接受任何类型的 Collection 并允许您选择 inner[=30= 的类型]和外部return集合。
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]]
另见不太通用的版本：Cartesian product of multiple lists
目前只能实现两个集合的笛卡尔积，代码如下：
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;
}
}
如何解决这个错误？
有没有一种优雅的方式来实现多个集合的笛卡尔积？假设我们有 class tuple.
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
这是一个解决方案，适用于在编译时未知所需的 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());
}
您将在 my own blog.
找到有关其工作原理的详细信息您可以使用 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]]
另见不太通用的版本：Finding cartesian product in Java
您可以使用 更通用的 解决方案，它接受任何类型的 Collection 并允许您选择 inner[=30= 的类型]和外部return集合。
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]]
另见不太通用的版本：Cartesian product of multiple lists