## 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 2n 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 sk. 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 sk to the permutations of the smaller set S - { sk }. Here are two programs to compute the permutations of a set based on this idea.

## 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;
}



## Thursday, June 12, 2014

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