Permutations

Permutations

Combinations are selections that disregard order. The powerset P(S) of a set S is the set of all possible combinations of the n elements of S. There are 2ⁿ of these. Permutations are arrangements of sequences into orders. The number of permutations of a set is denoted n! For example, the set {x, y, z} has 6 permutations : {x, y, z}, {x, z, y}, {y, x, z}, {y, z, x}, {z, y, x} and {z, x, y}. Suppose f exists that for given k provides all permutations of S that start with s_k. All permutations could then be found by f with k ranging over [0, N - 1]. But f trivially exists as it can be computed by prepending s_k to the permutations of the smaller set S - { s_k }. Here are two programs to compute the permutations of a set based on this idea.

Powerset

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^N 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;
}

Cartesian product

Cartesian product

For two sets $A$ and $B$, the Cartesian product denoted $A \times B$ is defined as the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. The obvious algorithm to compute a Cartesian product in OCaml can is simple!

let prod l r =
  let g acc a =
    let f acc x =
      (a, x) :: acc
    in List.fold_left f acc r
  in List.fold_left g [] l |> List.rev

A straight-forward translation of the above program into C++ yields this.

#include <boost/range.hpp>
#include <numeric>
#include <iterator>

template <class T>
struct _inner
{
  T a;
  _inner (T a) : a (a) {}
  template <class ItT>
    ItT operator ()(ItT acc, T const& x) const {
    return *acc++ = std::make_pair (a, x);
  }
};
template <class T> 
  _inner<T> inner (T a) { return _inner<T> (a); }

template <class RangeT>
struct _outer
{
  RangeT r;
  _outer (RangeT r) : r (r){}
  template <class T, class ItT>
    ItT operator ()(ItT acc, T const& a) const {
      return std::accumulate (
        boost::begin (r), boost::end(r), acc, inner (a));
  }
};
template <class RangeT>
  _outer<RangeT> outer (RangeT r) { return _outer<RangeT>(r); }

template <class R1, class R2, class ItT>  
ItT prod (R1 A, R2 B, ItT dst) {
  return std::accumulate (
    boost::begin (A), boost::end (A), dst, outer (B));
}

That's a lot more code than in the original OCaml program. But wait... C++11 lambda expressions to the rescue! We can eliminate most of that 'extra' code recovering the elegance of the original.

template <class R1, class R2, class ItT>  
ItT prod (R1 A, R2 B, ItT dst) {

  typedef ItT iterator;
  typedef boost::range_value<R1>::type alpha;
  typedef boost::range_value<R2>::type  beta;

  return std::accumulate (
   boost::begin (A), boost::end (A), dst, 
    [=] (iterator acc, alpha const& a) { 
      return std::accumulate (
        boost::begin (B), boost::end (B), acc, 
        [=] (ItT acc, beta const& x) {
          return *acc++ = std::make_pair (a, x); });
     });
}

Now, my buddy Juan Alday tells me that we can expect more improvements in C++14 relating to lambdas. I hope to persuade him to write more about that here in the next couple of weeks. Stay tuned!

Update: Juan advises that with C++ 14 'generic' lambdas, we can further get it down to this.

auto prod = [](auto const& A, auto const& B, auto dst) {
   return std::accumulate(std::begin(A), std::end(A), dst,
     [&B](auto& output, auto valA) {
      return std::accumulate(std::begin(B), std::end(B), output,
       [&valA](auto& output, auto valB) { 
         std::get<0>(*output) = std::move(valA); 
         std::get<1>(*output) = std::move(valB)); 
         return ++output;});
     });
 };

That's kind of amazing... There's not even one occurrence of the template keyword in that code!