Defined in transf.hpp.

This page contains the documentation for functionality in libsemigroups for various partial transformations.

A partial transformation \(f\) is just a function defined on a subset of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) called the degree of f. A partial transformation is stored as a container of the images of \(\{0, 1, \ldots, n -1\}\), i.e. \(((0)f, (1)f, \ldots, (n - 1)f)\) where the value UNDEFINED is used to indicate that \((i)f\) is, you guessed it, undefined (i.e. not among the points where \(f\) is defined).

Topics
	make<Transf>
	Safely construct a Transf instance.

	make<PPerm>
	Safely construct a PPerm instance.

	make<Perm>
	Safely construct a Perm instance.

Classes
class	DynamicPTransf< Scalar >
	Partial transformations with dynamic degree. More...

class	Perm< N, Scalar >
	Permutations with static or dynamic degree. More...

class	PPerm< N, Scalar >
	Partial permutations with static or dynamic degree. More...

class	PTransfBase< Scalar, Container >
	Base class for partial transformations. More...

class	StaticPTransf< N, Scalar >
	Partial transformations with static degree. More...

class	Transf< N, Scalar >
	Transformations with static or dynamic degree. More...

Typedefs
template<size_t N>
using	LeastPerm = typename detail::LeastPermHelper<N>::type
	Type of perms using the least memory for a given degree.

template<size_t N>
using	LeastPPerm = typename detail::LeastPPermHelper<N>::type
	Type of partial perms using the least memory for a given degree.

template<size_t N>
using	LeastTransf = typename detail::LeastTransfHelper<N>::type
	Type of transformations using the least memory for a given degree.

template<size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
using	PTransf
	Partial transformations with static or dynamic degree.

Functions
template<typename T>
std::vector< typename T::point_type >	domain (T const &f)
	Returns the set of points where a partial transformation is defined.

template<typename T, typename Scalar>
void	domain (T const &f, std::vector< Scalar > &dom)
	Replace the contents of a vector by the set of points where a partial transformation is defined.

template<typename T>
std::vector< typename T::point_type >	image (T const &f)
	Returns the set of images of a partial transformation.

template<typename T, typename Scalar>
void	image (T const &f, std::vector< Scalar > &im)
	Replace the contents of a vector by the set of images of a partial transformation.

template<size_t N, typename Scalar>
Perm< N, Scalar >	inverse (Perm< N, Scalar > const &f)
	Returns the inverse of a permutation.

template<size_t N, typename Scalar>
void	inverse (Perm< N, Scalar > const &from, Perm< N, Scalar > &to)
	Returns the inverse of a permutation.

template<size_t N, typename Scalar>
PPerm< N, Scalar >	inverse (PPerm< N, Scalar > const &f)
	Returns the inverse of a partial perm.

template<size_t N, typename Scalar>
void	inverse (PPerm< N, Scalar > const &from, PPerm< N, Scalar > &to)
	Replace contents of a partial perm with the inverse of another.

template<size_t N, typename Scalar>
PPerm< N, Scalar >	left_one (PPerm< N, Scalar > const &f)
	Returns the left one of a partial perm.

template<typename T>
auto	one (T const &f) -> std::enable_if_t< IsDerivedFromPTransf< T >, T >
	Returns the identity transformation of same degree as a sample.

template<size_t N, typename Scalar>
PPerm< N, Scalar >	right_one (PPerm< N, Scalar > const &f)
	Returns the right one of a partial perm.

template<typename Scalar, typename Container>
void	throw_if_image_value_out_of_range (PTransfBase< Scalar, Container > const &f)
	Check a partial transformation.

template<size_t N, typename Scalar>
void	throw_if_image_value_out_of_range (Transf< N, Scalar > const &f)
	Check a transformation.

template<size_t N, typename Scalar>
auto	throw_if_not_perm (Perm< N, Scalar > const &f)
	Check a permutation.

template<size_t N, typename Scalar>
void	throw_if_not_pperm (PPerm< N, Scalar > const &f)
	Check a partial perm.

template<size_t N, typename Scalar>
std::string	to_human_readable_repr (Perm< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}", size_t max_width=72)
	Return a human readable representation of a Perm object.

template<size_t N, typename Scalar>
std::string	to_human_readable_repr (PPerm< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}", size_t max_width=72)
	Return a human readable representation of a PPerm object.

template<size_t N, typename Scalar>
std::string	to_human_readable_repr (Transf< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}", size_t max_width=72)
	Return a human readable representation of a Transf object.

template<size_t N, typename Scalar>
std::string	to_input_string (Perm< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}")
	Return a string that can be used to recreate a permutation.

template<size_t N, typename Scalar>
std::string	to_input_string (PPerm< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}")
	Return a string that can be used to recreate a partial permutation.

template<size_t N, typename Scalar>
std::string	to_input_string (Transf< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}")
	Return a string that can be used to recreate a transformation.

Variables
template<typename T>
static constexpr bool	IsDerivedFromPTransf = std::is_base_of_v<detail::PTransfPolymorphicBase, T>
	Helper variable template.

template<typename T>
static constexpr bool	IsDynamic = detail::IsDynamicHelper<T>::value
	Helper variable template.

template<typename T>
static constexpr bool	IsPerm = detail::IsPermHelper<T>::value
	Helper variable template.

template<typename T>
static constexpr bool	IsPPerm = detail::IsPPermHelper<T>::value
	Helper variable template.

template<typename T>
static constexpr bool	IsPTransf = detail::IsPTransfHelper<T>::value
	Helper variable template.

template<typename T>
static constexpr bool	IsStatic = detail::IsStaticHelper<T>::value
	Helper variable template.

template<typename T>
static constexpr bool	IsTransf = detail::IsTransfHelper<T>::value
	Helper variable template.

Typedef Documentation

◆ LeastPerm

template<size_t N>

using LeastPerm = typename detail::LeastPermHelper<N>::type

Helper for getting the type of the least size, and fastest, permutation in libsemigroups or HPCombi that are defined on at most N points.

Defined in transf.hpp.

Template Parameters

N	the maximum number of points the permutations will be defined on.

◆ LeastPPerm

template<size_t N>

using LeastPPerm = typename detail::LeastPPermHelper<N>::type

Helper for getting the type of the least size, and fastest, partial perm in libsemigroups or HPCombi that are defined on at most N points.

Defined in transf.hpp.

Template Parameters

N	the maximum number of points the partial perms will be defined on.

◆ LeastTransf

template<size_t N>

using LeastTransf = typename detail::LeastTransfHelper<N>::type

Helper for getting the type of the least size, and fastest, transformation in libsemigroups or HPCombi that are defined on at most N points.

Defined in transf.hpp.

Template Parameters

N	the maximum number of points the transformations will be defined on.

◆ PTransf

template<size_t N = 0, typename Scalar = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>

using PTransf

Initial value:

std::

conditional_t<N == 0, DynamicPTransf<Scalar>, StaticPTransf<N, Scalar>>

libsemigroups::StaticPTransf

Partial transformations with static degree.

Definition transf.hpp:830

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.

Template Parameters

N	the degree (default: `0`).
Scalar	an unsigned integer type (the type of the image values).

Function Documentation

◆ domain() [1/2]

template<typename T>

std::vector< typename T::point_type > domain ( T const & f )

nodiscard

Returns a std::vector containing those values i such that:

\(i\in \{0, \ldots, n - 1\}\) where \(n\) is PTransfBase::degree() of the 1st parameter f; and
f[i] != UNDEFINED.

Template Parameters

T	the type of the 1st argument (Transf, libsemigroups::PTransf, PPerm, or Perm).

Parameters

f	the partial transformation whose image is sought.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n)\) where \(n\) equals PTransfBase::degree() of f.

See also: image

◆ domain() [2/2]

template<typename T, typename Scalar>

void domain	(	T const &	f,
		std::vector< Scalar > &	dom )

Replaces the contents of the 2nd argument dom by those values i such that:

\(i\in \{0, \ldots, n - 1\}\) where \(n\) is PTransfBase::degree() of the 1st parameter f; and
f[i] != UNDEFINED.

Template Parameters

T	the type of the 1st argument (Transf, libsemigroups::PTransf, PPerm, or Perm).
Scalar	the type of the values in the 2nd argument (typically T::point_type where `T` is the 1st template parameter).

Parameters

f	the partial transformation whose image is sought.
dom	vector to store the result.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n)\) where \(n\) equals PTransfBase::degree() of f.

See also: image

◆ image() [1/2]

template<typename T>

std::vector< typename T::point_type > image ( T const & f )

nodiscard

Returns a std::vector containing those values f[i] such that:

\(i\in \{0, \ldots, n - 1\}\) where \(n\) is PTransfBase::degree() of the 1st parameter f; and
f[i] != UNDEFINED.

Template Parameters

T	the type of the 1st argument (Transf, libsemigroups::PTransf, PPerm, or Perm).

Parameters

f	the partial transformation whose image is sought.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n\log(n))\) where \(n\) equals PTransfBase::degree() of f.

See also: domain

◆ image() [2/2]

template<typename T, typename Scalar>

void image	(	T const &	f,
		std::vector< Scalar > &	im )

Replaces the contents of the 2nd argument im by those values f[i] where:

\(i\in \{0, \ldots, n - 1\}\) where \(n\) is PTransfBase::degree() of the 1st parameter f;
f[i] != UNDEFINED.

Template Parameters

T	the type of the 1st argument (Transf, libsemigroups::PTransf, PPerm, or Perm).
Scalar	the type of the values in the 2nd argument (typically T::point_type where `T` is the 1st template parameter.

Parameters

f	the partial transformation whose image is sought.
im	vector to store the result.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n\log(n))\) where \(n\) equals PTransfBase::degree() of f.

See also: domain

◆ inverse() [1/4]

template<size_t N, typename Scalar>

Perm< N, Scalar > inverse ( Perm< N, Scalar > const & f )

nodiscard

This function returns a newly constructed inverse of f. The inverse of a permutation \(f\) is the permutation \(g\) such that \(fg = gf\) is the identity permutation of degree \(N\).

Template Parameters

N	the degree of `f`.
Scalar	the type of points of `f`.

Parameters

f	the permutation to invert.

Returns: A value of type PPerm.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ inverse() [2/4]

template<size_t N, typename Scalar>

void inverse	(	Perm< N, Scalar > const &	from,
		Perm< N, Scalar > &	to )

This function inverts from into to. The inverse of a permutation \(f\) is the permutation \(g\) such that \(fg = gf\) is the identity permutation of degree \(n\).

Template Parameters

N	the degree of `f`.
Scalar	the type of points of `f`.

Parameters

from	the permutation to invert.
to	the permutation to hold the inverse of `from`.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ inverse() [3/4]

template<size_t N, typename Scalar>

PPerm< N, Scalar > inverse ( PPerm< N, Scalar > const & f )

nodiscard

This function returns a newly constructed inverse of f. The inverse of a partial permutation \(f\) is the partial perm \(g\) such that \(fgf = f\) and \(gfg = g\).

Template Parameters

N	the degree of `f`.
Scalar	the type of points.

Parameters

f	the partial perm to invert.

Returns: A value of type PPerm.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

See also: right_one and left_one

◆ inverse() [4/4]

template<size_t N, typename Scalar>

void inverse	(	PPerm< N, Scalar > const &	from,
		PPerm< N, Scalar > &	to )

This function inverts from into to. The inverse of a partial permutation \(f\) is the partial perm \(g\) such that \(fgf = f\) and \(gfg = g\).

Parameters

from	the partial perm to invert.
to	the partial perm to hold the inverse of `from`.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ left_one()

template<size_t N, typename Scalar>

PPerm< N, Scalar > left_one ( PPerm< N, Scalar > const & f )

nodiscard

This function returns a newly constructed partial perm with degree equal to N that fixes every value in the domain of f, and is UNDEFINED on any other values.

Parameters

f	the partial perm.

Returns: A value of type PPerm<N, Scalar>.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ one()

template<typename T>

auto one ( T const & f ) -> std::enable_if_t<IsDerivedFromPTransf<T>, T>

nodiscard

This function returns a newly constructed partial transformation with degree equal to the degree of f that fixes every value from 0 to f.degree() - 1.

Template Parameters

T	the type of the transformation being constructed (Perm, PPerm, Transf, or PTransf).

Returns: A value of type T.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ right_one()

template<size_t N, typename Scalar>

PPerm< N, Scalar > right_one ( PPerm< N, Scalar > const & f )

nodiscard

This function returns a newly constructed partial perm with degree equal to N that fixes every value in the image of the argument f, and is UNDEFINED on any other values.

Parameters

f	the partial perm.

Returns: A value of type PPerm<N, Scalar>.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in f.degree().

◆ throw_if_image_value_out_of_range() [1/2]

template<typename Scalar, typename Container>

void throw_if_image_value_out_of_range ( PTransfBase< Scalar, Container > const & f )

Template Parameters

N	the degree.
Scalar	an unsigned integer type (the type of the image values).

Parameters

f	the partial transformation to check.

Exceptions

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 UNDEFINED.

Complexity: Linear in degree().

◆ throw_if_image_value_out_of_range() [2/2]

template<size_t N, typename Scalar>

void throw_if_image_value_out_of_range ( Transf< N, Scalar > const & f )

Template Parameters

N	the number of points.
Scalar	the type of the points.

Parameters

f	the transformation.

Exceptions

LibsemigroupsException if the image of any point exceeds f.degree() or is equal to UNDEFINED.

Complexity: Linear in f.degree().

◆ throw_if_not_perm()

template<size_t N, typename Scalar>

auto throw_if_not_perm ( Perm< N, Scalar > const & f )

Template Parameters

N	the first template parameter of Perm.
Scalar	the second template parameter of Perm.

Parameters

f	the permutation.

Exceptions

LibsemigroupsException

if:

the image of any point in f exceeds f.degree()
f is not injective

Complexity: Linear in f.degree().

◆ throw_if_not_pperm()

template<size_t N, typename Scalar>

void throw_if_not_pperm ( PPerm< N, Scalar > const & f )

Template Parameters

T	the type of the partial perm to check.

Parameters

f	the partial perm.

Exceptions

LibsemigroupsException

if:

the image of any point in f exceeds f.degree() and is not equal to UNDEFINED; or
f is not injective

Complexity: Linear in f.degree().

◆ to_human_readable_repr() [1/3]

template<size_t N, typename Scalar>

std::string to_human_readable_repr	(	Perm< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}",
		size_t	max_width = 72 )

nodiscard

This function returns a human readable representation of a Perm object. The returned std::string is either the same as to_input_string if the width of the returned string is less than the parameter max_width, or a std::string of the form "<permutation of degree X>" if not.

If the returned value of to_input_string has length less than max_width, then the following applies. If neither prefix nor braces is specified, then the returned string will have the form "Perm<N, Scalar>({...})" where N and Scalar are replaced by their values, and ... is replaced by the contents of x. If prefix is a non-empty string, its value will replace the prefix "Perm<N, Scalar>" in the returned string.

Template Parameters

N	the degree of the permutation `x`.
Scalar	the type of the image values.

Parameters

x	the Perm.
prefix	a prefix for the returned string (defaults to `""`).
braces	the braces to use in the string (defaults to `"{}"`).
max_width	the maximum width of the returned string (defaults to `72`).

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_human_readable_repr() [2/3]

template<size_t N, typename Scalar>

std::string to_human_readable_repr	(	PPerm< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}",
		size_t	max_width = 72 )

nodiscard

This function returns a human readable representation of a PPerm object. The returned std::string is either the same as to_input_string if the width of the returned string is less than the parameter max_width, or a std::string of the form "<partial permutation of degree X and rank Y>" if not.

If the returned value of to_input_string has length less than max_width, then the following applies. If neither prefix nor braces is specified, the returned string will have the form "PPerm<N, ! Scalar>({dom}, {im}, {deg})" where N and Scalar are replaced by their values, and dom, im, and degree are replaced by the domain, image, and degree of x, respectively. If prefix is a non-empty string, its value will replace the prefix "PPerm<N, Scalar>" in the returned string.

Template Parameters

N	the degree of the partial permutation `x`.
Scalar	the type of the image values.

Parameters

x	the PPerm.
prefix	a prefix for the returned string (defaults to `""`).
braces	the braces to use in the string (defaults to `"{}"`).
max_width	the maximum width of the returned string (defaults to `72`).

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ to_human_readable_repr() [3/3]

template<size_t N, typename Scalar>

std::string to_human_readable_repr	(	Transf< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}",
		size_t	max_width = 72 )

nodiscard

This function returns a human readable representation of a Transf object. The returned std::string is either the same as to_input_string if the width of the returned string is less than the parameter max_width, or a std::string of the form "<transformation of degree X and rank Y>" if not.

If the returned value of to_input_string has length less than max_width, then the following applies. If neither prefix nor braces is specified, then the returned string will have the form "Transf<N, Scalar>({...})" where N and Scalar are replaced by their values, and ... is replaced by the contents of x. If prefix is a non-empty string, its value will replace the prefix "Transf<N, ! Scalar>" in the returned string.

  \tparam N the degree of the transformation \p x.
  \tparam Scalar the type of the image values.

  \param x the Transf.
  \param prefix a prefix for the returned string (defaults to `""`).
  \param braces the braces to use in the string (defaults to `"{}"`).
  \param max_width the maximum width of the returned string (defaults to
  \c 72).

  \par Exceptions
  This function guarantees not to throw a \ref LibsemigroupsException.

◆ to_input_string() [1/3]

template<size_t N, typename Scalar>

std::string to_input_string	(	Perm< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}" )

nodiscard

This function returns a std::string containing the input required to construct a copy of the argument x.

If neither prefix nor braces is specified, then the returned string will have the form "Perm<N, Scalar>({...})" where N and Scalar are replaced by their values, and ... is replaced by the contents of x. If prefix is a non-empty string, its value will replace the prefix "Perm<N, Scalar>" in the returned string.

Template Parameters

N	the degree.
Scalar	an unsigned integer type (the type of the image values).

Parameters

x	the permutation.
prefix	a prefix for the returned string (defaults to `""`).
braces	the braces to use in the string (defaults to `"{}"`).

Returns: A string containing the input required to recreate x.

Exceptions

LibsemigroupsException if the argument braces is not of length 2.

◆ to_input_string() [2/3]

template<size_t N, typename Scalar>

std::string to_input_string	(	PPerm< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}" )

nodiscard

This function returns a std::string containing the input required to construct a copy of the argument x.

If neither prefix nor braces is specified, the returned string will have the form "PPerm<N, Scalar>({dom}, {im}, {deg})" where N and Scalar are replaced by their values, and dom, im, and degree are replaced by the domain, image, and degree of x, respectively. If prefix is a non-empty string, its value will replace the prefix "PPerm<N, Scalar>" in the returned string.

Template Parameters

N	the degree.
Scalar	an unsigned integer type (the type of the image values).

Parameters

x	the partial permutation.
prefix	a prefix for the returned string (defaults to `""`).
braces	the braces to use in the string (defaults to `"{}"`).

Returns: A string containing the input required to recreate x.

Exceptions

LibsemigroupsException if the argument braces is not of length 2.

◆ to_input_string() [3/3]

template<size_t N, typename Scalar>

std::string to_input_string	(	Transf< N, Scalar > const &	x,
		std::string_view	prefix = "",
		std::string_view	braces = "{}" )

nodiscard

This function returns a std::string containing the input required to construct a copy of the argument x.

If neither prefix nor braces is specified, then the returned string will have the form "Transf<N, Scalar>({...})" where N and Scalar are replaced by their values, and ... is replaced by the contents of x. If prefix is a non-empty string, its value will replace the prefix "Transf<N, Scalar>" in the returned string.

Template Parameters

N	the degree.
Scalar	an unsigned integer type (the type of the image values).

Parameters

x	the transformation.
prefix	a prefix for the returned string (defaults to `""`).
braces	the braces to use in the string (defaults to `"{}"`).

Returns: A string containing the input required to recreate x.

The value of this variable is true if the template parameter T is either DynamicPTransf or StaticPTransf for any template parameters.

Template Parameters

T a type.

See also: libsemigroups::IsStatic and libsemigroups::IsDynamic

◆ IsStatic

template<typename T>

bool IsStatic = detail::IsStaticHelper<T>::value

staticconstexpr

The value of this variable is true if the template parameter T is derived from StaticPTransf.

Template Parameters

T a type.

◆ IsTransf

template<typename T>

bool IsTransf = detail::IsTransfHelper<T>::value

staticconstexpr

The value of this variable is true if the template parameter T is Transf for any template parameters.

Template Parameters

T a type.

Topics

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ LeastPerm

◆ LeastPPerm

◆ LeastTransf

◆ PTransf

Function Documentation

◆ domain() [1/2]

◆ domain() [2/2]

◆ image() [1/2]

◆ image() [2/2]

◆ inverse() [1/4]

◆ inverse() [2/4]

◆ inverse() [3/4]

◆ inverse() [4/4]

◆ left_one()

◆ one()

◆ right_one()

◆ throw_if_image_value_out_of_range() [1/2]

◆ throw_if_image_value_out_of_range() [2/2]

◆ throw_if_not_perm()

◆ throw_if_not_pperm()

◆ to_human_readable_repr() [1/3]

◆ to_human_readable_repr() [2/3]

◆ to_human_readable_repr() [3/3]

◆ to_input_string() [1/3]

◆ to_input_string() [2/3]

◆ to_input_string() [3/3]

Variable Documentation

◆ IsDerivedFromPTransf

◆ IsDynamic

◆ IsPerm

◆ IsPPerm

◆ IsPTransf

◆ IsStatic

◆ IsTransf