SchreierSims< N, Point, Element, Traits >

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>
class libsemigroups::SchreierSims< N, Point, Element, Traits >

Defined in schreier-sims.hpp.

This class implements a deterministic version of the Schreier-Sims algorithm acting on a relatively small number of points ( \(< 1000\)).

Template Parameters

N	the largest point not fixed by the permutations in the permutation group to be represented by this.
Point	the type of the points acted on (default: the member type of SmallestInteger with template parameter N).
Element	the type of the group elements acting on Point (default: the member type of LeastPerm with template parameter N).
Traits	the type of traits object (default: SchreierSimsTraits with template parameters N, Point, and Element).

See also

SchreierSimsTraits.

Example

SchreierSims<5> S;
using Perm = decltype(S)::element_type;
S.add_generator(Perm({1, 0, 2, 3, 4}));
S.add_generator(Perm({1, 2, 3, 4, 0}));
S.size(); // 120

Public Types
using	Action = typename Traits::Action
	Alias for Traits::Action.
using	const_element_reference
	Type of a const reference to the elements.
using	Degree = typename Traits::Degree
	Adapter for the degree of an element.
using	domain_type = typename Traits::domain_type
	Type of the object containing all points acted on.
using	element_reference
	Type of a reference to the elements.
using	element_type = typename detail::BruidhinnTraits<Element>::value_type
	Type of the elements.
using	EqualTo = typename Traits::EqualTo
	Adapter for testing equality.
using	index_type = typename Traits::index_type
	Type of indices.
using	Inverse = typename Traits::Inverse
	Adapter for the inverse of an element.
using	One = typename Traits::One
	Adapter for the identity element of the given type.
using	point_type = Point
	Type of the points acted on.
using	Product = typename Traits::Product
	Adapter for the product of two elements.
using	Swap = typename Traits::Swap
	Adapter for swapping.

Public Member Functions
	SchreierSims ()
	Default constructor.
	SchreierSims (SchreierSims &&)
	Default move constructor.
	SchreierSims (SchreierSims const &that)
	Default copy constructor.
SchreierSims &	add_base_point (point_type pt)
	Add a base point to the stabiliser chain.
bool	add_generator (const_element_reference x)
	Add a generator.
bool	add_generator_no_checks (const_element_reference x)
	Add a generator.
point_type	base (index_type index) const
	Get a base point.
point_type	base_no_checks (index_type index) const
	Get a base point.
size_t	base_size () const noexcept
	Get the size of the current base.
bool	contains (const_element_reference x)
	Test membership of an element.
uint64_t	current_size () const
	Returns the size of the group represented by this, without running.
bool	currently_contains (const_element_reference x) const
	Test membership of an element without running.
bool	empty () const
	Check if any generators have been added so far.
bool	finished () const noexcept
	Check if the stabiliser chain is fully enumerated.
const_element_reference	generator (index_type index) const
	Get a generator.
const_element_reference	generator_no_checks (index_type index) const
	Get a generator.
SchreierSims &	init ()
	Reset to the trivial group.
const_element_reference	inverse_transversal_element (index_type depth, point_type pt) const
	Get an inverse of a transversal element.
const_element_reference	inverse_transversal_element_no_checks (index_type depth, point_type pt) const
	Get an inverse of a transversal element.
size_t	number_of_generators () const
	The number of generators.
size_t	number_of_strong_generators (index_type depth) const
	The number of strong generators at a given depth.
size_t	number_of_strong_generators_no_checks (index_type depth) const
	The number of strong generators at a given depth.
const_element_reference	one () const noexcept(noexcept(this->to_external_const(_one)))
	Returns a const reference to the identity.
SchreierSims &	operator= (SchreierSims &&)
	Default move assignment.
SchreierSims &	operator= (SchreierSims const &that)
	Default copy assignment.
bool	orbit_lookup (index_type depth, point_type pt) const
	Check if a point is in the orbit of a basepoint.
bool	orbit_lookup_no_checks (index_type depth, point_type pt) const
	Check if a point is in the orbit of a basepoint.
void	run ()
	Run the Schreier-Sims algorithm.
const_element_reference	sift (const_element_reference x) const
	Sift an element through the stabiliser chain.
void	sift_inplace (element_reference x) const
	Sift an element through the stabiliser chain in-place.
void	sift_inplace_no_checks (element_reference x) const
	Sift an element through the stabiliser chain in-place.
const_element_reference	sift_no_checks (const_element_reference x) const
	Sift an element through the stabiliser chain.
uint64_t	size ()
	Returns the size of the group represented by this.
const_element_reference	strong_generator (index_type depth, index_type index) const
	Get a strong generator.
const_element_reference	strong_generator_no_checks (index_type depth, index_type index) const
	Get a strong generator.
const_element_reference	transversal_element (index_type depth, point_type pt) const
	Get a transversal element.
const_element_reference	transversal_element_no_checks (index_type depth, point_type pt) const
	Get a transversal element.

Member Typedef Documentation

Action

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using Action = typename Traits::Action

Alias for Traits::Action. See Action for further details.

const_element_reference

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using const_element_reference

Initial value:

 
        typename detail::BruidhinnTraits<Element>::const_reference

The type of a const reference to the elements of a SchreierSims instance.

Degree

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using Degree = typename Traits::Degree

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature size_t operator()(Element const& x) const (possibly noexcept, inline and/or constexpr also).

The return value of the call operator ought to indicate the degree of a Element instance which may or may not depend on the parameter x. The degree of a permutation, for instance, would be the the number of points it acts on, the degree of a matrix is its dimension, and so on. This is used, for example, by SchreierSimsTraits in some member functions to determine whether it is known a priori that a permutation does not belong to the object, because it acts on too many points.

Template Parameters

Element

the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

• FroidurePinTraits
• KoniecznyTraits
• SchreierSimsTraits

Example

template <>
struct Degree<BMat8> {
  constexpr inline size_t operator()(BMat8 const&) const noexcept {
    return 8;
  }
};

domain_type

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using domain_type = typename Traits::domain_type

Type of the object containing all points acted on.

element_reference

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using element_reference

Initial value:

 
        typename detail::BruidhinnTraits<Element>::reference

The type of a reference to the elements of a SchreierSims instance.

element_type

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using element_type = typename detail::BruidhinnTraits<Element>::value_type

The type of the elements of a SchreierSims instance with const removed, and if Element is a pointer to const, then the second const is also removed.

EqualTo

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using EqualTo = typename Traits::EqualTo

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature bool operator()(Value const&, Value const&) (possibly noexcept, inline and/or constexpr also) for use with, for example, std::unordered_map.

Template Parameters

Value

the type of objects to compare.

The second template parameter exists for SFINAE.

Used by:

• ActionTraits
• FroidurePinTraits
• SchreierSimsTraits

index_type

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using index_type = typename Traits::index_type

Type of indices.

Inverse

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using Inverse = typename Traits::Inverse

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature Point operator()(Element const& x) const (possibly noexcept, inline and/or constexpr also).

The call operator should return the inverse of the element x under the assumption that x has an inverse (in the sense of groups). For example, if x is a permutation, then this would return its inverse. If x is a permutation matrix of type BMat8, then this operator would return its transpose.

Template Parameters

Element

the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

• SchreierSimsTraits

Example

template <>
struct Inverse<BMat8> {
  inline BMat8 operator()(BMat8 const& x) const noexcept {
    LIBSEMIGROUPS_ASSERT(x * x.transpose() == x.one());
    return x.transpose();
  }
};

One

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using One = typename Traits::One

Specialisations of this struct should be stateless trivially default constructible with two call operator of signatures:

1. Element operator()(size_t n) const (possibly noexcept, inline and/or constexpr also) returning a multiplicative identity element for the category Element and with Degree<Element>()(x) equal to the parameter n. For example, if Element is a type of n x n matrices, then this should return the n x n identity matrix.
2. Element operator()(T const&) const (possibly noexcept, inline and/or constexpr also). This could be implemented as:

   Element operator()(Element const& x) const noexcept {
     return this->operator()(Degree<Element>()(x));
   }

Template Parameters

Element

the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

• ActionTraits
• FroidurePinTraits
• SchreierSimsTraits

Example

template <typename T>
struct One<
    T,
    typename std::enable_if<std::is_base_of<PTransf16, T>::value>::type> {
  T operator()(size_t = 0) const noexcept {
    return T::one();
  }
 
  T operator()(T const&) const noexcept {
    return T::one();
  }
};

point_type

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using point_type = Point

Type of the points acted on. Also the template parameter Point.

Product

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using Product = typename Traits::Product

Defined in adapters.hpp.

Specialisations of this struct should be stateless trivially default constructible with a call operator of signature void operator()(Element&, Element const&, Element const&, size_t = 0) (possibly noexcept, inline and/or constexpr also).

The call operator should change xy in-place to be the product of x and y. The 4th parameter is optional and it can be used as an index for static thread local storage, that might be required for forming the product of x and y. The purpose of the 1st parameter is to avoid repeated allocations of memory to hold temporary products that are discarded soon after they are created.

Template Parameters

Element

the type of the elements of a semigroup.

The second template parameter exists for SFINAE.

Used by:

• ActionTraits
• FroidurePinTraits
• SchreierSimsTraits

Example

template <>
struct Product<size_t> {
  void operator()(size_t& xy, size_t x, size_t y, size_t = 0) const
  noexcept {
    xy = x * y;
  }
};

Swap

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

using Swap = typename Traits::Swap

Defined in adapters.hpp.

This type should be a stateless trivially default constructible with a call operator of signature void operator()(Value&, Value&) (possibly noexcept, inline and/or constexpr also) which swaps its arguments.

Template Parameters

Value

the type of objects to swap.

The second template parameter exists for SFINAE.

Used by:

• ActionTraits
• FroidurePinTraits
• SchreierSimsTraits

Constructor & Destructor Documentation

SchreierSims() [1/3]

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims

(

)

Construct a SchreierSims object representing the trivial group.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(N ^ 2)\) where N is the first template parameter.

SchreierSims() [2/3]

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims

(

SchreierSims< N, Point, Element, Traits > &&

)

Default move constructor.

SchreierSims() [3/3]

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims

(

SchreierSims< N, Point, Element, Traits > const &

that

)

Default copy constructor.

Member Function Documentation

add_base_point()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims & add_base_point

(

point_type

pt

)

Add a base point to the stabiliser chain.

Parameters

pt	the base point to add.

Exceptions

LibsemigroupsException	if pt is out of range.
LibsemigroupsException	if finished() returns true.
LibsemigroupsException	if pt is already a base point.

Complexity

Linear in the current number of base points.

add_generator()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool add_generator

(

const_element_reference

x

)

This functions adds the argument x as a new generator if and only if x is not already an element of the group represented by the SchreierSims object.

Parameters

x	a const reference to the generator to add.

Returns

true if x is added as a generator and false if it is not.

Exceptions

LibsemigroupsException

if the degree of x is not equal to the first template parameter N, or if this already contains the maximum number of elements.

Complexity

Constant

add_generator_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool add_generator_no_checks

(

const_element_reference

x

)

This functions adds the argument x as a new generator if and only if x is not already an element of the group represented by the SchreierSims object. For example, the identity element is never added as a generator.

Parameters

x	a const reference to the generator to add.

Returns

true if x is added as a generator and false if it is not.

Complexity

Constant

Warning

This functions performs no checks on its arguments. In particular, if the degree of x is not equal to the first template parameter N, or if this already contains the maximum number of elements, then bad things will happen.

base()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

point_type base ( index_type index ) const

inlinenodiscard

Get a base point, having checked index if not out of range.

Parameters

index

the index of the base point.

Returns

the base point with index index.

Exceptions

LibsemigroupsException

if index is out of range.

Complexity

Constant.

base_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

point_type base_no_checks ( index_type index ) const

inlinenodiscard

Get a base point.

Parameters

index

the index of the base point.

Returns

the base point with index index.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if index is out of range, then bad things will happen.

base_size()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

size_t base_size ( ) const

inlinenodiscardnoexcept

Get the size of the current base.

Returns

A size_t.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

contains()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool contains ( const_element_reference x )

nodiscard

Test membership of an element.

Parameters

x	a const reference to the possible element.

Returns

A bool.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Note

Returns false if the degree of x is not equal to the first template parameter N.

current_size()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

uint64_t current_size ( ) const

nodiscard

Returns the size of the group represented by this without running the algorithm.

Returns

the size, a value of uint64_t.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

currently_contains()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool currently_contains ( const_element_reference x ) const

nodiscard

Test membership of an element without running.

Parameters

x	a const reference to the possible element.

Returns

A bool.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Note

Returns false if the degree of x is not equal to the first template parameter N.

empty()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool empty ( ) const

inlinenodiscard

Check if any generators have been added so far.

Returns

true if number_of_generators() == 0 and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

finished()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool finished ( ) const

inlinenodiscardnoexcept

Check if the stabiliser chain is fully enumerated.

Returns

true if the stabiliser chain is fully enumerated and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

generator()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference generator ( index_type index ) const

inlinenodiscard

Get a generator with a given index, having checked that the index is in bounds.

Parameters

index

the index of the generator to return.

Returns

A const reference to the generator of this with index index.

Exceptions

LibsemigroupsException

if the index is out of bounds.

Complexity

Constant.

generator_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference generator_no_checks ( index_type index ) const

inlinenodiscard

Get a generator with a given index.

Parameters

index

the index of the generator to return.

Returns

A const reference to the generator of this with index index.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if index is out of bounds, then bad things will happen.

init()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims & init

(

)

Removes all generators, and orbits, and resets this so that it represents the trivial group, as if this had been newly constructed.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(N ^ 2)\) where N is the first template parameter.

inverse_transversal_element()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference inverse_transversal_element ( index_type depth, point_type pt ) const

nodiscard

Get an inverse of a transversal element.

Parameters

depth	the depth.
pt	the point to map to the base point under the inverse_transversal_element.

Returns

A const reference to the inverse_transversal_element element of this at depth depth moving the corresponding point pt to the basepoint.

Exceptions

LibsemigroupsException	if the depth is out of bounds.
LibsemigroupsException	if pt is not in the orbit of the basepoint.

Complexity

Constant.

inverse_transversal_element_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference inverse_transversal_element_no_checks ( index_type depth, point_type pt ) const

inlinenodiscard

Get an inverse of a transversal element.

Parameters

depth	the depth.
pt	the image of the base point under the traversal.

Returns

A const reference to the transversal element of this at depth depth moving the corresponding basepoint to the point pt.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if depth is out of bounds or pt is not in the orbit of the basepoint, then bad things will happen.

number_of_generators()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

size_t number_of_generators ( ) const

nodiscard

Return the number of generators.

Returns

The number of generators, a value of size_t.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

number_of_strong_generators()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

size_t number_of_strong_generators ( index_type depth ) const

inlinenodiscard

Return the number of strong generators at a given depth.

Parameters

depth

the depth.

Returns

The number of strong generators, a value of size_t, at depth depth of the stabiliser chain.

Exceptions

LibsemigroupsException

if the depth is out of bounds.

Complexity

Constant.

number_of_strong_generators_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

size_t number_of_strong_generators_no_checks ( index_type depth ) const

inlinenodiscard

Return the number of strong generators at a given depth.

Parameters

depth

the depth.

Returns

The number of strong generators, a value of size_t, at depth depth of the stabiliser chain.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if depth is out of bounds, then bad things will happen.

one()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference one ( ) const

inlinenodiscardnoexcept

Returns a const reference to the identity.

Returns

A const reference to the identity element.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

operator=() [1/2]

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims & operator=

(

SchreierSims< N, Point, Element, Traits > &&

)

Default move assignment.

operator=() [2/2]

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

SchreierSims & operator=

(

SchreierSims< N, Point, Element, Traits > const &

that

)

Default copy assignment

orbit_lookup()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool orbit_lookup ( index_type depth, point_type pt ) const

inlinenodiscard

Check if a point is in the orbit of a basepoint.

Parameters

depth	the depth.
pt	the point.

Returns

A boolean indicating if the point pt is in the orbit of the basepoint of this at depth depth.

Exceptions

LibsemigroupsException

if the depth is out of bounds or if pt is out of bounds.

Complexity

Constant.

orbit_lookup_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

bool orbit_lookup_no_checks ( index_type depth, point_type pt ) const

inlinenodiscard

Check if a point is in the orbit of a basepoint.

Parameters

depth	the depth.
pt	the point.

Returns

A boolean indicating if the point pt is in the orbit of the basepoint of this at depth depth.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if either depth or pt are out of bounds, then bad things will happen.

run()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

void run

(

)

Run the Schreier-Sims algorithm.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(N^2\log^3|G|+|T|N^2\log|G|)\) time and \(O(N^2\log|G|+|T|N)\) space, where N is the first template parameter, \(|G|\) is the size of the group and \(|T|\) is the number of generators of the group.

sift()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference sift ( const_element_reference x ) const

inlinenodiscard

Sift an element through the stabiliser chain, having checked the degree of x is equal to the first template parameter N.

Parameters

x	a const reference to a group element.

Returns

A value of type element_type.

Exceptions

LibsemigroupsException

if the degree of x is not equal to the first template parameter N.

sift_inplace()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

void sift_inplace ( element_reference x ) const

inline

Sift an element through the stabiliser chain in-place, having checked the degree of x is equal to the first template parameter N.

Parameters

x	a const reference to a group element.

Exceptions

LibsemigroupsException

if the degree of x is not equal to the first template parameter N.

sift_inplace_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

void sift_inplace_no_checks ( element_reference x ) const

inline

Sift an element through the stabiliser chain in-place.

Parameters

x	a const reference to a group element.

Warning

This functions performs no checks on its arguments. In particular, if either the degree of x is not equal to the first template parameter N, then bad things will happen.

sift_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference sift_no_checks ( const_element_reference x ) const

inline

Sift an element through the stabiliser chain.

Parameters

x	a const reference to a group element.

Returns

A value of type element_type.

Warning

This functions performs no checks on its arguments. In particular, if either the degree of x is not equal to the first template parameter N, then bad things will happen.

size()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

uint64_t size ( )

nodiscard

Returns the size of the group represented by this.

Returns

the size, a value of uint64_t.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

strong_generator()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference strong_generator ( index_type depth, index_type index ) const

nodiscard

Get a strong generator.

Parameters

depth	the depth.
index	the index of the generator to return.

Returns

A const reference to the strong generator of this at depth depth and with index index.

Exceptions

LibsemigroupsException	if the depth is out of bounds.
LibsemigroupsException	if the index is out of bounds.

Complexity

Constant.

strong_generator_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference strong_generator_no_checks ( index_type depth, index_type index ) const

inlinenodiscard

Get a strong generator.

Parameters

depth	the depth.
index	the index of the generator to return.

Returns

A const reference to the strong generator of this at depth depth and with index index.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if either depth or index is out of bounds, then bad things will happen.

transversal_element()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference transversal_element ( index_type depth, point_type pt ) const

nodiscard

Get a transversal element.

Parameters

depth	the depth.
pt	the image of the base point under the traversal.

Returns

A const reference to the transversal element of this at depth depth moving the corresponding basepoint to the point pt.

Exceptions

LibsemigroupsException	if the depth is out of bounds.
LibsemigroupsException	if pt is not in the orbit of the basepoint.

Complexity

Constant.

transversal_element_no_checks()

template<size_t N, typename Point = typename SmallestInteger<N>::type, typename Element = LeastPerm<N>, typename Traits = SchreierSimsTraits<N, Point, Element>>

const_element_reference transversal_element_no_checks ( index_type depth, point_type pt ) const

inlinenodiscard

Get a transversal element.

Parameters

depth	the depth.
pt	the image of the base point under the traversal.

Returns

A const reference to the transversal element of this at depth depth moving the corresponding basepoint to the point pt.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

Constant.

Warning

This functions performs no checks on its arguments. In particular, if depth is out of bounds or pt is not in the orbit of the basepoint, then bad things will happen.

---

The documentation for this class was generated from the following file:

• /Users/jdm3/libsemigroups/include/libsemigroups/schreier-sims.hpp