maasg -4 years ago 63
Scala Question

# Generalize list combinations to N lists

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?

``````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))
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download