LeastPerm

template<size_t N>
using libsemigroups::LeastPerm = typename detail::LeastPermHelper<N>::type

Defined in transf.hpp.

! ! Dynamic partial transformations. ! ! This is a class for partial transformations where the number of points ! acted on (the degree) can be set at run time. ! !

public: ! Type of the image values. ! ! Also the template parameter

Scalar. using value_type = Scalar;

! Type of the underlying container. ! ! In this case, this is std::vector<value_type>. using container_type = std::vector<value_type>;

TODO(later) This is currently undocumentable. The doc is available in PTransfBase but they aren’t present in the doxygen xml output. using detail::PTransfBase<value_type, container_type>::PTransfBase;

! container_type>begin

container_type>begin using base_type::begin;

! Returns the degree of a transformation. ! ! The degree

of a transformation is the number of points used ! in its definition, which is equal to the size of the underlying ! container. ! !

! container_type>

end
Parameters

! (None) using base_type::degree;

container_type>end using base_type::end;

! Construct with given degree. ! ! Constructs a partial transformation of degree n with the image of ! every point set to UNDEFINED

. ! !

! Increase the degree in-place. ! ! Increases the degree of

this

in-place, leaving existing values ! unaltered. ! !

protected: using base_type::resize; };

////////////////////////////////////////////////////////////////////// StaticPTransf //////////////////////////////////////////////////////////////////////

! Defined in transf.hpp

. ! ! Static partial transformations. ! ! This is a class for partial transformations where the number of points ! acted on (the degree) is set at compile time. ! !

public: ! Type of the image values.

Also the template parameter Scalar. using value_type = Scalar;

! Type of the underlying container. ! ! In this case, this is std::array<value_type, N>. using container_type = std::array<Scalar, N>;

TODO(later) This is currently undocumentable. The doc is available in PTransfBase but they aren’t present in the doxygen xml output. using detail::PTransfBase<value_type, container_type>::PTransfBase;

! container_type>begin

container_type>begin using base_type::begin;

! container_type>end

container_type>end using base_type::end;

! Default constructor. ! ! Constructs a partial transformation of degree equal to the template ! parameter N with the image of every point set to UNDEFINED. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in the template parameter N. explicit StaticPTransf(size_t = 0) : base_type() { std::fill(begin(), end(), UNDEFINED); }

! Returns the degree of a partial transformation.

The degree of a partial transformation is the number of points used in its definition, which is equal to the size of the underlying container.

! Increase the degree in-place. ! ! This doesn’t make sense for this type, and it throws every time. ! !

////////////////////////////////////////////////////////////////////// PTransf //////////////////////////////////////////////////////////////////////

Parameters

(None) constexpr size_t degree() const noexcept { return N; }

! Defined in transf.hpp. ! ! This alias equals either DynamicPTransf or StaticPTransf depending on the ! template parameters N and Scalar. ! ! If N is 0 (the default), then PTransf is ! DynamicPTransf. In this case the default value of Scalar is ! uint32_t. If N is not 0, then PTransf is StaticPTransf, ! and the default value of Scalar is the smallest integer type able to ! hold N. See also SmallestInteger

. ! !

namespace detail { template <typename T> struct IsPTransfHelper : std::false_type {};

template <typename Scalar> struct IsPTransfHelper<DynamicPTransf<Scalar>> : std::true_type {};

template <size_t N, typename Scalar> struct IsPTransfHelper<StaticPTransf<N, Scalar>> : std::true_type {};

template <size_t N, typename Scalar> struct IsStaticHelper<StaticPTransf<N, Scalar>> : std::true_type {};

template <typename Scalar> struct IsDynamicHelper<DynamicPTransf<Scalar>> : std::true_type {}; } // namespace detail

! Helper variable template. ! ! The value of this variable is true if the template parameter T

is ! either DynamicPTransf or StaticPTransf for any template ! parameters. ! !

! Check that a partial transformation is valid. ! !

////////////////////////////////////////////////////////////////////// Transf //////////////////////////////////////////////////////////////////////

! Defined in transf.hpp. ! ! A transformation \(f\) is just a function defined on the ! whole of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) ! called the degree of \(f\). A transformation is stored as a ! vector of the images of \(\{0, 1, \ldots, n - 1\}\), i.e. ! \(\{(0)f, (1)f, \ldots, (n - 1)f\}\). ! ! If N is 0 (the default), then the degree of a Transf instance ! can be defined at runtime, and if N is not 0, then the degree is ! fixed at compile time. ! ! If N is 0, then the default value of Scalar is uint32_t. If ! N is not 0, then the default value of Scalar is the smallest ! integer type able to hold N. See also SmallestInteger

. ! !

public: ! Type of the image values. ! ! Also the template parameter

Scalar. using value_type = Scalar;

! Type of the underlying container. ! ! In this case, this is PTransf<N, Scalar>::container_type. using container_type = typename base_type::container_type;

using PTransf<N, Scalar>::PTransf;

! tESTING using base_type::degree;

! Construct from a container and validate. ! ! Constructs an transformation initialized using the ! container cont as follows: the image of the point i under ! the transformation is the value in position i of the container !

cont. ! !

! Construct from a container and validate. ! !

! Multiply two transformations and store the product in this. ! ! Replaces the contents of this by the product of x and y

. ! !

! Returns the identity transformation on degree() points. ! ! This function returns a newly constructed transformation with ! degree equal to the degree of

this that fixes every value from 0

! to degree(). ! !

! Returns the identity transformation on the given number of points. ! ! This function returns a newly constructed transformation with ! degree equal to

M that fixes every value from 0 to M

. ! !

namespace detail { template <typename T> struct IsTransfHelper : std::false_type {};

See also

make static Transf make(std::initializer_list<value_type>&& cont) { return make<std::initializer_list<value_type>>(std::move(cont)); }

Parameters

! (None) Transf identity() const { return identity(degree()); }

template <size_t N, typename Scalar> struct IsTransfHelper<Transf<N, Scalar>> : std::true_type {};

template <size_t N, typename Scalar> struct IsStaticHelper<Transf<N, Scalar>> : IsStaticHelper<PTransf<N, Scalar>> {};

template <size_t N, typename Scalar> struct IsDynamicHelper<Transf<N, Scalar>> : IsDynamicHelper<PTransf<N, Scalar>> {}; } // namespace detail

////////////////////////////////////////////////////////////////////// Transf helpers //////////////////////////////////////////////////////////////////////

! Helper variable template. ! ! The value of this variable is true if the template parameter T

is ! Transf for any template parameters. ! !

////////////////////////////////////////////////////////////////////// Transf validate //////////////////////////////////////////////////////////////////////

! Validate a transformation. ! !

////////////////////////////////////////////////////////////////////// PPerm //////////////////////////////////////////////////////////////////////

! Defined in transf.hpp. ! ! A partial permutation \(f\) is just an injective partial ! transformation, which is stored as a vector of the images of \(\{0, 1, //! \ldots, n - 1\}\), i.e. i.e. \(\{(0)f, (1)f, \ldots, (n - 1)f\}\) ! where the value UNDEFINED is used to indicate that \((i)f\) is ! undefined (i.e. not among the points where \(f\) is defined). ! ! If N is 0 (the default), then the degree of a PPerm instance ! can be defined at runtime, and if N is not 0, then the degree is ! fixed at compile time. ! ! If N is 0, then the default value of Scalar is uint32_t. If ! N is not 0, then the default value of Scalar is the smallest ! integer type able to hold N. See also SmallestInteger

. ! !

public: ! Type of the image values. ! ! Also the template parameter

Scalar. using value_type = Scalar;

! Type of the underlying container. ! ! In this case, this is PTransf<N, Scalar>::container_type. using container_type = typename base_type::container_type;

Currently no way to document these using PTransf<N, value_type>::PTransf;

Currently no way to document these using base_type::degree; using base_type::undef;

! Construct from image list and validate ! ! Constructs a partial perm \(f\) of degree M such that \(f(i) = //! cont[i]\) for every value in the range \([0, M)\) where \(M\) is ! cont.size()

! !

! Construct from image list and validate ! ! Constructs a partial perm

\(f\) of degree M such that \(f(i) = //! cont[i]\) for every value in the range \([0, M)\) where \(M\) is ! cont.size()

! !

! Construct from domain, range, and degree, and validate ! ! Constructs a partial perm of degree

M such that (dom[i])f = ran[i] ! for all i and which is UNDEFINED on every other value in the ! range \([0, M)\)

. ! !

! Construct from domain, range, and degree. ! ! Constructs a partial perm of degree

M such that (dom[i])f = ran[i] ! for all i and which is UNDEFINED on every other value in the ! range \([0, M)\)

. ! !

! Construct from domain, range, and degree. ! ! Constructs a partial perm of degree

M such that (dom[i])f = ran[i] ! for all i and which is UNDEFINED on every other value in the ! range \([0, M)\)

. ! !

! Multiply two partial perms and store the product in

this. ! ! Replaces the contents of this by the product of x and y

. ! !

! Returns the identity partial perm on degree() points. ! ! This function returns a newly constructed partial perm with degree ! equal to the degree of

this that fixes every value from 0

to ! degree(). ! !

! Returns the identity partial perm on the given number of points. ! ! This function returns a newly constructed partial perm with ! degree equal to

M that fixes every value from 0 to M

. ! !

! Returns the right one of this. ! ! This function returns a newly constructed partial perm with ! degree equal to

M that fixes every value in the range of this, ! and is UNDEFINED

on any other values. ! !

! Returns the left one of this. ! ! This function returns a newly constructed partial perm with ! degree equal to

M that fixes every value in the domain of this, ! and is UNDEFINED

on any other values. ! !

! Returns the inverse. ! ! This function returns a newly constructed inverse of

this

. ! !

! Replace contents of a partial perm with the inverse of another. ! ! This function inverts

that into this

. ! !

private: static void validate_args(std::vector<value_type> const& dom, std::vector<value_type> const& ran, size_t deg = N) { if (N != 0 && deg != N) { Sanity check that the final argument is compatible with the template param N, if we have a dynamic pperm LIBSEMIGROUPS_EXCEPTION( “the 3rd argument is not valid, expected %llu, found %llu”, uint64_t(N), uint64_t(deg)); } else if (dom.size() != ran.size()) { The next 2 checks just verify that we can safely run the constructor that uses *this[dom[i]] = im[i] for i = 0, …, dom.size() - 1. LIBSEMIGROUPS_EXCEPTION(“domain and range size mismatch, domain has “ “size %llu but range has size %llu”, uint64_t(dom.size()), uint64_t(ran.size())); } else if (!(dom.empty() || deg > *stdmax_element(dom.cbegin(), dom.cend()))) { LIBSEMIGROUPS_EXCEPTION( “domain value out of bounds, found %llu, must be less than %llu”, uint64_t(*stdmax_element(dom.cbegin(), dom.cend())), uint64_t(deg)); } } };

See also

! make. Note: we use vectors here not container_type (which might be array), because the length of dom and ran might not equal degree(). PPerm(std::vector<value_type> const& dom, std::vector<value_type> const& ran, size_t M = N) : PPerm(M) { LIBSEMIGROUPS_ASSERT(M >= N); LIBSEMIGROUPS_ASSERT(dom.size() <= M); LIBSEMIGROUPS_ASSERT(ran.size() <= M); LIBSEMIGROUPS_ASSERT(ran.size() <= dom.size()); for (size_t i = 0; i < dom.size(); ++i) { (*this)[dom[i]] = ran[i]; } }

See also

! make

. PPerm(std::initializer_list<value_type> dom,

std::initializer_list<value_type> ran,

size_t M) : PPerm(std::vector<value_type>(dom), std::vector<value_type>(ran), M) { }

Parameters

! (None) PPerm identity() const { return identity(degree()); }

Parameters

! (None) ! ! \complexity ! Linear in degree() PPerm right_one() const { size_t const n = degree(); PPerm result(n); std::fill( result.begin(), result.end(), static_cast<value_type>(UNDEFINED)); for (size_t i = 0; i < n; ++i) { if ((*this)[i] != UNDEFINED) { result[(*this)[i]] = (*this)[i]; } } return result; }

Parameters

! (None) ! ! \complexity ! Linear in degree() PPerm left_one() const { size_t const n = degree(); PPerm result(n); std::fill( result.begin(), result.end(), static_cast<value_type>(UNDEFINED)); for (size_t i = 0; i < n; ++i) { if ((*this)[i] != UNDEFINED) { result[i] = i; } } return result; }

Parameters

! (None) ! ! \complexity ! Linear in degree() PPerm inverse() const { PPerm result(degree()); inverse(result); return result; }

////////////////////////////////////////////////////////////////////// PPerm helpers //////////////////////////////////////////////////////////////////////

namespace detail { template <typename T> struct IsPPermHelper : std::false_type {};

template <size_t N, typename Scalar> struct IsPPermHelper<PPerm<N, Scalar>> : std::true_type {};

template <size_t N, typename Scalar> struct IsStaticHelper<PPerm<N, Scalar>> : IsStaticHelper<PTransf<N, Scalar>> {};

template <size_t N, typename Scalar> struct IsDynamicHelper<PPerm<N, Scalar>> : IsDynamicHelper<PTransf<N, Scalar>> {};

} // namespace detail

! Helper variable template. ! ! The value of this variable is true if the template parameter T

is ! PPerm for any template parameters. ! !

////////////////////////////////////////////////////////////////////// PPerm validate //////////////////////////////////////////////////////////////////////

namespace detail { template <typename T> void validate_no_duplicate_image_values(T const& x) { size_t const deg = x.degree(); std::vector<int> present(deg, false); for (auto it = x.cbegin(); it != x.cend(); ++it) { if (*it != UNDEFINED) { if (present[*it]) { LIBSEMIGROUPS_EXCEPTION( “duplicate image value, found %llu in position %llu, first “ “occurrence in position %llu”, uint64_t(*it), std::distance(x.begin(), it), std::distance(x.begin(), std::find(x.begin(), it, *it))); } present[*it] = 1; } } } } // namespace detail

! Validate a partial perm. ! !

////////////////////////////////////////////////////////////////////// Perm //////////////////////////////////////////////////////////////////////

! Defined in transf.hpp. ! ! A permutation \(f\) is an injective transformation defined on the ! whole of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) called ! the degree of \(f\). A permutation is stored as a vector of the ! images of \((0, 1, \ldots, n - 1)\), i.e. \(((0)f, (1)f, \ldots, (n - //! 1)f)\). ! ! If N is 0 (the default), then the degree of a PPerm instance ! can be defined at runtime, and if N is not 0, then the degree is ! fixed at compile time. ! ! If N is 0, then the default value of Scalar is uint32_t. If ! N is not 0, then the default value of Scalar is the smallest ! integer type able to hold N. See also SmallestInteger

. ! !

public: ! Type of the image values. ! ! Also the template parameter

Scalar. using value_type = Scalar;

! Type of the underlying container. ! ! In this case, this is PTransf<N, Scalar>::container_type. using container_type = typename PTransf<N, value_type>::container_type;

Currently no way to document these using Transf<N, Scalar>::Transf;

Currently no way to document these using base_type::degree;

! Construct from image list and validate ! ! Constructs a permutation \(f\) of degree M such that \(f(i) = //! cont[i]\) for every value in the range \([0, M)\) where \(M\) is ! cont.size()

! !

! Returns the identity permutation on degree() points. ! ! This function returns a newly constructed permutation with degree ! equal to the degree of

this that fixes every value from 0

to ! degree(). ! !

! Returns the identity permutation on the given number of points. ! ! This function returns a newly constructed permutation with ! degree equal to

M that fixes every value from 0 to M

. ! !

! Returns the inverse. ! ! This function returns a newly constructed inverse of

this. ! The inverse of a permutation \(f\) is the permutation \(g\) such ! that \(fg = gf\) is the identity permutation of degree \(n\)

. ! !

////////////////////////////////////////////////////////////////////// Perm helpers //////////////////////////////////////////////////////////////////////

Parameters

! (None) Perm identity() const { return identity(degree()); }

Parameters

! (None) ! ! \complexity ! Linear in degree() Perm inverse() const { size_t const n = degree(); Perm id(n); for (Scalar i = 0; i < n; i++) { id[(*this)[i]] = i; } return id; } TODO(later) inverse(that) };

namespace detail { template <typename T> struct IsPermHelper : std::false_type {};

template <size_t N, typename Scalar> struct IsPermHelper<Perm<N, Scalar>> : std::true_type {}; } // namespace detail

! Helper variable template. ! ! The value of this variable is true if the template parameter T

is ! Perm for any template parameters. ! !

////////////////////////////////////////////////////////////////////// Perm validate //////////////////////////////////////////////////////////////////////

! Validate a permutation. ! !

////////////////////////////////////////////////////////////////////// Adapters //////////////////////////////////////////////////////////////////////

template <typename T> struct Degree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> { constexpr size_t operator()(T const& x) const noexcept { return x.degree(); } };

template <typename T> struct One<T, std::enable_if_t<IsDerivedFromPTransf<T>>> { T operator()(T const& x) const { return (*this)(x.degree()); }

T operator()(size_t N = 0) const { return T::identity(N); } };

template <size_t N, typename Scalar> struct Inverse<Perm<N, Scalar>> { Perm<N, Scalar> operator()(Perm<N, Scalar> const& x) { return x.inverse(); } };

template <typename TSubclass> struct Product<TSubclass, std::enable_if_t<IsDerivedFromPTransf<TSubclass>>> { void operator()(TSubclass& xy, TSubclass const& x, TSubclass const& y, size_t = 0) { xy.product_inplace(x, y); } };

template <typename T> struct Hash<T, std::enable_if_t<IsDerivedFromPTransf<T>>> { constexpr size_t operator()(T const& x) const { return x.hash_value(); } };

template <typename T> struct Complexity<T, std::enable_if_t<IsDerivedFromPTransf<T>>> { constexpr size_t operator()(T const& x) const noexcept { return x.degree(); } };

! Specialization of the adapter IncreaseDegree for type derived from ! PTransfPolymorphicBase

. ! !

////////////////////////////////////////////////////////////////////// ImageRight/LeftAction - Transf //////////////////////////////////////////////////////////////////////

See also

IncreaseDegree. template <typename T> struct IncreaseDegree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> { ! Returns x->increase_degree_by(n). inline void operator()(T& x, size_t n) const { return x.increase_degree_by(n); } };

Equivalent to OnSets in GAP Slowest works for T = std::vector and T = StaticVector1 ! Specialization of the adapter ImageRightAction for instances of ! Transformation and std::vector. ! !

Fastest, but limited to at most degree 64 ! Specialization of the adapter ImageRightAction for instances of ! Transformation and BitSet<N> (

\(0 \leq N leq 64\)

). ! !

OnKernelAntiAction T = StaticVector1

See also

ImageRightAction template <size_t N, typename Scalar, typename T> struct ImageRightAction<Transf<N, Scalar>, T> { ! Stores the image set of pt under x in res. void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const { res.clear(); for (auto i : pt) { res.push_back(x[i]); } std::sort(res.begin(), res.end()); res.erase(std::unique(res.begin(), res.end()), res.end()); } };

See also

ImageRightAction template <size_t N, typename Scalar, size_t M> struct ImageRightAction<Transf<N, Scalar>, BitSet<M>> { ! Stores the image set of pt under x in res

. void operator()(BitSet<M>& res,

BitSet<M> const& pt,

Transf<N, Scalar> const& x) const { res.reset(); Apply the lambda to every set bit in pt pt.apply([&x, &res](size_t i) { res.set(x[i]); }); } };

Note

! Transf has the same member functions as ! StaticPTransf and DynamicPTransf, this isn’t currently ! reflected by the contents of this page. template < size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>> class Transf : public PTransf<N, Scalar> { using base_type = PTransf<N, Scalar>;

Warning

! No checks are made on whether or not the parameters are compatible. If ! x and y have different degrees, then bad things will happen. void product_inplace(Transf const& x, Transf const& y) { LIBSEMIGROUPS_ASSERT(x.degree() == y.degree()); LIBSEMIGROUPS_ASSERT(x.degree() == this->degree()); LIBSEMIGROUPS_ASSERT(&x != this && &y != this); size_t const n = this->degree(); for (value_type i = 0; i < n; ++i) { (*this)[i] = y[x[i]]; } }

Note

! PPerm has the same member functions as StaticPTransf and ! DynamicPTransf, this isn’t current reflected by the contents of this ! page. template < size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>> class PPerm final : public PTransf<N, Scalar> { using base_type = PTransf<N, Scalar>;

Warning

! No checks whatsoever are performed on the validity of the arguments. ! !

Warning

! No checks whatsoever are performed on the validity of the arguments. ! !

Warning

! No checks are made on whether or not the parameters are compatible. If ! x and y have different degrees, then bad things will happen. void product_inplace(PPerm const& x, PPerm const& y) { LIBSEMIGROUPS_ASSERT(x.degree() == y.degree()); LIBSEMIGROUPS_ASSERT(x.degree() == degree()); LIBSEMIGROUPS_ASSERT(&x != this && &y != this); size_t const n = degree(); for (value_type i = 0; i < n; ++i) { (*this)[i] = (x[i] == UNDEFINED ? UNDEFINED : y[x[i]]); } }

Note

! Perm has the same member functions as StaticPTransf and ! DynamicPTransf, this isn’t current reflected by the contents of this ! page. template < size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>> class Perm final : public Transf<N, Scalar> { using base_type = PTransf<N, Scalar>;

Template Parameters:
  • Scalar – a unsigned integer type. template <typename Scalar> class DynamicPTransf : public detail::PTransfBase<Scalar, std::vector<Scalar>> { using base_type = detail::PTransfBase<Scalar, std::vector<Scalar>>;

  • Scalar – an unsigned integer type. template <size_t N, typename Scalar> class StaticPTransf : public detail::PTransfBase<Scalar, std::array<Scalar, N>> { using base_type = detail::PTransfBase<Scalar, std::array<Scalar, N>>;

  • N – the degree (default: 0) !

  • Scalar – an unsigned integer type (the type of the image values) template < size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>> using PTransf = std:: conditional_t<N == 0, DynamicPTransf<Scalar>, StaticPTransf<N, Scalar>>;

  • T – a type. TODO(later) add doc link to IsStatic/IsDynamic (tried but it didn’t work on 15/03/2021) template <typename T> static constexpr bool IsPTransf = detail::IsPTransfHelper<T>::value;

  • N – the degree !

  • Scalar – an unsigned integer type (the type of the image values) ! !

  • N – the degree (default: 0) !

  • Scalar – an unsigned integer type (the type of the image values) ! !

  • T – the type of the container cont. ! !

  • T – a type. template <typename T> static constexpr bool IsTransf = detail::IsTransfHelper<T>::value;

  • T – the type of the transformation to validate. ! !

  • N – the degree (default: 0) !

  • Scalar – an unsigned integer type (the type of the image values) ! !

  • T – a type. template <typename T> static constexpr bool IsPPerm = detail::IsPPermHelper<T>::value;

  • T – the type of the partial perm to validate. ! !

  • N – the degree (default: 0) !

  • Scalar – an unsigned integer type (the type of the image values) ! !

  • T – a type. template <typename T> static constexpr bool IsPerm = detail::IsPermHelper<T>::value;

  • T – the type of the permutation to validate. ! !

Return:

! A value of type size_t. ! ! \exceptions ! \noexcept ! !

Param n:

the degree ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in the parameter n. explicit DynamicPTransf(size_t n) : base_type() { resize(n, UNDEFINED); }

Param m:

the number of points to add. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! At worst linear in the sum of the parameter m and degree(). void increase_degree_by(size_t m) { resize(degree() + m); std::iota(end() - m, end(), degree() - m); }

Throws (None):

This function is noexcept and is guaranteed never to throw.

Throws LibsemigroupsException:

every time. void increase_degree_by(size_t) { do nothing can’t increase the degree LIBSEMIGROUPS_EXCEPTION(“cannot increase the degree of a StaticPTransf!”); } };

Return:

A value of type size_t.

Param x:

a const reference to the partial transformation to validate. ! !

Throws LibsemigroupsException:

if any of the following hold: ! * the size of cont is incompatible with T::container_type. ! * any value in cont exceeds cont.size() and is not equal to ! libsemigroups::UNDEFINED. ! ! \complexity ! Linear in degree(). template <typename T> auto validate(T const& x) -> std::enable_if_t<IsPTransf<T>> { size_t const M = x.degree(); for (auto const& val : x) { the type of “val” is an unsigned int, and so we don’t check for val being less than 0 if (val >= M && val != UNDEFINED) { LIBSEMIGROUPS_EXCEPTION(“image value out of bounds, expected value in “ “[%llu, %llu), found %llu”, uint64_t(0), uint64_t(M), uint64_t(val)); } } }

Return:

! (None) ! !

Param cont:

the container. ! !

Throws LibsemigroupsException:

if any of the following hold: ! * the size of cont is incompatible with container_type. ! * any value in cont exceeds cont.size() or is equal to ! UNDEFINED. ! ! \complexity ! Linear in the size of the container cont. template <typename T> static Transf make(T&& cont) { return base_type::template make<Transf>(std::forward<T>(cont)); }

Param x:

a transformation. !

Param y:

a transformation. ! !

Param M:

the degree. ! !

Return:

! (None) ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in PTransf::degree. ! !

Return:

! A value of type Transf. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! A value of type Transf. ! ! \exceptions ! \no_libsemigroups_except ! ! \exceptions ! \no_libsemigroups_except static Transf identity(size_t M) { return base_type::template identity<Transf>(M); } };

Param x:

the transformation. ! !

Throws LibsemigroupsException:

if the image of any point exceeds ! x.degree() or is equal to UNDEFINED. ! ! \complexity ! Linear in the size of the container x.degree(). template <size_t N, typename Scalar> void validate(Transf<N, Scalar> const& x) { size_t const M = x.degree(); for (auto const& val : x) { if (val >= M) { LIBSEMIGROUPS_EXCEPTION(“image value out of bounds, expected value in “ “[%llu, %llu), found %llu”, uint64_t(0), uint64_t(M), uint64_t(val)); } } }

Param cont:

list of images or UNDEFINED ! ! \complexity ! Linear in the size of cont. ! !

Throws LibsemigroupsException:

if any of the following fail to hold: ! * the size of cont is incompatible with container_type. ! * any value in cont exceeds cont.size() and is not equal to ! UNDEFINED. ! * there are repeated values in cont. template <typename T> static PPerm make(T&& cont) { return base_type::template make<PPerm>(std::forward<T>(cont)); }

Param cont:

list of images or UNDEFINED ! ! \complexity ! Linear in the size of cont. ! !

Throws LibsemigroupsException:

if any of the following fail to hold: ! * the size of cont is incompatible with container_type. ! * any value in cont exceeds cont.size() and is not equal to ! UNDEFINED. ! * there are repeated values in cont. static PPerm make(std::initializer_list<value_type>&& cont) { return make<std::initializer_list<value_type>>(std::move(cont)); }

Param dom:

the domain !

Param ran:

the range !

Param M:

the degree ! ! \complexity ! Linear in the size of dom. ! !

Throws LibsemigroupsException:

if any of the following fail to hold: ! * the value M is not compatible with the template parameter N ! * dom and ran do not have the same size ! * any value in dom or ran is greater than M ! * there are repeated entries in dom or ran

. static PPerm make(std::vector<value_type> const& dom,

std::vector<value_type> const& ran,

size_t const M) { validate_args(dom, ran, M); PPerm result(dom, ran, M); validate(result); return result; }

Param dom:

the domain !

Param ran:

the range !

Param M:

the degree ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in the size of dom. ! !

Param dom:

the domain !

Param ran:

the range !

Param M:

the degree ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in the size of dom. ! !

Param x:

a partial perm. !

Param y:

a partial perm. ! !

Param M:

the degree. ! !

Param that:

the partial perm to invert. ! !

Return:

! (None) ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in degree(). ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in M. static PPerm identity(size_t M) { return base_type::template identity<PPerm>(M); }

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! (None) ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in degree() Put the inverse of this into that void inverse(PPerm& that) const { that.resize(degree()); std::fill(that.begin(), that.end(), static_cast<value_type>(UNDEFINED)); for (size_t i = 0; i < degree(); ++i) { if ((*this)[i] != UNDEFINED) { that[(*this)[i]] = i; } } }

Param x:

the partial perm. ! !

Throws LibsemigroupsException:

if: ! * the image of any point in x exceeds x.degree() and is not equal ! to UNDEFINED; or ! * x is not injective ! ! \complexity ! Linear in the size of the container x.degree(). template <size_t N, typename Scalar> void validate(PPerm<N, Scalar> const& x) { validate(static_cast<PTransf<N, Scalar> const&>(x)); detail::validate_no_duplicate_image_values(x); }

Param cont:

list of images ! ! \complexity ! Linear in the size of cont. ! !

Throws LibsemigroupsException:

if any of the following fail to hold: ! * the size of cont is incompatible with container_type. ! * any value in cont exceeds cont.size() ! * there are repeated values in cont. template <typename T> static Perm make(T&& cont) { return base_type::template make<Perm>(std::forward<T>(cont)); }

Param M:

the degree. ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Linear in M. static Perm identity(size_t M) { return base_type::template identity<Perm>(M); }

Return:

! A value of type PPerm. ! ! \exceptions ! \no_libsemigroups_except ! !

Param x:

the permutation. ! !

Throws LibsemigroupsException:

if: ! * the image of any point in x exceeds x.degree() ! * x is not injective ! ! \complexity ! Linear in the size of the container x.degree(). template <size_t N, typename Scalar> auto validate(Perm<N, Scalar> const& x) { validate(static_cast<Transf<N, Scalar> const&>(x)); detail::validate_no_duplicate_image_values(x); }