将列表组合概括为N个列表

Question

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

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

Answer 2

还有一个方法:

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