Partial Permutations¶
Overview¶
Defined in element.hpp
.
This page contains the documentation for the class template
libsemigroups::PartialPerm
.
Full API¶
-
template<typename
TIntType
>
structImageRightAction
<PartialPerm<TIntType>, PartialPerm<TIntType>>¶ Specialization of the adapter ImageRightAction for instance of PartialPerm.
- See
Public Functions
-
void
operator()
(PartialPerm<TIntType> &res, PartialPerm<TIntType> const &pt, PartialPerm<TIntType> const &x) const¶ Stores the idempotent \((xy) ^ {-1}xy\) in
res
.
-
template<typename
T
>
classPartialPerm
: public libsemigroups::PartialTransformation<T, PartialPerm<T>>¶ Template class for partial permutations.
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. \(\{(0)f, (1)f, \ldots, (n - 1)f\}\) where the value libsemigroups::UNDEFINED is used to indicate that \((i)f\) is undefined (i.e. not among the points where \(f\) is defined).
- Template Parameters
T
: the value of this template parameter can be used to reduce the amount of memory required by instances of this class. This must be an unsigned integral type.
Public Functions
-
PartialPerm
(std::vector<T> const &vec)¶ A constructor.
Constructs a PartialPerm using the corresponding PartialTransformation constructor and then checks that it represents a valid PartialPerm.
-
PartialPerm
(std::vector<T> &&vec)¶ A constructor.
The parameter
vector
should be a rvalue reference to defining data of a PartialPerm.Returns a PartialPerm whose defining data is
vec
. This constructor moves the data fromvec
, meaning thatvec
is changed by this constructor.
-
PartialPerm
(std::initializer_list<T> imgs)¶ A constructor.
Constructs a vector from
imgs
and uses the corresponding constructor.
-
PartialPerm
(std::vector<T> const &dom, std::vector<T> const &ran, size_t deg)¶ A constructor.
Constructs a partial perm of degree
deg
such thatfor all(dom[i])f = ran[i]
i
and which is undefined on every other value in the range 0 to (strictly less thandeg
). This member function asserts thatdom
andran
have equal size and thatdeg
is greater than to the maximum value indom
orran
.
-
PartialPerm
(std::initializer_list<T> dom, std::initializer_list<T> ran, size_t deg)¶ A constructor.
Constructs vectors from
dom
andran
and uses the constructor above.
-
void
validate
() const¶ Validates the data defining
this
.This member function throws a libsemigroups::LibsemigroupsException if any value of
this
is out of bounds (i.e. greater than or equal todegree()
), and not equal to libsemigroups::UNDEFINED), or if any image appears more than once.
-
PartialPerm
(PartialPerm const ©)¶ A copy constructor.
-
void
increase_degree_by
(size_t)¶ Increases the degree of
this
bydeg
.This does not make sense for all subclasses of Element.
-
bool
operator<
(const Element &that) const¶ Returns
true
ifthis
is less thanthat
.This defines a total order on partial permutations that is equivalent to that used by GAP. It is not short-lex on the list of images.
Returns
true
if something complicated istrue
andfalse
if it is not.
-
void
redefine
(Element const &x, Element const &y)¶ Multiply
x
andy
and stores the result inthis
.See Element::redefine for more details about this member function.
This member function asserts that the degrees of
x
,y
, andthis
, are all equal, and that neitherx
nory
equalsthis
.
-
size_t
crank
() const¶ Returns the rank of a partial permutation.
The rank of a partial permutation is the number of its distinct image values, not including libsemigroups::UNDEFINED. This member function involves slightly less work than PartialTransformation::crank since a partial permutation is injective, and so every image value occurs precisely once. This member function recomputes the return value every time it is called.
-
PartialPerm<T>
right_one
() const¶ Returns the idempotent \(x ^ {-1} x\) where \(x\) is the partial perm represented by
this
.
-
PartialPerm<T>
left_one
() const¶ Returns the idempotent \(xx ^ {-1}\) where \(x\) is the partial perm represented by
this
.
-
virtual void
redefine
() Multiplies
x
andy
and stores the result inthis
.Redefine
this
to be the product ofx
andy
. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.The implementation of this member function in the Element base class simply calls the 3 parameter version with third parameter 0. Any subclass of Element can implement either a two or three parameter version of this member function and the base class member function implements the other member function.
-
void
redefine
() Multiplies
x
andy
and stores the result inthis
.This version of the member function takes const pointers rather than const references, but otherwise behaves like the other Element::redefine.
-
virtual void
redefine
() Multiplies
x
andy
and stores the result inthis
.Redefine
this
to be the product ofx
andy
. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.The implementation of this member function in the Element base class simply calls the 2 parameter version and ignores the third parameter
thread_id
. Any subclass of Element can implement either a two or three parameter version of this member function and the base class member function implements the other member function.The parameter
thread_id
is required in some derived classes of Element because some temporary storage is required to find the product ofx
andy
.Note that if different threads call this member function on a derived class of Element where static temporary storage is used in the redefine member function with the same value of
thread_id
, then bad things may happen.
-
void
redefine
() Multiplies
x
andy
and stores the result inthis
.This member function differs from the the previous only in taking pointers instead of references.
-
size_t
complexity
() const Returns the approximate time complexity of multiplying two partial transformations.
The approximate time complexity of multiplying partial transformations is just their degree.
-
size_t
degree
() const Returns the degree of a partial transformation.
The degree of a partial transformation is the number of points used in its definition.
-
PartialPerm<T>
identity
() const¶ Returns the identity transformation with same degree as
this
.This member function returns a new partial transformation with degree equal to the degree of
this
that fixes every value from 0 to the degree ofthis
.
-
virtual bool
operator==
(Element const&) const = 0 Returns
true
ifthis
equalsthat
.This member function checks the mathematical equality of two Element objects in the same subclass of Element.
-
bool
operator>
(Element const &that) const Returns
true
ifthis
is greater thanthat
.This member function returns
true
ifthis
is greater thanthat
, under the ordering defined by the operator <.
-
bool
operator!=
(Element const &that) const Returns
true
ifthis
is not equal tothat
.This member function returns
true
ifthis
is mathematically not equal tothat
.
-
bool
operator<=
(Element const &that) const Returns
true
ifthis
is less than or equal tothat
.This member function returns
true
ifthis
is less than (under the order defined by the operator <) or mathematically equal tothat
.
-
bool
operator>=
(Element const &that) const Returns
true
ifthis
is less than or equal tothat
.This member function returns
true
ifthis
is greater than (under the order defined by the operator <) or mathematically equal tothat
.
-
size_t
hash_value
() const Return the hash value of an Element.
This member function returns a hash value for an object in a subclass of Element. This value is only computed the first time this member function is called.
-
virtual void
swap
(Element&) = 0 Swap another Element with
this
.This member function swaps the defining data of
x
andthis
.
-
void
redefine
(Element const *x, Element const *y) Multiplies
x
andy
and stores the result inthis
.This version of the member function takes const pointers rather than const references, but otherwise behaves like the other Element::redefine.
-
virtual void
redefine
(Element const &x, Element const &y, size_t) Multiplies
x
andy
and stores the result inthis
.Redefine
this
to be the product ofx
andy
. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.The implementation of this member function in the Element base class simply calls the 2 parameter version and ignores the third parameter
thread_id
. Any subclass of Element can implement either a two or three parameter version of this member function and the base class member function implements the other member function.The parameter
thread_id
is required in some derived classes of Element because some temporary storage is required to find the product ofx
andy
.Note that if different threads call this member function on a derived class of Element where static temporary storage is used in the redefine member function with the same value of
thread_id
, then bad things may happen.
-
void
redefine
(Element const *x, Element const *y, size_t) Multiplies
x
andy
and stores the result inthis
.This member function differs from the the previous only in taking pointers instead of references.
-
virtual Element *
heap_copy
() const = 0 Returns a new element completely independent of
this
.This member function really copies an Element. To minimise the amount of copying when Element objects are inserted in a std::unordered_map and other containers, an Element behaves somewhat like a pointer, in that the actual data in an Element is only copied when this member function is called. Otherwise, if an Element is copied, then its defining data is only stored once.
-
virtual Element *
heap_identity
() const = 0 Returns an independent copy of the identity.
This member function returns a copy of the identity element (in the appropriate semigroup) which is independent from previous copies.
Public Static Functions
-
static PartialPerm<T>
identity
(size_t n)¶ Returns the identity transformation with
n
.This member function returns a new partial transformation with degree equal to
n
and that fixes every value from 0 ton
.