## 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 2^{n}−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.

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