Permutation P(N,R) of types in compile time

Question

I've written a working code for computing P(N,R) for packs when the pack has all different types, e.g.

    PermutationN<2, P<int, char, bool>>

is to be

    P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> >

But when there are repeat elements, I'm getting the wrong results. For example,

PermutationN<2, P<int, int, char>>

should be

P< P<int, int>, P<int, char>, P<char, int> >

Here is my working code for when all the types are different. I'm stuck on how to adapt it so that it gives correct results when there are repeated types in the pack. Any help would be appreciated.

#include <iostream>
#include <type_traits>

template <typename, typename> 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 N, typename Pack, typename Previous, typename... Output> struct PermutationNHelper;

template <std::size_t N, template <typename...> class P, typename First, typename... Rest, typename... Prev, typename... Output>
struct PermutationNHelper<N, P<First, Rest...>, P<Prev...>, Output...> : Merge<
    // P<Prev..., Rest...> are the remaining elements, thus ensuring that the next
    // element chosen will not be First. The new Prev... is empty since we now start
    // at the first element of P<Prev..., Rest...>.
    typename PermutationNHelper<N-1, P<Prev..., Rest...>, P<>, Output..., First>::type,
    // Using P<Rest...> ensures that the next set of permutations will begin with the
    // type after First, and thus the new Prev... is Prev..., First.
    typename PermutationNHelper<N, P<Rest...>, P<Prev..., First>, Output...>::type
> {};

template <std::size_t N, template <typename...> class P, typename Previous, typename... Output>
struct PermutationNHelper<N, P<>, Previous, Output...> {
    using type = P<>;
};

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

template <template <typename...> class P, typename Previous, typename... Output>
struct PermutationNHelper<0, P<>, Previous, Output...> {
    using type = P<P<Output...>>;
};

template <typename Pack> struct EmptyPack;

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

template <std::size_t N, typename Pack>
using PermutationN = typename PermutationNHelper<N, Pack, typename EmptyPack<Pack>::type>::type;

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

int main() {
    std::cout << std::is_same<
        PermutationN<2, P<int, char, bool>>,
        P< P<int, char>, P<int, bool>, P<char, int>, P<char, bool>, P<bool, int>, P<bool, char> >
    >::value << '\n';  // true

    std::cout << std::is_same<
        PermutationN<2, P<int, int, int>>,
        P< P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int>, P<int, int> >
    >::value << '\n';  // true (but the answer should be P< P<int, int> >.
}

N.B. I'm looking for an elegant (and efficient) solution that does not simply carry out the above and then merely remove all repeat packs from the output (I can already do that but refuse to write up such an ugly, inefficient solution that does not tackle the heart of the problem), but rather get the correct output directly. That's where I'm stuck.

T.C. · Accepted Answer · 2016-04-07T17:47:45.263

The basic idea is to process the initial list of types into a list of (type, count) pairs, and work from there. First, some primitives:

template<class, size_t> struct counted_type {};
template<class...> struct pack {};

Our representation is going to be a pack of counted_types. To build it, we need to be able to add a type to it:

template<class T, class CT> struct do_push;
template<class T, class...Ts, size_t... Is>
struct do_push<T, pack<counted_type<Ts, Is>...>>{
   using type = std::conditional_t<std::disjunction_v<std::is_same<Ts, T>...>,
        pack<counted_type<Ts, Is + (std::is_same_v<Ts, T>? 1 : 0)>...>,
        pack<counted_type<Ts, Is>..., counted_type<T, 1>>
        >;
};
template<class T, class CT> using push = typename do_push<T, CT>::type;

If the type is already there, we add 1 to the count; otherwise we append a counted_type<T, 1>.

And to use it later, we'll need to be able to remove a type from it:

template<class T, class CT> struct do_pop;
template<class T, class...Ts, std::size_t... Is>
struct do_pop<T, pack<counted_type<Ts, Is>...>>{
   using type = remove<counted_type<T, 0>,
                       pack<counted_type<Ts, Is - (std::is_same_v<Ts, T>? 1 : 0)>...>>;
};

template<class T, class CT> using pop = typename do_pop<T, CT>::type;

remove<T, pack<Ts...>> removes the first instance of T from Ts..., if it exists, and returns the resulting pack (if T doesn't exist, the pack is returned unchanged). The (rather boring) implementation is left as an exercise to the reader.

With push we can easily build a pack of counted_types from a pack of types:

template<class P, class CT = pack<> >
struct count_types_imp { using type = CT; };

template<class CT, class T, class... Ts>
struct count_types_imp<pack<T, Ts...>, CT>
        : count_types_imp<pack<Ts...>, push<T, CT>> {};

template<class P>
using count_types = typename count_types_imp<P>::type;

Now, the actual implementation is

template<class T> struct identity { using type = T; };

template <std::size_t N, typename CT, typename = pack<> > struct PermutationNHelper;

// Workaround for GCC's partial ordering failure
template <std::size_t N, class CT, class> struct PermutationNHelper1;

template <std::size_t N, class... Types, std::size_t... Counts, class... Current >
struct PermutationNHelper1<N, pack<counted_type<Types, Counts>...>, pack<Current...>> {
    // The next item can be anything in Types...
    // We append it to Current... and pop it from the list of types, then
    // recursively generate the remaining items
    // Do this for every type in Types..., and concatenate the result.
    using type = concat<
        typename PermutationNHelper<N-1, pop<Types, pack<counted_type<Types, Counts>...>>,
                                    pack<Current..., Types>>::type...
        >;
};


template <std::size_t N, class... Types, std::size_t... Counts, class... Current >
struct PermutationNHelper<N, pack<counted_type<Types, Counts>...>, pack<Current...>> {
    using type = typename std::conditional_t<
                     N == 0,
                     identity<pack<pack<Current...>>>,
                     PermutationNHelper1<N, pack<counted_type<Types, Counts>...>, 
                                            pack<Current...>>
                  >::type; 
     // Note that we don't attempt to evaluate PermutationNHelper1<...>::type 
     // until we are sure that N > 0
};


template <std::size_t N, typename Pack>
using PermutationN = typename PermutationNHelper<N, count_types<Pack>>::type;

Normally this can be done in one template with two partial specializations (one for N > 0 and one for N == 0), but GCC's partial ordering is buggy, so I dispatched explicitly with conditional. Actually evaluating the pack expansion in PermutationNHelper1 with N equal to 0 will explode horribly, so the unimaginatively named PermutationNHelper1 is introduced to provide an extra level of indirection and prevent the explosion.

concat is just a variadic version of your Merge (well, typename Merge<...>::type). The implementation is left as an exercise to the reader.

@ T.C. Thanks for this most beautiful solution I've ever seen. I've verified that it works correctly. And GCC 5.3 does allow it to compile with just one template with two partial specializations as long as we use `std::enable_if` to separate the N > 0 and N == 0 cases. Here is the entire working code: http://ideone.com/hqL11N — prestokeys, Apr 07 '16 at 23:48

Permutation P(N,R) of types in compile time

1 Answers1

Linked