Generate combinations using items from different sets in Scala

Question

Let's say I have a list of sets, for example

scala> val a = List(Set(1, 2, 3), Set(4, 5), Set(6, 7, 8, 9))

I would like to produce a list with all possible combinations of items, each for every set in the list (in a functional fashion). For example,

List(Set(1, 4, 6), Set(1, 4, 7), ...)

Duplicate, look for "cross product" or "product", see e.g. https://stackoverflow.com/questions/8217764/cartesian-product-of-two-lists. — uberwach, Jul 07 '16 at 15:08
What problems did you encounter when you tried implementing it yourself? — Dima, Jul 07 '16 at 16:45

score 4 · Answer 1 · answered Jul 12 '16 at 13:42

4

input.foldLeft(List[Set[Int]](Set.empty)) {
  case (acc, set) =>
    for {
      accSet <- acc
      n <- set
    } yield accSet + n
}

answered Jul 12 '16 at 13:42

Michael Kopaniov

957
9
17

score 1 · Answer 2 · answered Jul 14 '16 at 15:19

Just adding a bit of generalization to Michael's answer, to cover requirement for "items":

  def setCombos[A](xsa: List[Set[A]]): List[Set[A]] =
    xsa.foldLeft(List[Set[A]](Set.empty)) {
      (acc, set) =>
        for {
          accSet <- acc
          n <- set
        } yield accSet + n
    }

score 1 · Answer 3 · answered Jul 18 '16 at 14:09

object Demo extends App {
  def cartesian[T](x: List[List[T]]): List[List[T]] = {
    def partialCartesian(x: List[T], y: List[List[T]]): List[List[T]] =
      for {
        head <- x
        tail <- y
      } yield head +: tail

    x match {
      case head :: Nil => head.map(List(_))
      case head :: tail => partialCartesian(head, cartesian(tail))
    }
  }

  val a = List(List(1, 2, 3), List(4, 5), List(6, 7, 8, 9))
  cartesian(a).foreach(println)
}

>> List(1, 4, 6)
>> List(1, 4, 7)
>> List(1, 4, 8)
>> List(1, 4, 9)
>> List(1, 5, 6)
>> List(1, 5, 7)
>> List(1, 5, 8)
>> List(1, 5, 9)
>> List(2, 4, 6)
>> List(2, 4, 7)
>> List(2, 4, 8)
>> List(2, 4, 9)
>> List(2, 5, 6)
>> List(2, 5, 7)
>> List(2, 5, 8)
>> List(2, 5, 9)
>> List(3, 4, 6)
>> List(3, 4, 7)
>> List(3, 4, 8)
>> List(3, 4, 9)
>> List(3, 5, 6)
>> List(3, 5, 7)
>> List(3, 5, 8)
>> List(3, 5, 9)

I use 'List' not 'Set' - for shortest code. P.S. Sorry for my english.

Generate combinations using items from different sets in Scala

3 Answers3