How to generate the power set of a set in Scala

powerset, scala, set

Solution

Notice that if you have a set `S` and another set `T` where `T = S ∪ {x}` (i.e. `T` is `S` with one element added) then the powerset of `T` - `P(T)` - can be expressed in terms of `P(S)` and `x` as follows:

P(T) = P(S) ∪ { p ∪ {x} | p ∈ P(S) }

That is, you can define the powerset recursively (notice how this gives you the size of the powerset for free - i.e. adding 1-element doubles the size of the powerset). So, you can do this tail-recursively in scala as follows:

scala> def power[A](t: Set[A]): Set[Set[A]] = {
   |     @annotation.tailrec 
   |     def pwr(t: Set[A], ps: Set[Set[A]]): Set[Set[A]] =
   |       if (t.isEmpty) ps
   |       else pwr(t.tail, ps ++ (ps map (_ + t.head)))
   |
   |     pwr(t, Set(Set.empty[A])) //Powerset of ∅ is {∅}
   |   }
power: [A](t: Set[A])Set[Set[A]]

Then:

scala> power(Set(1, 2, 3))
res2: Set[Set[Int]] = Set(Set(1, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), Set(1, 2))

It actually looks much nicer doing the same with a `List` (i.e. a recursive ADT):

scala> def power[A](s: List[A]): List[List[A]] = {
   |     @annotation.tailrec 
   |     def pwr(s: List[A], acc: List[List[A]]): List[List[A]] = s match {
   |       case Nil     => acc 
   |       case a :: as => pwr(as, acc ::: (acc map (a :: _)))
   |     }
   |     pwr(s, Nil :: Nil)
   |   }
power: [A](s: List[A])List[List[A]]

Problem

I have a Set of items of some type and want to generate its power set. I searched the web and couldn't find any Scala code that adresses this specific task. This is what I came up with. It allows you to restrict the cardinality of the sets produced by the length parameter. ``` def power[T](set: Set[T], length: Int) = { var res = Set[Set[T]]() res ++= set.map(Set(_)) for (i <- 1 until length) res = res.map(x => set.map(x + _)).flatten res } ``` This will not include the empty set. To accomplish this you would have to change the last line of the method simply to res + Set() Any suggestions how this can be accomplished in a more functional style?

Original source