trjhtr

Often we need to find out if two tuples, or two packs in general, are the same as each other up to permutation. If there are no repeat types, then implementing is_permutation_no_repeats is quite straightforward. For example, simply remove each type in the first pack from the second pack and check if the second pack becomes empty or not. If the two packs have repeated types, then simply group those repeated types into num_types<T, Count>, where Count is the number of times T occurs in the pack. Then we've reduced the two packs into packs of num_types<T, Count>s types, and thus have no repeat types any more, and then is_permutation_no_repeats can be invoked. Here is my implementation and test:

#include <type_traits>
#include <utility>

namespace utilities 
 template <typename T, typename Pack, typename... Ts> struct remove_first_found;

 template <typename T, template <typename...> class P, typename... Ts>
 struct remove_first_found<T, P<>, Ts...> 
 using type = P<Ts...>; // T was never found. 
 ;

 template <typename T, template <typename...> class P, typename... Rest, typename... Ts>
 struct remove_first_found<T, P<T, Rest...>, Ts...> 
 using type = P<Ts..., Rest...>; // First T found and removed.
 ;

 template <typename T, template <typename...> class P, typename First, typename... Rest, typename... Ts>
 struct remove_first_found<T, P<First, Rest...>, Ts...> : remove_first_found<T, P<Rest...>, Ts..., First> ;


template <typename T, std::size_t Count> struct num_types;

template <typename T, typename Pack, std::size_t Count, typename... Ts> struct get_num_types;

template <typename T, template <typename...> class P, std::size_t Count, typename... Ts>
struct get_num_types<T, P<>, Count, Ts...> 
 using type = num_types<T, Count>;
 using remaining = P<Ts...>;
;

template <typename T, template <typename...> class P, typename First, typename... Rest, std::size_t Count, typename... Ts>
struct get_num_types<T, P<First, Rest...>, Count, Ts...> : get_num_types<T, P<Rest...>, Count, Ts..., First> ;

template <typename T, template <typename...> class P, typename... Rest, std::size_t Count, typename... Ts>
struct get_num_types<T, P<T, Rest...>, Count, Ts...> : get_num_types<T, P<Rest...>, Count + 1, Ts...> ;

template <typename Pack, typename... NumTypes> struct count_types;

template <template <typename...> class P, typename... NumTypes>
struct count_types<P<>, NumTypes...> 
 using type = P<NumTypes...>;
;

template <template <typename...> class P, typename First, typename... Rest, typename... NumTypes>
struct count_types<P<First, Rest...>, NumTypes...> 
 using meta = get_num_types<First, P<Rest...>, 1>;
 using type = typename count_types<typename meta::remaining, NumTypes..., typename meta::type>::type;
;

template <typename Pack1, typename Pack2>
struct is_permutation_no_repeats : std::false_type ;

template <template <typename...> class P, template <typename...> class Q>
struct is_permutation_no_repeats<P<>, Q<>> : std::true_type ;

template <template <typename...> class P, typename First, typename... Rest, typename Pack2>
struct is_permutation_no_repeats<P<First, Rest...>, Pack2> 
 using meta = typename utilities::remove_first_found<First, Pack2>::type;
 static constexpr bool value = std::is_same_v<meta, Pack2> ? false : is_permutation_no_repeats<P<Rest...>, meta>::value;
;

template <typename Pack1, typename Pack2>
struct is_permutation : is_permutation_no_repeats<typename count_types<Pack1>::type, typename count_types<Pack2>::type> ;

template <typename Pack1, typename Pack2>
constexpr bool is_permutation_v = is_permutation<Pack1, Pack2>::value;

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

int main() 
 static_assert(std::is_same_v<
 count_types<P<int, char, long, int, bool, char, bool, int, double, int, bool>>::type,
 P<num_types<int, 4>, num_types<char, 2>, num_types<long, 1>, num_types<bool, 3>, num_types<double, 1>>
 >);

 static_assert(is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
 Q<int, char, long, int, bool, char, bool, int, double, int, bool>>); // Identical contents in the two packs.
 static_assert(is_permutation_v<P<int, char, long, bool, double>,
 Q<double, bool, int, long, char>>); // Permutation with no repeats types.
 static_assert(is_permutation_no_repeats<P<int, char, long, bool, double>,
 Q<double, bool, int, long, char>>::value);
 static_assert(is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
 Q<bool, int, bool, int, char, int, int, bool, char, long, double>>); // Permutations with repeat types.
 static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
 Q<bool, int, float, int, char, int, int, bool, char, long, double>>); // Second pack has float when the first pack does not.
 static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
 Q<bool, int, bool, int, char, int, int, bool, char, long>>); // Second pack is one type less than the first pack.
 static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
 Q<bool, int, bool, int, char, int, int, bool, double, long, double>>); // Second pack 2 doubles instead of 1 and 1 char instead of 2.