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

    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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: