Scala 中的交叉产品
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14740199/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Cross product in Scala
提问by pathikrit
I want to have a binary operator cross(cross-product/cartesian product) that operates with traversables in Scala:
我想要一个二元运算符cross（交叉积/笛卡尔积），它在 Scala 中与可遍历对象一起运行：
val x = Seq(1, 2)
val y = List('hello', 'world', 'bye')
val z = x cross y # i can chain as many traversables e.g. x cross y cross w etc
assert z == ((1, 'hello'), (1, 'world'), (1, 'bye'), (2, 'hello'), (2, 'world'), (2, 'bye'))
What is the best way to do this in Scala only (i.e. not using something like scalaz)?
仅在 Scala 中执行此操作的最佳方法是什么（即不使用诸如 scalaz 之类的东西）？
回答by Travis Brown
You can do this pretty straightforwardly with an implicit class and a for-comprehension in Scala 2.10:
您可以使用forScala 2.10 中的隐式类和-comprehension非常简单地完成此操作：
implicit class Crossable[X](xs: Traversable[X]) {
def cross[Y](ys: Traversable[Y]) = for { x <- xs; y <- ys } yield (x, y)
}
val xs = Seq(1, 2)
val ys = List("hello", "world", "bye")
And now:
现在：
scala> xs cross ys
res0: Traversable[(Int, String)] = List((1,hello), (1,world), ...
This is possible before 2.10—just not quite as concise, since you'd need to define both the class and an implicit conversion method.
这在 2.10 之前是可能的——只是不太简洁，因为您需要定义类和隐式转换方法。
You can also write this:
你也可以这样写：
scala> xs cross ys cross List('a, 'b)
res2: Traversable[((Int, String), Symbol)] = List(((1,hello),'a), ...
If you want xs cross ys cross zsto return a Tuple3, however, you'll need either a lot of boilerplate or a library like Shapeless.
但是，如果您想xs cross ys cross zs返回 a Tuple3，您将需要大量样板或类似Shapeless的库。
回答by u8968951
cross x_listand y_listwith:
交叉x_list并y_list与：
val cross = x_list.flatMap(x => y_list.map(y => (x, y)))
回答by Milad Khajavi
Here is the implementation of recursive cross product of arbitrary number of lists:
这是任意数量列表的递归叉积的实现：
def crossJoin[T](list: Traversable[Traversable[T]]): Traversable[Traversable[T]] =
list match {
case xs :: Nil => xs map (Traversable(_))
case x :: xs => for {
i <- x
j <- crossJoin(xs)
} yield Traversable(i) ++ j
}
crossJoin(
List(
List(3, "b"),
List(1, 8),
List(0, "f", 4.3)
)
)
res0: Traversable[Traversable[Any]] = List(List(3, 1, 0), List(3, 1, f), List(3, 1, 4.3), List(3, 8, 0), List(3, 8, f), List(3, 8, 4.3), List(b, 1, 0), List(b, 1, f), List(b, 1, 4.3), List(b, 8, 0), List(b, 8, f), List(b, 8, 4.3))
回答by Noel Yap
class CartesianProduct(product: Traversable[Traversable[_ <: Any]]) {
override def toString(): String = {
product.toString
}
def *(rhs: Traversable[_ <: Any]): CartesianProduct = {
val p = product.flatMap { lhs =>
rhs.map { r =>
lhs.toList :+ r
}
}
new CartesianProduct(p)
}
}
object CartesianProduct {
def apply(traversable: Traversable[_ <: Any]): CartesianProduct = {
new CartesianProduct(
traversable.map { t =>
Traversable(t)
}
)
}
}
// TODO: How can this conversion be made implicit?
val x = CartesianProduct(Set(0, 1))
val y = List("Alice", "Bob")
val z = Array(Math.E, Math.PI)
println(x * y * z) // Set(List(0, Alice, 3.141592653589793), List(0, Alice, 2.718281828459045), List(0, Bob, 3.141592653589793), List(1, Alice, 2.718281828459045), List(0, Bob, 2.718281828459045), List(1, Bob, 3.141592653589793), List(1, Alice, 3.141592653589793), List(1, Bob, 2.718281828459045))
// TODO: How can this conversion be made implicit?
val s0 = CartesianProduct(Seq(0, 0))
val s1 = Seq(0, 0)
println(s0 * s1) // List(List(0, 0), List(0, 0), List(0, 0), List(0, 0))
回答by turtlemonvh
Here is something similar to Milad's response, but non-recursive.
这是类似于Milad's response 的内容，但不是递归的。
def cartesianProduct[T](seqs: Seq[Seq[T]]): Seq[Seq[T]] = {
seqs.foldLeft(Seq(Seq.empty[T]))((b, a) => b.flatMap(i => a.map(j => i ++ Seq(j))))
}
Based off this blog post.
基于这篇博文。
回答by Apoorv Shrivastava
Similar to other responses, just my approach.
与其他响应类似，只是我的方法。
def loop(lst: List[List[Int]],acc:List[Int]): List[List[Int]] = {
lst match {
case head :: Nil => head.map(_ :: acc)
case head :: tail => head.flatMap(x => loop(tail,x :: acc))
case Nil => ???
}
}
val l1 = List(10,20,30,40)
val l2 = List(2,4,6)
val l3 = List(3,5,7,9,11)
val lst = List(l1,l2,l3)
loop(lst,List.empty[Int])
