Permutation Monoid
(monoid/permutation.hpp)

• View this file on GitHub
• Last update: 2026-07-21 20:17:47+09:00
• Include: #include "monoid/permutation.hpp"

Overview

A monoid for representing and composing fixed-size permutations. The underlying value_type is std::array<int, N>.

When two permutations $A$ and $B$ are merged (i.e., op(A, B)), it corresponds to applying permutation $A$ first, followed by permutation $B$. That is, the resulting permutation $C$ satisfies $C[i] = B[A[i]]$.

Example

#include "ds/segtree/segtree.hpp"
#include "monoid/permutation.hpp"
#include <iostream>
#include <vector>

using Perm3 = m1une::monoid::Permutation<3>;

int main() {
    std::vector<Perm3::value_type> init_data = {
        {1, 2, 0}, // Swaps elements cyclically
        {0, 2, 1}  // Swaps index 1 and 2
    };

    m1une::ds::Segtree<Perm3> seg(init_data);

    // Get the composed permutation for the range [0, 2)
    auto res = seg.prod(0, 2);

    std::cout << "0 maps to: " << res[0] << "\n";
    std::cout << "1 maps to: " << res[1] << "\n";
    std::cout << "2 maps to: " << res[2] << "\n";

    return 0;
}

Interface and Complexity

This is a stateless algebra tag. Generic data structures use its public value_type, id(), and op(a, b) members. If the type also provides helpers such as make(...) or inv(x), they are described above or in the documented properties.

Each static operation runs in the cost of the underlying operation shown in the properties. Scalar monoids are $O(1)$; monoids whose value_type stores several items, permutations, or matrices scale with that stored size.

Verified with

• verify/monoid/commutative_flags.test.cpp

Code

#ifndef M1UNE_MONOID_PERMUTATION_HPP
#define M1UNE_MONOID_PERMUTATION_HPP 1

#include <array>
#include <numeric>

namespace m1une {
namespace monoid {

// Monoid for Permutation Composition.
// Represents a permutation of fixed size N.
template <int N>
struct Permutation {
    using value_type = std::array<int, N>;
    static constexpr bool commutative = false;

    // The identity element is the identity permutation (0, 1, 2, ..., N-1).
    static constexpr value_type id() {
        value_type res{};
        std::iota(res.begin(), res.end(), 0);
        return res;
    }

    // Composes two permutations (applies 'a' then 'b').
    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            res[i] = b[a[i]];
        }
        return res;
    }
};

}  // namespace monoid
}  // namespace m1une

#endif  // M1UNE_MONOID_PERMUTATION_HPP

#line 1 "monoid/permutation.hpp"



#include <array>
#include <numeric>

namespace m1une {
namespace monoid {

// Monoid for Permutation Composition.
// Represents a permutation of fixed size N.
template <int N>
struct Permutation {
    using value_type = std::array<int, N>;
    static constexpr bool commutative = false;

    // The identity element is the identity permutation (0, 1, 2, ..., N-1).
    static constexpr value_type id() {
        value_type res{};
        std::iota(res.begin(), res.end(), 0);
        return res;
    }

    // Composes two permutations (applies 'a' then 'b').
    static constexpr value_type op(const value_type& a, const value_type& b) {
        value_type res{};
        for (int i = 0; i < N; ++i) {
            res[i] = b[a[i]];
        }
        return res;
    }
};

}  // namespace monoid
}  // namespace m1une

Back to top page