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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
powerset.cc
hosted with ❤ by GitHub