15
\$\begingroup\$

Given a typelist, return a typelist of all the permutations of it. For example:

using Types = typelist<char, int, double>;
using Permutations = typelist<
    typelist<char, int, double>,
    typelist<char, double, int>,
    typelist<int, char, double>,
    typelist<int, double, char>,
    typelist<double, char, int>,
    typelist<double, int, char>
    >;

static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

There are two different ways of writing metafunction "overloads": partial specialization or function overloading. I'm still unsure of which is "better", and in this solution I ended up using both, which strikes me as questionable.

The algorithm here is: the permutations of a list is the concatenation of (each element in the list prepended to all the permutations of the list with that element removed).

template <class...> struct typelist { };
template <class T> struct tag { using type=T; };

// remove first instance of type from a typelist
template <class T, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<T, Ts...>, typelist<Rs...>)
    -> tag<typelist<Rs..., Ts...>>;

template <class T, class F, class... Ts, class... Rs>
auto remove_first(tag<T>, typelist<F, Ts...>, typelist<Rs...>)
    -> decltype(remove_first(tag<T>{}, typelist<Ts...>{}, typelist<Rs..., F>{}));

template <class T, class TL>
using remove_first_t = typename decltype(remove_first(tag<T>{}, TL{}, typelist<>{}))::type;

// concatenate lots of typelists into one typelist
template <class TL>
auto concat(TL ) -> tag<TL>;

template <class... A, class... B, class... Cs>
auto concat(typelist<A...>, typelist<B...>, Cs... cs)
    -> decltype(concat(typelist<A..., B...>{}, cs...));

template <class... Ts>
using concat_t = typename decltype(concat(Ts{}...))::type;

// prepend a type onto a typelist of typelists
template <class T, class... TLs>
auto prepend(tag<T>, typelist<TLs...>)
    -> tag<typelist<concat_t<typelist<T>, TLs>...>>;

template <class T, class TL>
using prepend_t = typename decltype(prepend(tag<T>{}, TL{}))::type;

// get all the permutations of a typelist
template <class T, class=void>
struct permute : tag<typelist<T>> { };

template <class T>
using permute_t = typename permute<T>::type;

template <class... Ts>
struct permute<typelist<Ts...>, std::enable_if_t<(sizeof...(Ts)>1)>>
    : tag<
        concat_t<
            prepend_t<
                Ts,
                permute_t<remove_first_t<Ts, typelist<Ts...>>>
            >...
        >
    >
{ };
\$\endgroup\$
  • 1
    \$\begingroup\$ Out of curiosity: what are the uses of doing this? \$\endgroup\$ – user2296177 Nov 21 '15 at 19:30
  • \$\begingroup\$ I don't have a compiler at hand, but I think you could also use a compile time "random number generator", and generate just one permutation of the typelist (unless you really want all permutations, I don't know). For this, I'd use the idea of Neves and Araujo, see Fig. 3 and the discussion after it. Is this helpful? \$\endgroup\$ – Juho Nov 26 '15 at 12:59
  • \$\begingroup\$ @Quuxplusone Thanks! I have no idea how that happened, I thought I just copy/pasted the code in ::shrug:: \$\endgroup\$ – Barry Jan 5 '16 at 18:31
  • \$\begingroup\$ Do you allow types in type-list to be non-unique? \$\endgroup\$ – Jan Korous Jun 10 '16 at 20:48
3
\$\begingroup\$

You might have some bug in the algorithm.

"testdata"

struct A {};
struct B {};
struct C {};
struct D {};

using Types = typelist<A, B, C, D>;
using Permutations = typelist<
    typelist<A,B,C,D>,
    typelist<A,B,D,C>,
    typelist<A,C,B,D>,
    typelist<A,C,D,B>,
    typelist<A,D,B,C>,
    typelist<A,D,C,B>,
    typelist<B,A,D,C>,
    typelist<B,A,C,D>,
    typelist<B,C,D,A>,
    typelist<B,C,A,D>,
    typelist<B,D,C,A>,
    typelist<B,D,A,C>,
    typelist<C,A,B,D>,
    typelist<C,A,D,B>,
    typelist<C,B,A,D>,
    typelist<C,B,D,A>,
    typelist<C,D,A,B>,
    typelist<C,D,B,A>,
    typelist<D,A,C,B>,
    typelist<D,A,B,C>,
    typelist<D,B,C,A>,
    typelist<D,B,A,C>,
    typelist<D,C,B,A>,
    typelist<D,C,A,B>
>;
static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");

results in:

prog.cpp:90:1: error: static assertion failed: !
 static_assert(std::is_same<permute_t<Types>, Permutations>{}, "!");
 ^
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.