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.

Advertisement

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:


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

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 )

Connecting to %s

%d bloggers like this: