5

我在 Scala 中有一个列表，如下所示。

val inputList:List[List[Int]] = List(List(1, 2), List(3, 4, 5), List(1, 9))

我想要所有子列表的交叉产品列表。

val desiredOutput: List[List[Int]] = List( 
        List(1, 3, 1), List(1, 3, 9),
        List(1, 4, 1), List(1, 4, 9),
        List(1, 5, 1), List(1, 5, 9),
        List(2, 3, 1), List(2, 3, 9),
        List(2, 4, 1), List(2, 4, 9),
        List(2, 5, 1), List(2, 5, 9))

inputList 和子列表中的元素数量不固定。Scala 的做法是什么？

4

4 回答 4

4

这是一种使用递归的方法。但是它不是尾递归的，所以要小心 stackoverflows。然而，它可以通过使用辅助函数转换为尾递归函数。

def getProduct(input:List[List[Int]]):List[List[Int]] = input match{
  case Nil => Nil // just in case you input an empty list
  case head::Nil => head.map(_::Nil) 
  case head::tail => for(elem<- head; sub <- getProduct(tail)) yield elem::sub
}

测试：

scala> getProduct(inputList)
res32: List[List[Int]] = List(List(1, 3, 1), List(1, 3, 9), List(1, 4, 1), List(1, 4, 9), List(1, 5, 1), List(1, 5, 9), List(2, 3, 1), List(2, 3, 9), List(2, 4, 1), List(2, 4, 9), List(2, 5, 1), List(2, 5, 9))
于 2012-11-26T15:28:35.557 回答
4

如果您使用scalaz，这可能是一个适合的情况Applicative Builder：

import scalaz._
import Scalaz._

def desiredOutput(input: List[List[Int]]) = 
  input.foldLeft(List(List.empty[Int]))((l, r) => (l |@| r)(_ :+ _))

desiredOutput(List(List(1, 2), List(3, 4, 5), List(1, 9)))

我自己对 scalaz 不是很熟悉，我希望它有一些更强大的魔法来做到这一点。

编辑

正如特拉维斯布朗建议的那样，我们只是写

def desiredOutput(input: List[List[Int]]) = input.sequence

我发现这个问题的答案对于理解什么非常有帮助sequence。

于 2012-11-26T16:04:13.637 回答
2

如果你不介意一点函数式编程：

def cross[T](inputs: List[List[T]]) : List[List[T]] = 
    inputs.foldRight(List[List[T]](Nil))((el, rest) => el.flatMap(p => rest.map(p :: _)))

发现它是如何工作的很有趣。:-)

于 2017-06-12T09:42:08.667 回答
1

经过几次尝试，我得出了这个解决方案。

val inputList: List[List[Int]] = List(List(1, 2), List(3, 4, 5), List(1, 9))
val zss: List[List[Int]] = List(List())
def fun(xs: List[Int], zss: List[List[Int]]): List[List[Int]] = {
    for {
        x <- xs
        zs <- zss
    } yield {
        x :: zs
    }
}
val crossProd: List[List[Int]] = inputList.foldRight(zss)(fun _)
println(crossProd)
于 2012-11-26T16:22:54.953 回答