### Powerset

If *S* is a set, then *P(S)*, the 'powerset' of *S* is the set of all subsets of *S* including the empty set and *S* itself. If *S* has cardinality *N* then the cardinality of *P(S)* is *2 ^{N}* (why?). That is, there are

*2*subsets associated with

^{N}*S*.

Here's a function to compute *P(S)* in OCaml. It's an instance of the 'divide and conquer' strategy of problem solving.

let rec sets l = match l with | [] -> [[]] | x :: xs -> let l = sets xs in l @ (List.map (fun y -> x :: y) l)

This program translates to C++ naturally and with brevity thanks to C++ 11 lambdas.

#include <boost/utility.hpp> #include <set> #include <iterator> #include <algorithm> template <class I, class D> D sets (I begin, I end, D dst) { typedef typename std::iterator_traits<I>::value_type value_type; typedef std::set<value_type> set_t; if (begin == end) { *dst++ = set_t (); //the empty set } else { std::set<set_t> l; std::set<set_t>::iterator back=l.end (); sets (boost::next (begin), end, std::inserter (l, back)); std::transform (l.begin (), l.end (), dst, [](set_t const& s) -> set_t const& { return s; }); std::transform (l.begin (), l.end (), dst, [=](set_t s) -> set_t { s.insert (*begin); return s; }); } return dst; }