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 parameterN
. 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 parametersN
andScalar
. ! ! IfN
is0
(the default), thenPTransf
is ! DynamicPTransf. In this case the default value ofScalar
is!
uint32_t. IfN
is not0
, thenPTransf
is StaticPTransf, ! and the default value ofScalar
is the smallest integer type able to ! holdN
. 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 parameterT
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\}\). ! ! IfN
is0
(the default), then the degree of a Transf instance ! can be defined at runtime, and ifN
is not0
, then the degree is ! fixed at compile time. ! ! IfN
is0
, then the default value ofScalar
isuint32_t
. If !N
is not0
, then the default value ofScalar
is the smallest ! integer type able to holdN
. 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 pointi
under ! the transformation is the value in positioni
of the container!
cont. ! !
! Construct from a container and validate. ! !
! Multiply two transformations and store the product inthis
. ! ! Replaces the contents ofthis
by the product ofx
andy
. ! !
! 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 from0
! 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 from0
toM
. ! !
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 parameterT
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). ! ! IfN
is0
(the default), then the degree of a PPerm instance ! can be defined at runtime, and ifN
is not0
, then the degree is ! fixed at compile time. ! ! IfN
is0
, then the default value ofScalar
isuint32_t
. If !N
is not0
, then the default value ofScalar
is the smallest ! integer type able to holdN
. 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 degreeM
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 alli
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 alli
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 alli
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 ofthis
by the product ofx
andy
. ! !
! 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 from0
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 from0
toM
. ! !
! 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 ofthis
, ! and is UNDEFINEDon 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 ofthis
, ! and is UNDEFINEDon 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
intothis
. ! !
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 parameterT
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)\). ! ! IfN
is0
(the default), then the degree of a PPerm instance ! can be defined at runtime, and ifN
is not0
, then the degree is ! fixed at compile time. ! ! IfN
is0
, then the default value ofScalar
isuint32_t
. If !N
is not0
, then the default value ofScalar
is the smallest ! integer type able to holdN
. 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 from0
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 from0
toM
. ! !
! 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 parameterT
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
underx
inres
. 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
underx
inres
. 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
andy
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
andy
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 withT::container_type
. ! * any value incont
exceedscont.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 incont
exceedscont.size()
or is equal to ! UNDEFINED. ! ! \complexity ! Linear in the size of the containercont
. 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 containerx.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 incont
exceedscont.size()
and is not equal to ! UNDEFINED. ! * there are repeated values incont
. 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 incont
exceedscont.size()
and is not equal to ! UNDEFINED. ! * there are repeated values incont
. 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 parameterN
! *dom
andran
do not have the same size ! * any value indom
orran
is greater thanM
! * there are repeated entries indom
orran
. 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 inM
. 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
exceedsx.degree()
and is not equal ! to UNDEFINED; or ! *x
is not injective ! ! \complexity ! Linear in the size of the containerx.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 incont
exceedscont.size()
! * there are repeated values incont
. 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 inM
. 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
exceedsx.degree()
! *x
is not injective ! ! \complexity ! Linear in the size of the containerx.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); }