list - 将列表组合推广到 N 个列表

Question

在 Scala 中生成已知数量列表的组合非常简单。您可以使用 for-comprehension:

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]] = ???

有任何想法吗？

Answer 1

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))