Take the 2-minute tour ×

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


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?

share|improve this question
add comment

4 Answers

up vote 14 down vote accepted

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


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]]
share|improve this answer
Thanks, this is nicer code than mine. I'll use yours. :) –  Björn Jacobs Jul 20 '12 at 15:02
No problem - this is actually one of my interview questions :-s –  oxbow_lakes Jul 20 '12 at 15:06
So, do I get the job? :) –  Luigi Plinge Jul 20 '12 at 15:20
No - you fail :-) - in my question, there is no scala! –  oxbow_lakes Jul 20 '12 at 15:31
add comment

Here's one of the more interesting ways to write it:

import scalaz._, Scalaz._

def powerSet[A](xs: List[A]) = xs filterM (_ => true :: false :: Nil)

Which works as expected:

scala> powerSet(List(1, 2, 3)) foreach println
List(1, 2, 3)
List(1, 2)
List(1, 3)
List(2, 3)

See for example this discussion thread for an explanation of how it works.

(And as debilski notes in the comments, ListW also pimps powerset onto List, but that's no fun.)

share|improve this answer
I love that - my question would be, what else is filterM used for? –  oxbow_lakes Jul 20 '12 at 15:45
@oxbow_lakes You can for example do a three-way predicate filter. (x => if ... None/Some(false)/Some(true)). A single None would clear the whole input. But I guess there will be much more advanced usages with exotic monads I‘ve never heard of. –  Debilski Jul 20 '12 at 16:04
It is built-in by the way: List(1, 2, 3).powerset. :) –  Debilski Jul 20 '12 at 16:09
@oxbow_lakes: let doYouLike it = fmap (== "y") $ putStr ("do you like " ++ show it ++ " (y/n)? ") >> getLine in filterM doYouLike ["scala", "haskell"] –  Travis Brown Jul 20 '12 at 17:01
filterM and friends are quite useful for M=[a]State[X, a]. You could, for example, filter out repeats with: gist.github.com/3157243 –  retronym Jul 21 '12 at 21:47
show 1 more comment

Looks like no-one knew about it back in July, but there's a built-in method: subsets.

scala> Set(1,2,3).subsets foreach println
Set(1, 2)
Set(1, 3)
Set(2, 3)
Set(1, 2, 3)
share|improve this answer
add comment

Use the built-in combinations function:

val xs = Seq(1,2,3)
(0 to xs.size) flatMap xs.combinations

// Vector(List(), List(1), List(2), List(3), List(1, 2), List(1, 3), List(2, 3),
// List(1, 2, 3))

Note, I cheated and used a Seq, because for reasons unknown, combinations is defined on SeqLike. So with a set, you need to convert to/from a Seq:

val xs = Set(1,2,3)
val ys = xs.toSeq
(0 to xs.size).flatMap(ys.combinations).map(_.toSet).toSet

//Set(1, 2))
share|improve this answer
add comment

Your Answer


