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):
from itertools import compress def poweriter(data): for n in range(2 ** len(data)): yield list(compress(data, map(int, reversed(bin(n)[2:]))))A Java version:
import java.math.BigInteger; import java.util.*; import static java.math.BigInteger.ONE; import static java.math.BigInteger.ZERO; public class PowerSet { public static <T> Set<Set<T>> of(Set<T> set) { List<T> items = new ArrayList<>(set); Set<Set<T>> powerSet = new HashSet<>(); BigInteger max = new BigInteger("2").pow(set.size()); for (BigInteger b = ZERO; b.compareTo(max) < 0; b = b.add(ONE)) { Set<T> subSet = new HashSet<>(); for (int i = 0; i < b.bitLength(); i++) { if (b.testBit(i)) { subSet.add(items.get(i)); } } powerSet.add(subSet); } return powerSet; } public static void main(String[] args) { Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3)); Set<Set<Integer>> powerSet = of(set); System.out.println(powerSet); } }Here’s three solutions in Haskell – just for fun, we generate the subsets in Gray code order. pset3 also works with lazy lists:
f t a = t ++ map (a:) (reverse t) g t [] = [] g t (a:s) = u ++ g (t ++ u) s where u = map (a:) (reverse t) pset1 = map reverse . foldl f [[]] pset2 = map reverse . foldr (flip f) [[]] . reverse pset3 = map reverse . ([]:) . g [[]] main = print (pset1 [1,2,3,4]) >> print (pset2 [1,2,3,4]) >> print (pset3 [1,2,3,4]) >> print (take 16 (pset3 [1..])) -- [[[],[1],[1,2],[2],[2,3],[1,2,3],[1,3],[3],[3,4],[1,3,4],[1,2,3,4],[2,3,4],[2,4],[1,2,4],[1,4],[4]]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++:
#include #include #include #include #include #include using set_t = std::vector; std::vector powerset(const set_t &set) { std::vector result {{}}; for (const std::string &item : set) { std::size_t n = result.size(); for (std::size_t i = 0; i length() != 0) { set.push_back(*it); } } auto pset = powerset(set); std::cout << '('; for (auto it = pset.begin(); it != pset.end(); ++it) { if (it != pset.begin()) { std::cout << ' '; } std::cout <begin(); iit != it->end(); ++iit) { if (iit != it->begin()) { std::cout << ' '; } std::cout << *iit; } std::cout << ')'; } std::cout << ')' << std::endl; } return 0; }Huh… sorry, my posted solution got mangled. Here it is in full: