## Thursday, June 19, 2014

### 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 2N (why?). That is, there are 2N subsets associated with 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;
}