patterncppMinor

Permuting a typelist

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

permutingtypeliststackoverflow

Problem

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

using Types = typelist;
using Permutations = typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist
    >;

static_assert(std::is_same, 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  struct typelist { };
template  struct tag { using type=T; };

// remove first instance of type from a typelist
template 
auto remove_first(tag, typelist, typelist)
    -> tag>;

template 
auto remove_first(tag, typelist, typelist)
    -> decltype(remove_first(tag{}, typelist{}, typelist{}));

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

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

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

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

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

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

// get all the permutations of a typelist
template 
struct permute : tag> { };

template 
using permute_t = typename permute::type;

template 
struct permute, std::enable_if_t1)>>
    : tag>>
            >...
        >
    >
{ };

Solution

You might have some bug in the algorithm.

"testdata"

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

using Types = typelist;
using Permutations = typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist,
    typelist
>;
static_assert(std::is_same, Permutations>{}, "!");

results in:

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

Code Snippets

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>{}, "!");

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

Context

StackExchange Code Review Q#111425, answer score: 3

Revisions (0)

No revisions yet.