patterncppMinor

Generating all permutations of a template pack

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

Viewed 0 times

templateallpackgeneratingpermutations

Problem

AllPermutedPacks>::type is to be the pack of packs consisting of all permutations of Types.... For example, AllPermutedPacks::type is to be:

Pack, Pack, Pack, Pack, Pack, Pack>

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>. 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
#include

template struct RemoveFirstTypeFound;

template struct Identity { using type = T; };

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

template struct Prepend;

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

template struct PrependToEachPack;

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

template struct Merge;

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

template struct AllPermutedPacksHelper;

template class P, typename Pack, typename... Accum

Solution

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

namespace utilities {
    template  struct merge;

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

template  struct nPr_h;

template  class P, typename First, typename... Rest, typename... TypesIgnored, typename... Output>
struct nPr_h, P, P> {
    // 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>;
};

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

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

template  class P, typename First, typename... Rest, typename... TypesIgnored, typename... Output>
struct nPr_h, P, P, std::enable_if_t> : utilities::merge since we are starting a new nPr_h call).
    typename nPr_h, P<>, P>::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, P, P>::type
> { };

template  struct nPr;

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

// Testing
template  struct P;

int main() {
    static_assert(std::is_same>::type,  
        P, P, P, P, P, P>
    >::value);

    static_assert(std::is_same>::type,
        P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P>
    >::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 
#include 

namespace utilities {
    template  struct merge;

    template 
    struct merge {
        using type = Pack;
    };

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

    template 
    struct merge : merge::type> { };

    template  struct prepend;

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

    template  struct prepend_to_each;

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

    template  struct pack_size;

    template  class P, typename... Ts>
    struct pack_size> : std::integral_constant { };

//  all_rotations
    template  struct rotate;

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

    template  class P, typename First, typename... Rest>
    struct rotate> : rotate> { };

    template  struct all_rotations_h;

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

    template 
    struct all_rotations : all_rotations_h::value>> { };
}

// nCr
template  struct nCr;

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

template  class P, typename First, typename... Rest>
struct nCr, std::enable_if_t 1)>> : utilities::merge>::type>::type,
    typename nCr>::type
> { };

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

// all_permutations
template  struct all_permutations_h;

template  struct all_permutations_h_on_each;

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

template  struct
all_permutations : all_permutations_h_on_each::type> { };

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

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

// We now combine nCr with all_permutations to get nPr.
template  struct all_permutations_on_each_pack;

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

template 
struct nPr : all_permutations_on_each_pack::type> { };

// Testing
template  struct P;

int main() {
    static_assert(std::is_same>::type,  
        P, P, P, P, P, P>
    >::value);

    static_assert(std::is_same>::type,
        P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P, P>
    >::value);
}

Code Snippets

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

#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...>> :

Context

StackExchange Code Review Q#80373, answer score: 4

Revisions (0)

No revisions yet.