# Handle permutations with duplicates at compile time

I created a simple library which handles permutation sequences with duplicates at compile time in C++14.

## Oberview

I published an open source library called 'komoperm’, which handles permutation sequences with repetition.

It can calculate an index of a sequence of integers or enumerations, or generate a sequence which corresponds to the given index.

#include "komoperm/komoperm.hpp" enum Hoge { A, B, C, }; int main() { constexpr komoperm::Permutations<Hoge, A, A, A, B, B, C> p; static_assert(p.Size() == 60, "The number os possible permutations is 60"); static_assert(p.Index({B, A, B, C, A, A}) < 60, "{B, A, B, C, A, A} is a permutation of {A, A, A, B, B, C}"); static_assert(p.Index(p.Get(10)) == 10, "Get() generates the 10th permutation"); }

A set of permutation sequences `komoperm::Permutations`

have two template parameters: typename `T`

and sequence values `Vals...`

. The values `Vals...`

don’t have to be sorted. Moreover, same values don’t need to be located consecutive position.

All komoperm’s calculations are done at compile time, and they works fast even at runtime thanks to template calculation. The memory consumption at compile time is relatively small because they don’t use template recursions.

Only C++14 features are used in komoperm.^{1} In the following section, I would like to show briefly how to realize these features.

## Implementation

The most difficult point in komoperm is not generation of sequences but creation of a helpful type `PermutationImpl`

.

Input: Permutations<T, Vals...> Output: PermutationsImpl< T, N, // sizeof...(Vals) M, // The number of the most frequent value in Vals... ItemCount< Val, // A value N2, // How many remaining symbols are to be placed C // How many `Val` is to be placed >, ItemCount< // ... > ... >

A type `PermutationImpl`

contains each `Val`

and its counts `C`

as template parameters. By using this type, we can easily realize permutation operations. In the above code example, values except for `Val`

, `N2`

, and `C`

are easily obtained by `Vals...`

. Therefore, we focus on how we could make a type which has `<Val, N2, C>...`

in template parameters.

In komoperm, it is realized as follows.

- Get unique values in
`Vals...`

- Sort
`Vals...`

- Count the number of
`Val`

for each`Val`

- Expand result of 3.

Note that komoperm doesn’t use template recursion at all, so it doesn’t need huge memory at compile time.

1., 2., and 3. are not so difficult. Without recursion, they are easily realized like this code and this code.

The most tough part is No.4. From 1-3, we have the following three arrays.

- A array which contains unique
`Val`

s - The number of
`Val`

s in i, i+1,i+2,… - The number of
`Vals`

For example, consider a sequence `A, A, A, B, B, C`

. The above sequences are as follows.

`{A, B, C}`

`{6, 3, 1}`

`{3, 2, 1}`

Now, we would like to create a new type whose template parameters are “vertically" ordered like `<A, 6, 3>, <B, 3, 2>, <C, 1, 1>`

. One may think that is difficult, but we can realize it by index substitutions and by template parameter pack expansions.

template <typename T, T... Vals, std::size_t... Indices> struct MakePermutationsImpl<ValueSet<T, Vals...>, std::index_sequence<Indices...>> { private: static constexpr auto Impl() noexcept { constexpr auto kValue = MakeItemCountsImplCalc<T, Vals...>(); using type = PermutationsImpl< T, sizeof...(Vals), std::max({kValue.counts[Indices]...}), ItemCount<T, kValue.values[Indices], kValue.remains[Indices], kValue.counts[Indices]>...>; return type{}; } public: using type = decltype(Impl()); };

The point is line 1, and 9-10. By using an index parameter pack `Indices...`

, the parameter pack expansion `ItemCount<values[Indices], remain[Indices], counts[Indices]>...`

generates the desired type sequence. By using these index techniques, we could realize the type conversion without recursion.

## Conclusion

In this article, I showed basic techniques for permutation sequence with repetition. I’ll be happy if you found the difficulty of c++ templates.