5

在 Scala 中生成已知数量的列表的组合非常简单。您可以使用理解：

for {
   elem1 <- list1
   elem2 <- list2 } yield List(elem1, elem2)

或者您可以使用脱糖版本：

list1.flatMap( elem1 => list2.map(elem2 => List(elem1,elem2)))

在套件之后，我想从 N 个列表中创建元素的组合（N 在运行时是已知的）。按照组合器示例，3 个列表将是：

list1.flatMap( elem1 => list2.flatMap(elem2 => list3.map(elem3 => List(elem1,elem2,elem3)))

所以我看到了这个模式，我知道那里有一个递归，但我一直在努力把它固定下来。

def combinations[T](lists:List[List[T]]): List[List[T]] = ???

有任何想法吗？

4

3 回答 3

8 
def combinationList[T](ls:List[List[T]]):List[List[T]] = ls match {
     case Nil => Nil::Nil
     case head :: tail => val rec = combinationList[T](tail)
                          rec.flatMap(r => head.map(t => t::r))
}


scala> val l = List(List(1,2,3,4),List('a,'b,'c),List("x","y"))
l: List[List[Any]] = List(List(1, 2, 3, 4), List('a, 'b, 'c), List(x, y))

scala> combinationList(l)
res5: List[List[Any]] = List(List(1, 'a, x), List(2, 'a, x), List(3, 'a, x),
  List(4, 'a, x), List(1, 'b, x), List(2, 'b, x), List(3, 'b, x), List(4, 'b, x),
  List(1, 'c, x), List(2, 'c, x), List(3, 'c, x), List(4, 'c, x), List(1, 'a, y),
  List(2, 'a, y), List(3, 'a, y), List(4, 'a, y), List(1, 'b, y), List(2, 'b, y),
  List(3, 'b, y), List(4, 'b, y), List(1, 'c, y), List(2, 'c, y), List(3, 'c, y),
  List(4, 'c, y))
于 2013-11-04T13:57:49.963 回答
5

还有一种方法：

def merge[T](a: List[List[T]],b:List[T]) = a match {
    case List() => for(i <- b) yield List(i) 
    case xs => for{ x <- xs; y<- b } yield y ::x 
}

scala> def com[T](ls: List[List[T]]) =  ls.foldLeft(List(List[T]()))((l,x) => merge(l,x))

scala> val l = List(List(1,2,3,4),List('a,'b,'c),List("x","y"))
l: List[List[Any]] = List(List(1, 2, 3, 4), List('a, 'b, 'c), List(x, y))

scala> com(l)
res1: List[List[Any]] = List(List(x, 'a, 1), List(y, 'a, 1), List(x, 'b, 1), Lis
t(y, 'b, 1), List(x, 'c, 1), List(y, 'c, 1), List(x, 'a, 2), List(y, 'a, 2), Lis
t(x, 'b, 2), List(y, 'b, 2), List(x, 'c, 2), List(y, 'c, 2), List(x, 'a, 3), Lis
t(y, 'a, 3), List(x, 'b, 3), List(y, 'b, 3), List(x, 'c, 3), List(y, 'c, 3), Lis
t(x, 'a, 4), List(y, 'a, 4), List(x, 'b, 4), List(y, 'b, 4), List(x, 'c, 4), Lis
t(y, 'c, 4))
于 2013-11-04T14:19:50.480 回答
1

另一种解决方案，与公认的答案非常相似，但恕我直言，这更具可读性：

def helper[T](x: List[List[T]]): List[List[T]] = {
  x match {
    case Nil => List(Nil)
    case head :: tail => {
        for (
          n <- head;
          t <- helper(tail)
        ) yield n :: t
      }
  }
}
于 2017-06-11T23:42:05.903 回答