## 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.

Pages: 1 2

### 9 Responses to “Powerset”

1. FA said

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

2. Francesco said

```import Control.Monad
let f xs = filterM (\x -> [True, False]) xs
```

λ> f [1,2,3]
[[1,2,3],[1,2],[1,3],,[2,3],,,[]]

3. Mike said
```import itertools as it

def powerset(lst):
for n in range(len(lst)+1):
yield from it.combinations(lst, n)
```
4. Jussi Piitulainen said

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:]))))
```
5. 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)) {
}
}
}
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);
}

}
```
6. matthew said

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,2],,[2,3],[1,2,3],[1,3],,[3,4],[1,3,4],[1,2,3,4],[2,3,4],[2,4],[1,2,4],[1,4],]
```
7. Mark said

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;
}
```
8. Mark said

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