How to generate the power set of a set in Scala

问题:

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?

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

回答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)

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

回答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))

回答5:

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

回答6:

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]()))
}

回答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)
  )

回答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))