The SchreierSims class

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

Example:

>>> from libsemigroups_pybind11 import SchreierSims, Perm
>>> p1 = Perm([1, 0, 2, 3, 4] + list(range(5, 255)))
>>> p2 = Perm([1, 2, 3, 4, 0] + list(range(5, 255)))
>>> S = SchreierSims([p1, p2])
>>> S.size()
120

Contents

`SchreierSims`	This class implements a deterministic version of the Schreier-Sims algorithm acting on a relatively small number of points (< 1000).
`SchreierSims.add_base_point`(…)	Add a base point to the stabiliser chain.
`SchreierSims.add_generator`(…)	Add a generator.
`SchreierSims.base`(…)	Get a base point.
`SchreierSims.base_size`(…)	Get the size of the current base.
`SchreierSims.contains`(…)	Test membership of an element.
`SchreierSims.copy`(…)	Copy a `SchreierSims`.
`SchreierSims.current_size`(…)	Returns the size of the group represented by this, without running the algorithm.
`SchreierSims.currently_contains`(…)	Test membership of an element without running.
`SchreierSims.empty`(…)	Check if any generators have been added so far.
`SchreierSims.finished`(…)	Check if the stabiliser chain is fully enumerated.
`SchreierSims.generator`(…)	Get a generator.
`SchreierSims.init`(…)	Reset to the trivial group.
`SchreierSims.inverse_transversal_element`(…)	Get an inverse of a transversal element.
`SchreierSims.number_of_generators`(…)	The number of generators.
`SchreierSims.number_of_strong_generators`(…)	The number of strong generators at a given depth.
`SchreierSims.one`(…)	Returns the identity permutation.
`SchreierSims.orbit_lookup`(…)	Check if a point is in the orbit of a basepoint.
`SchreierSims.run`(…)	Run the Schreier-Sims algorithm.
`SchreierSims.sift`(…)	Sift an element through the stabiliser chain.
`SchreierSims.sift_inplace`(…)	Sift an element through the stabiliser chain in-place.
`SchreierSims.size`(…)	Returns the size of the group represented by self.
`SchreierSims.strong_generator`(…)	Get a strong generator.
`SchreierSims.transversal_element`(…)	Get an transversal element.

Full API

class SchreierSims

__init__(self: SchreierSims, gens: list[Element]) → None

Construct from a list of generators.

This function constructs a SchreierSims instance with generators in the list gens.

Parameters:: gens (list[Element]) – the list of generators.
Raises:: LibsemigroupsError – if the generators do not have degree equal to \(255\) or \(511\), or the number of generators exceeds the maximum capacity.

add_base_point(self: SchreierSims, pt: int) → SchreierSims

Add a base point to the stabiliser chain.

Parameters:

pt (int) – the base point to add.

Returns:

self.

Return type:

SchreierSims

Raises:

LibsemigroupsError – if pt is out of range.
LibsemigroupsError – if pt is already a base point.
LibsemigroupsError – if finished() returns True.

Complexity:

Linear in the current number of base points.

add_generator(self: SchreierSims, x: Element) → bool

Add a generator.

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 Schreier-Sims object.

Parameters:: x (Element) – the generator to add.
Returns:: True if x is added as a generator and False if it is not.
Return type:: bool
Raises:: LibsemigroupsError – if the degree of x is not equal to \(255\) or \(511\), or if self already contains the maximum number of elements.
Complexity:: Constant

base(self: SchreierSims, index: int) → int

Get a base point.

This function gets the base point with a given index.

Parameters:: index (int) – the index of the base point.
Returns:: The base point with index index.
Return type:: int
Raises:: LibsemigroupsError – if index is out of range.
Complexity:: Constant.

base_size(self: SchreierSims) → int

Get the size of the current base.

Returns:: The base size.
Return type:: int
Complexity:: Constant.

contains(self: SchreierSims, x: Element) → bool

Test membership of an element.

Parameters:: x (Element) – the possible element.
Returns:: True if element is a contained in the SchreierSims instance, and False otherwise.
Return type:: bool

copy(self: SchreierSims) → SchreierSims

Copy a SchreierSims.

Returns:: A copy.
Return type:: SchreierSims

current_size(self: SchreierSims) → int

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

Returns:: the size of the group.
Return type:: int

currently_contains(self: SchreierSims, x: Element) → bool

Test membership of an element without running.

This function tests the membership of an element without running the algorithm.

Parameters:: x (Element) – the possible element.
Returns:: True if x is a contained in the SchreierSims instance, and False otherwise.
Return type:: bool

empty(self: SchreierSims) → bool

Check if any generators have been added so far.

Returns:: True if number_of_generators() == 0 and False otherwise.
Return type:: bool
Complexity:: Constant.

finished(self: SchreierSims) → bool

Check if the stabiliser chain is fully enumerated.

Returns:: True if the stabiliser chain is fully enumerated and False otherwise.
Return type:: bool
Complexity:: Constant.

generator(self: SchreierSims, index: int) → Element

Get a generator.

This function returns the generator with a given index.

Parameters:: index (int) – the index of the generator to return.
Returns:: The generator with index index.
Return type:: Element
Raises:: LibsemigroupsError – if the index is out of bounds.
Complexity:: Constant.

init(self: SchreierSims) → SchreierSims

Reset to the trivial group.

This function removes all generators, and orbits, and resets self so that it represents the trivial group, as if self had been newly constructed.

Returns:: self.
Return type:: SchreierSims
Complexity:: Constant.

inverse_transversal_element(self: SchreierSims, depth: int, pt: int) → Element

Get an inverse of a transversal element.

This function returns the transversal element at depth depth which sends pt to the basepoint.

Parameters:

depth (int) – the depth.
pt (int) – the point to map to the base point under the inverse transversal element.

Returns:

the inverse transversal element.

Return type:

Element

Raises:

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

Complexity:

Constant.

number_of_generators(self: SchreierSims) → int

The number of generators.

This function returns the number of generators.

Returns:: The number of generators.
Return type:: int
Complexity:: Constant.

number_of_strong_generators(self: SchreierSims, depth: int) → int

The number of strong generators at a given depth.

This function returns the number of strong generators of the stabiliser chain at a given depth.

Parameters:: depth (int) – the depth.
Returns:: The number of strong generators.
Return type:: int
Raises:: LibsemigroupsError – if the depth is out of bounds.
Complexity:: Constant.

one(self: SchreierSims) → Element

Returns the identity permutation.

This function returns the identity permutation of the same degree as the permutations belonging to a SchreierSims object.

Returns:: The identity element.
Return type:: Element

orbit_lookup(self: SchreierSims, depth: int, pt: int) → bool

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

Parameters:

depth (int) – the depth.
pt (int) – the point.

Returns:

True if the point pt is in the orbit of the base point of self at depth depth, and False otherwise.

Return type:

bool

Raises:

LibsemigroupsError – if the depth*` is out of bounds or if *pt is out of bounds.

Complexity:

Constant.

run(self: SchreierSims) → None

Run the Schreier-Sims algorithm.

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 degree of the generators, \(|G|\) is the size of the group and \(|T|\) is the number of generators of the group.

sift(self: SchreierSims, x: Element) → Element

Sift an element through the stabiliser chain.

Parameters:: x (Element) – A group element.
Returns:: A sifted element.
Return type:: Element
Raises:: LibsemigroupsError – if the degree of x is not equal to the degree of the generators.

sift_inplace(self: SchreierSims, x: Element) → None

Sift an element through the stabiliser chain in-place.

Parameters:: x (Element) – a group element.
Raises:: LibsemigroupsError – if the degree of x is not equal to the degree of the generators.

size(self: SchreierSims) → int

Returns the size of the group represented by self.

Returns:: the size of the group.
Return type:: int

strong_generator(self: SchreierSims, depth: int, index: int) → Element

Get a strong generator.

This function returns the generator with a given depth and index.

Parameters:

depth (int) – the depth.
index (int) – the index of the generator to return.

Returns:

The strong generator of at depth depth and with index index.

Return type:

Element

Raises:

LibsemigroupsError – if the depth is out of bounds.
LibsemigroupsError – if the index is out of bounds.

Complexity:

Constant.

transversal_element(self: SchreierSims, depth: int, pt: int) → Element

Get an transversal element.

This function returns the transversal element at depth depth which sends the corresponding basepoint to the point pt.

Parameters:

depth (int) – the depth.
pt (int) – the image of the base point under the traversal.

Returns:

The transversal element.

Return type:

Element

Raises:

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

Complexity:

Constant.