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

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
      }
  }
}
许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top