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))
Generalize list combinations to N lists
-
03-07-2022 - |
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?
Solution
OTHER TIPS
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))
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
}
}
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow