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.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
9 Comments »

9 Responses to “Powerset”

  1. FA said
    July 7, 2015 at 10:07 AM

    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
    July 7, 2015 at 2:47 PM

    Haskell:

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

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

  3. Mike said
    July 7, 2015 at 9:22 PM 
    import itertools as it

def powerset(lst):
	for n in range(len(lst)+1):
		yield from it.combinations(lst, n)
  4. Jussi Piitulainen said
    July 8, 2015 at 6:16 AM

    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. Catalin Cristu (@catalin_c) said
    July 8, 2015 at 12:38 PM

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

}
  6. matthew said
    July 8, 2015 at 7:26 PM

    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]]
  8. Mark said
    July 25, 2015 at 4:04 AM

    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;
}
  9. Mark said
    July 25, 2015 at 4:06 AM

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


    #include <algorithm>
    #include <iostream>
    #include <iterator>
    #include <regex>
    #include <string>
    #include <vector>
    using set_t = std::vector<std::string>;
    std::vector<set_t> powerset(const set_t &set) {
    std::vector<set_t> 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

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: