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))
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))
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With