How to generate the power set of a set in Scala

Question

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?

Suctorial

Answer 1

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

Personate

Answer 2

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()
Set(1)
Set(2)
Set(3)
Set(1, 2)
Set(1, 3)
Set(2, 3)
Set(1, 2, 3)

Civilization

Answer 3

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(1)
List(2, 3)
List(2)
List(3)
List()

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

Sanalda

I love that - my question would be, what else is filterM used for? – Personate

@Personate 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. – Ibnsina

It is built-in by the way: List(1, 2, 3).powerset. :) – Ibnsina

@oxbow_lakes: let doYouLike it = fmap (== "y") $ putStr ("do you like " ++ show it ++ " (y/n)? ") >> getLine in filterM doYouLike ["scala", "haskell"] – Sanalda

filterM and friends are quite useful for M=[a]State[X, a]. You could, for example, filter out repeats with: gist.github.com/3157243 – Carmel

Answer 4

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)
(0 to xs.size).flatMap(xs.toSeq.combinations).map(_.toSet).toSet

//Set(Set(1, 2, 3), Set(2, 3), Set(), Set(3), Set(2), Set(1), Set(1, 3), 
//Set(1, 2))

Civilization

But with set, does it maintain lexicographic set? – Wormy

Answer 5

Can be as simple as:

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = 
  xs.foldLeft(Seq(Seq[A]())) {(sets, set) => sets ++ sets.map(_ :+ set)}

Recursive implementation:

def powerSet[A](xs: Seq[A]): Seq[Seq[A]] = {
  def go(xsRemaining: Seq[A], sets: Seq[Seq[A]]): Seq[Seq[A]] = xsRemaining match {
    case Nil => sets
    case y :: ys => go(ys, sets ++ sets.map(_ :+ y))
  }

  go(xs, Seq[Seq[A]](Seq[A]()))
}

Togs

While this code may answer the question, it would be better to include some context, explaining how it works and when to use it. Code-only answers are not useful in the long run. – Forrest

Kudos for foldLeft. I was looking for that implementation specifically. As an earlier commenter said, an explanation would be nice. – Hanging

Answer 6

All the other answers seemed a bit complicated, here is a simple function:

    def powerSet (l:List[_]) : List[List[Any]] =
      l match {
       case Nil => List(List())
       case x::xs =>
         var a = powerSet(xs)
         a.map(n => n:::List(x)):::a
      }

so

    powerSet(List('a','b','c'))

will produce the following result

    res0: List[List[Any]] = List(List(c, b, a), List(b, a), List(c, a), List(a), List(c, b), List(b), List(c), List())

Laminated

Answer 7

Here's another (lazy) version... since we're collecting ways of computing the power set, I thought I'd add it:

def powerset[A](s: Seq[A]) =
  Iterator.range(0, 1 << s.length).map(i =>
    Iterator.range(0, s.length).withFilter(j =>
      (i >> j) % 2 == 1
    ).map(s)
  )

Rann

Answer 8

Here's a simple, recursive solution using a helper function:

def concatElemToList[A](a: A, list: List[A]): List[Any] = (a,list) match {
    case (x, Nil)                 => List(List(x))
    case (x, ((h:List[_]) :: t))  => (x :: h) :: concatElemToList(x, t)
    case (x, (h::t))              => List(x, h) :: concatElemToList(x, t)
}

def powerSetRec[A] (a: List[A]): List[Any] = a match {
    case Nil    => List()
    case (h::t) => powerSetRec(t) ++ concatElemToList(h, powerSetRec (t))
}

so the call of

powerSetRec(List("a", "b", "c"))

will give the result

List(List(c), List(b, c), List(b), List(a, c), List(a, b, c), List(a, b), List(a))

Katabasis

The empty set is missing from the results – Togs