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

Answer 2

Well one more way:

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

Answer 3

One more solution, very similar to accepted answer, but imho this is more readable:

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