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.
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:
powerset.cc
hosted with ❤ by GitHub