Handle permutations with duplicates at compile time

ProgrammingC/C++

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.

komori-n/komoperm - GitHub

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.

  1. Get unique values in Vals...
  2. Sort Vals...
  3. Count the number of Val for each Val
  4. 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 Vals
  • The number of Vals 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.

notes

  1. For user’s convenience, it switches implementations using C++17.

ProgrammingC/C++

Posted by komori