## Powerset

### July 7, 2015

Sets are ubiquitous in programming; we have discussed sets in several previous exercises. One of the operations that can be performed on a set is to compute its powerset, which is a set of all the subsets of the original set. For instance, the powerset of (1 2 3) is the set (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) where neither the order of the subsets nor the order of the elements of the individual subsets matters.

Your task is to write a program that computes the powerset of a set. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Scala:

package programmingpraxis

object PowerSet {

val s = Set[Int](1, 2, 3) //> s : scala.collection.immutable.Set[Int] = Set(1, 2, 3)

//Scala default algorythm:

s.subsets().toList //> res0: List[scala.collection.immutable.Set[Int]] = List(Set(), Set(1), Set(2),

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

//Own dummy algo:

def subsets[T](s: Set[T]): Set[Set[T]] = {

if (s.isEmpty) Set(s);

else {

Set(s)++((for (i subsets: [T](s: Set[T])Set[Set[T]]

subsets(Set(1, 2,3)) //> res1: Set[Set[Int]] = Set(Set(), Set(1, 3), Set(2), Set(1, 2), Set(2, 3), Se

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

}

Haskell:

λ> f [1,2,3]

[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Python’s itertools.compress filters data elements in at 1-bits (True), out at 0-bits (False):

A Java version:

Here’s three solutions in Haskell – just for fun, we generate the subsets in Gray code order. pset3 also works with lazy lists:

Using R7RS Scheme with SRFI-113

https://notabug.org/PangolinTurtle/praxis-solutions/raw/master/07-07-2015.scm

A non-bitset based solution in C++:

Huh… sorry, my posted solution got mangled. Here it is in full: