## Powerset

### July 7, 2015

We begin by noting that the cardinality of the powerset of a set is exponential in the cardinality of the set, so any solution we create won’t scale very well. We represent sets as lists.

The canonical Scheme implementation of powersets uses recursion to insert the first item of the set in each set in the powerset of the remainders of the set; we used exactly this function in a previous exercise:

```(define (power-set xs)   (if (null? xs) (list (list))     (let ((rest (power-set (cdr xs))))       (append rest (map (lambda (x) (cons (car xs) x)) rest)))))```

``` ```

```> (power-set 1 2 3) (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))```

An alternate implementation uses binary numbers; for each 1-bit in the binary representation of the numbers from 0 to 2n−1, where n is the cardinality of the set, include the corresponding element in the outgoing subset. Here bits calculates the bits of n, including leading zeros, and collect makes a set of elements corresponding to 1-bits:

```(define (bits n len)   (let loop ((n n) (len len) (bs (list)))     (if (zero? len) bs       (loop (quotient n 2) (- len 1)             (cons (if (odd? n) 1 0) bs)))))```

``` (define (collect n xs)   (let loop ((bs (bits n (length xs))) (xs xs) (zs (list)))     (if (null? bs) zs       (loop (cdr bs) (cdr xs)         (if (zero? (car bs)) zs (cons (car xs) zs)))))) (define (power-set xs)   (do ((n 0 (+ n 1)) (xss (list) (cons (collect n xs) xss)))       ((= n (expt 2 (length xs))) xss))) ```

```> (power-set 1 2 3) ((3 2 1) (2 1) (3 1) (1) (3 2) (2) (3) ())```

The binary implementation is especially useful when the need is to generate the subsets and operate on each in turn, as there is no need to store the intermediate results:

```(define (for-power-set op xs)   (let ((len (length xs)))     (do ((n 0 (+ n 1))) ((= n (expt 2 len)))       (op (collect n xs)))))```

``` ```

```> (for-power-set (lambda (s) (display s) (newline)) '(1 2 3)) () (3) (2) (3 2) (1) (3 1) (2 1) (3 2 1)```

You can run the program at http://ideone.com/MBPxVm.

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:

 #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 < n; ++i) { set_t rset = result[i]; rset.push_back(item); result.push_back(rset); } } return result; } int main() { const std::regex token_re("[(),\\s]+"); while (true) { std::string input; set_t set; std::getline(std::cin, input); if (input.length() == 0) { break; } for (auto it = std::sregex_token_iterator(input.begin(), input.end(), token_re, –1); it != std::sregex_token_iterator(); ++it) { if (it->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 << '('; for (auto iit = it->begin(); iit != it->end(); ++iit) { if (iit != it->begin()) { std::cout << ' '; } std::cout << *iit; } std::cout << ')'; } std::cout << ')' << std::endl; } return 0; }

view raw
powerset.cc
hosted with ❤ by GitHub