Generalize list combinations to N lists

Question

Generating the combination of a known number of lists is quite simple in Scala. You can either use a for-comprehension:

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

Or you can use the de-sugarized version:

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

Following suite, I would like to create combinations of elements from N lists (N is known at runtime). Following the combinators example, 3 lists would be:

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

so I see the pattern and I know there's a recursion there, but I've been struggling to pin it down.

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

Any ideas?

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