# Generating all permutations of a template pack

AllPermutedPacks<Pack<Types...>>::type is to be the pack of packs consisting of all permutations of Types.... For example, AllPermutedPacks<Pack<int, char, double>>::type is to be:

Pack<Pack<int, char, double>, Pack<int, double, char>, Pack<char, int, double>, Pack<char, double, int>, Pack<double, int, char>, Pack<double, char, int>>


Here's a sketch of my idea:

Let's assume three types A,B,C in the pack. AllPermutedPacks ABC will come from A + AllPermutedPacks BC, B + AllPermutedPacks AC, C + AllPermutedPacks AB, where AllPermutedPacks BC will come from B + AllPermutedPacks C, C + AllPermutedPacks B, and similarly for the others.

So when we are down to just one type T left AllPermutedPacks will just give Pack<Pack<T>>. But how to get BC from ABC?

We must use a helper RemoveFirstTypeFound that removes A from the pack ABC. Similarly, for AC and AB. The + operation described above is from another helper Prepend. But prepending must be done for all the permuted types in the recursion, so PrependToEachPack must be defined too. Also we must merge the accumulated pack of packs to the newly generated pack of packs each time, so Merge must also be defined.

Perhaps this plan of mine is more complicated than it needs to be, which is why I'm seeking a better (and shorter) solution. Here is my full solution using the above plan:

#include <iostream>
#include <type_traits>

template <typename, typename, typename...> struct RemoveFirstTypeFound;

template <typename T> struct Identity { using type = T; };

template <typename RemoveMe, template<typename...> class P, typename First, typename... Rest, typename... Types>
struct RemoveFirstTypeFound<RemoveMe, P<First, Rest...>, Types...> : std::conditional<std::is_same<RemoveMe, First>::value,
Identity<P<Types..., Rest...>>,
RemoveFirstTypeFound<RemoveMe, P<Rest...>, Types..., First>
>::type {};

template <typename, typename> struct Prepend;

template <typename T, template <typename...> class P, typename... Types>
struct Prepend<T, P<Types...>> {
using type = P<T, Types...>;
};

template <typename, typename> struct PrependToEachPack;

template <typename T, template <typename...> class P, typename... Packs>
struct PrependToEachPack<T, P<Packs...>> {
using type = P<typename Prepend<T, Packs>::type...>;
};

template <typename, typename> struct Merge;

template <template <typename...> class P, typename... Types1, typename... Types2>
struct Merge<P<Types1...>, P<Types2...>> {
using type = P<Types1..., Types2...>;
};

template <typename, typename, typename> struct AllPermutedPacksHelper;

template <template<typename...> class P, typename Pack, typename... AccumulatedPacks>
struct AllPermutedPacksHelper<Pack, P<>, P<AccumulatedPacks...>> {
using type = P<AccumulatedPacks...>;
};

template <template<typename...> class P, typename... Types, typename Last>
struct AllPermutedPacksHelper<P<Types...>, P<Last>, P<>> {
using type = P<P<Last>>;
};

template <template<typename...> class P, typename First, typename Pack1, typename Pack2, typename Pack3, typename Pack4>
using AllPermutedPacksHelperAlias = AllPermutedPacksHelper<Pack1, Pack2, typename Merge<Pack3,
typename PrependToEachPack<First, typename AllPermutedPacksHelper<Pack4, Pack4, P<>>::type>::type>::type>;

template <template<typename...> class P, typename... Types, typename... AccumulatedPacks, typename First, typename... Rest>
struct AllPermutedPacksHelper<P<Types...>, P<First, Rest...>, P<AccumulatedPacks...>> :
AllPermutedPacksHelperAlias<P, First, P<Types...>, P<Rest...>, P<AccumulatedPacks...>, typename RemoveFirstTypeFound<First, P<Types...>>::type> {};

template <typename> struct AllPermutedPacks;

template <template<typename...> class P, typename... Types>
struct AllPermutedPacks<P<Types...>> : AllPermutedPacksHelper<P<Types...>, P<Types...>, P<>> {};

// -----------------------------------------------------------------------------------------------------------------------------------------------
// Testing

template <typename...> struct Pack {};

int main() {
std::cout << std::boolalpha << std::is_same< AllPermutedPacks<Pack<>>::type,
Pack<>
>::value << std::endl;  // true

std::cout << std::is_same< AllPermutedPacks<Pack<int>>::type,
Pack<Pack<int>>
>::value << std::endl;  // true

std::cout << std::is_same< AllPermutedPacks<Pack<int, char>>::type,
Pack<Pack<int, char>, Pack<char, int>>
>::value << std::endl;  // true

std::cout << std::is_same< AllPermutedPacks<Pack<int, char, double>>::type,
Pack<Pack<int, char, double>, Pack<int, double, char>, Pack<char, int, double>, Pack<char, double, int>, Pack<double, int, char>, Pack<double, char, int>>
>::value << std::endl;  // true
}


Can someone suggest a shorter method? I know that RemoveFirstTypeFound<First, P<Types...>>::type is being computed twice so another helper can be used to use it just once, but apart from that?

Update: I shortened my original solution slightly by taking care of the repetition I just mentioned (though now it is perhaps harder to read). But I know there is a shorter and more elegant solution than this. I tried all day to think of a better way, but can't. This question is not insanely hard, so the solution should not be so long.

• Are all types different in your scenario, or do you want to allow for doublons? Commented Nov 7, 2018 at 9:18

I think I've found a better solution. This is shorter in code, and also more efficient because the O(N) RemoveFirstTypeFound metafunction is not being used at all.

#include <type_traits>
#include <utility>

namespace utilities {
template <typename Pack1, typename Pack2> struct merge;

template <template <typename...> class P, typename... Ts, typename... Us>
struct merge<P<Ts...>, P<Us...>> {
using type = P<Ts..., Us...>;
};
}

template <std::size_t R, typename Pack, typename TypesIgnored, typename Output, typename = void> struct nPr_h;

template <template <typename...> class P, typename First, typename... Rest, typename... TypesIgnored, typename... Output>
struct nPr_h<0, P<First, Rest...>, P<TypesIgnored...>, P<Output...>> {
// Just one single pack (which must be wrapped in P so that the resulting merge
// will give all such single packs, rather than a merge of all the types).
using type = P<P<Output...>>;
};

template <std::size_t R, template <typename...> class P, typename TypesIgnored, typename Output>
struct nPr_h<R, P<>, TypesIgnored, Output> {
// No pack can come out of this (permuting R types from nothing).
using type = P<>;
};

template <std::size_t R, template <typename...> class P, typename First, typename... Rest, typename... TypesIgnored, typename... Output>
struct nPr_h<R, P<First, Rest...>, P<TypesIgnored...>, P<Output...>, std::enable_if_t<(R > sizeof...(Rest) + sizeof...(TypesIgnored))>> {
// No pack can come out of this (since there are fewer types in
// P<TypesIgnored..., Rest...> than R).
using type = P<>;
};

template <std::size_t R, template <typename...> class P, typename First, typename... Rest, typename... TypesIgnored, typename... Output>
struct nPr_h<R, P<First, Rest...>, P<TypesIgnored...>, P<Output...>, std::enable_if_t<(R <= sizeof...(Rest) + sizeof...(TypesIgnored) && R != 0)>> : utilities::merge<
// Case 1: 'First' is in the permuted pack (note that Output..., First are the
// types in just one pack).  Now continue to get R-1 more types from
// TypesIgnored..., Rest... (which are the remaining available types since
// 'First' is no longer available for the remaining R-1 types, and the ignored
// types are now P<> since we are starting a new nPr_h call).
typename nPr_h<R-1, P<TypesIgnored..., Rest...>, P<>, P<Output..., First>>::type,
// Case 2: 'First' in not in the permuted pack, so try to get R types from
// Rest... to append to Output...  First is appended to TypesIgnored... since
// it is now among those types not used.
typename nPr_h<R, P<Rest...>, P<TypesIgnored..., First>, P<Output...>>::type
> { };

template <std::size_t R, typename Pack> struct nPr;

template <std::size_t R, template <typename...> class P, typename... Ts>
struct nPr<R, P<Ts...>> : nPr_h<R, P<Ts...>, P<>, P<>> { };

// Testing
template <typename...> struct P;

int main() {
static_assert(std::is_same<
nPr<2, P<int, char, float>>::type,
P<P<int, char>, P<int, float>, P<char, int>, P<char, float>, P<float, int>, P<float, char>>
>::value);

static_assert(std::is_same<
nPr<3, P<int, char, float, bool>>::type,
P<P<int, char, float>, P<int, char, bool>, P<int, float, char>, P<int, float, bool>, P<int, bool, char>, P<int, bool, float>, P<char, int, float>, P<char, int, bool>, P<char, float, int>, P<char, float, bool>, P<char, bool, int>, P<char, bool, float>, P<float, int, char>, P<float, int, bool>, P<float, char, int>, P<float, char, bool>, P<float, bool, int>, P<float, bool, char>, P<bool, int, char>, P<bool, int, float>, P<bool, char, int>, P<bool, char, float>, P<bool, float, int>, P<bool, float, char>>
>::value);
}


Incidentally, here is a longer solution, but one which has the advantage of having the implementation for nCr and all_permutations, which are useful in their own right:

#include <type_traits>
#include <utility>

namespace utilities {
template <typename... Packs> struct merge;

template <typename Pack>
struct merge<Pack> {
using type = Pack;
};

template <template <typename...> class P, typename... Ts, typename... Us>
struct merge<P<Ts...>, P<Us...>> {
using type = P<Ts..., Us...>;
};

template <typename First, typename... Rest>
struct merge<First, Rest...> : merge<First, typename merge<Rest...>::type> { };

template <typename T, typename Pack> struct prepend;

template <template <typename...> class P, typename... Ts, typename T>
struct prepend<T, P<Ts...>> {
using type = P<T, Ts...>;
};

template <typename T, typename PackOfPacks> struct prepend_to_each;

template <typename T, template <typename...> class P, typename... Packs>
struct prepend_to_each<T, P<Packs...>> {
using type = P<typename prepend<T, Packs>::type...>;
};

template <typename Pack> struct pack_size;

template <template <typename...> class P, typename... Ts>
struct pack_size<P<Ts...>> : std::integral_constant<std::size_t, sizeof...(Ts)> { };

//  all_rotations
template <std::size_t, typename> struct rotate;

template <template <typename...> class P, typename First, typename... Rest>
struct rotate<0, P<First, Rest...>> {
using type = P<First, Rest...>;
};

template <std::size_t N, template <typename...> class P, typename First, typename... Rest>
struct rotate<N, P<First, Rest...>> : rotate<N - 1, P<Rest..., First>> { };

template <typename Pack, typename Sequence> struct all_rotations_h;

template <template <typename...> class P, typename... Ts, std::size_t... Is>
struct all_rotations_h<P<Ts...>, std::index_sequence<Is...>> {
using type = P<typename rotate<Is, P<Ts...>>::type...>;
};

template <typename Pack>
struct all_rotations : all_rotations_h<Pack, std::make_index_sequence<pack_size<Pack>::value>> { };
}

// nCr
template <std::size_t R, typename Pack, typename = void> struct nCr;

template <template <typename...> class P, typename... Ts>
struct nCr<1, P<Ts...>> {
using type = P<P<Ts>...>;
};

template <std::size_t R, template <typename...> class P, typename First, typename... Rest>
struct nCr<R, P<First, Rest...>, std::enable_if_t<(R <= sizeof...(Rest) + 1 && R > 1)>> : utilities::merge<
typename utilities::prepend_to_each<First, typename nCr<R-1, P<Rest...>>::type>::type,
typename nCr<R, P<Rest...>>::type
> { };

template <std::size_t R, template <typename...> class P, typename First, typename... Rest>
struct nCr<R, P<First, Rest...>, std::enable_if_t<(R > sizeof...(Rest) + 1)>> {
using type = P<>;
};

// all_permutations
template <typename Pack> struct all_permutations_h;

template <typename PackOfPacks> struct all_permutations_h_on_each;

template <template <typename...> class P, typename... Packs>
struct all_permutations_h_on_each<P<Packs...>> : utilities::merge<typename all_permutations_h<Packs>::type...> { };

template <typename Pack> struct
all_permutations : all_permutations_h_on_each<typename utilities::all_rotations<Pack>::type> { };

template <template <typename...> class P, typename Last>
struct all_permutations_h<P<Last>> {
using type = P<P<Last>>;
};

template <template <typename...> class P, typename First, typename... Rest>
struct all_permutations_h<P<First, Rest...>> : utilities::prepend_to_each<First, typename all_permutations<P<Rest...>>::type> { };

// We now combine nCr with all_permutations to get nPr.
template <typename PackOfPacks> struct all_permutations_on_each_pack;

template <template <typename...> class P, typename... Packs>
struct all_permutations_on_each_pack<P<Packs...>> : utilities::merge<typename all_permutations<Packs>::type...> { };

template <std::size_t R, typename Pack>
struct nPr : all_permutations_on_each_pack<typename nCr<R, Pack>::type> { };

// Testing
template <typename...> struct P;

int main() {
static_assert(std::is_same<
nPr<2, P<int, char, float>>::type,
P<P<int, char>, P<char, int>, P<int, float>, P<float, int>, P<char, float>, P<float, char>>
>::value);

static_assert(std::is_same<
nPr<3, P<int, char, float, bool>>::type,
P<P<int, char, float>, P<int, float, char>, P<char, float, int>, P<char, int, float>, P<float, int, char>, P<float, char, int>, P<int, char, bool>, P<int, bool, char>, P<char, bool, int>, P<char, int, bool>, P<bool, int, char>, P<bool, char, int>, P<int, float, bool>, P<int, bool, float>, P<float, bool, int>, P<float, int, bool>, P<bool, int, float>, P<bool, float, int>, P<char, float, bool>, P<char, bool, float>, P<float, bool, char>, P<float, char, bool>, P<bool, char, float>, P<bool, float, char>>
>::value);
}


Based on the idea to rotate the pack I came up with a shorter solution that generates the permutations of all types. The permutations will not be unique when there are duplicates in the list, but I think that's the right thing to do.

The basic idea is to take all possible rotations of the list of types, and recursively generate permutations of all but the first type for all those rotations. This recurses until only one element is left or all rotations have been done. Here's the complete code and a live demo:

#include <cstddef>
#include <type_traits>

namespace detail {

template <typename P1, typename P2>
struct merge {};

template <template <typename...> class P, typename... Ts, typename... Us>
struct merge<P<Ts...>, P<Us...>> {
using type = P<Ts..., Us...>;
};

template <typename T, typename P>
struct prepend {};

template <typename T, template <typename...> class P, typename... Packs>
struct prepend<T, P<Packs...>> {
using type = P<typename merge<P<T>, Packs>::type...>;
};

// N is the number of rotations to go
template <std::size_t N, typename Pack, typename = void>
struct permutations_impl {};

template <template <typename...> class P, typename... Ts>
struct permutations_impl<0, P<Ts...>> {
// All rotations done, break the recursion
using type = P<>;
};

template <std::size_t N, template <typename...> class P, typename T>
struct permutations_impl<N, P<T>> {
using type = P<P<T>>;
};

template <std::size_t N, template <typename...> class P, typename F, typename... Rest>
struct permutations_impl<N, P<F, Rest...>, std::enable_if_t<(sizeof...(Rest) && N != 0)>> {
using PermuteRest = typename permutations_impl<sizeof...(Rest), P<Rest...>>::type;
using NextRotation = typename permutations_impl<N-1, P<Rest..., F>>::type;

using type = typename merge<typename prepend<F, PermuteRest>::type, NextRotation>::type;
};

} // namespace detail

template <typename Pack>
struct permutations {};

template <template <typename...> class P, typename... Ts>
struct permutations<P<Ts...>> {
using type = typename detail::permutations_impl<sizeof...(Ts), P<Ts...>>::type;
};

template <typename Pack>
using permutations_t = typename permutations<Pack>::type;


I have no idea how to judge the efficiency of my approach, so a comment would be much appreciated if you do.