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.

Advertisements

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

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

    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]]
    
  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:

Leave a Reply

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

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

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

Facebook photo

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

w

Connecting to %s

%d bloggers like this: