CODEWITHSUNDEEP
scalafunctional-programmingcombinations
Bob
Bob

Reputation: 879

Generate combinations using items from different sets in Scala

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

Upvotes: 2

Views: 306

Answers (3)

Ivan Golovach
Ivan Golovach

Reputation: 209

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.

Upvotes: 1

TRuhland
TRuhland

Reputation: 126

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
    }

Upvotes: 1

Michael Kopaniov
Michael Kopaniov

Reputation: 957

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

Upvotes: 4

Related Questions