SchreierSims

template<size_t N, typename TPointType = typename SmallestInteger<N>::type, typename TElementType = LeastPerm<N>, typename TTraits = SchreierSimsTraits<N, TPointType, TElementType>>
class SchreierSims : private libsemigroups::detail::BruidhinnTraits<LeastPerm<N>>

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

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

Template Parameters
  • N – the largest point not fixed by the permutations in the permutation group to be represented by this.

  • TPointType – the type of the points acted on (default: the member type of SmallestInteger with template parameter N).

  • TElementType – the type of the group elements acting on TPointType (default: the member type of LeastPerm with template parameter N).

  • TTraits – the type of traits object (default: SchreierSimsTraits with template parameters N, TPointType, and TElementType).

Member types

domain_type

Type of the object containing all points acted on.

element_type

Type of the elements.

index_type

Type of indices.

point_type

Type of the points acted on.

Adapter types

Action

Alias for TTraits::Action.

Degree

Adapter for the degree of an element.

EqualTo

Adapter for testing equality.

Inverse

Adapter for the inverse of an element.

One

Adapter for the identity element of the given type.

Product

Adapter for the product of two elements.

Swap

Adapter for swapping.

Constructors

SchreierSims()

Default constructor.

SchreierSims(SchreierSims &&) = default

Default move constructor.

Deleted constructors

SchreierSims(SchreierSims const &) = delete

Deleted.

operator=(SchreierSims &&) = delete

Deleted.

operator=(SchreierSims const &) = delete

Deleted.

Initialisation

add_base_point(point_type)

Add a base point to the stabiliser chain.

add_generator(const_element_reference)

Add a generator.

clear()

Reset to the trivial group.

Running

run()

Run the Schreier-Sims algorithm.

Attributes

base(index_type) const

Get a base point.

base_size() const noexcept

Get the size of the current base.

empty()

Check if any generators have been added so far.

finished() const

Check if the stabiliser chain is fully enumerated.

generator(index_type) const

Get a generator.

identity() const

Returns a const reference to the identity.

inversal_element(index_type, point_type)

Get an inversal element.

number_of_generators() const noexcept

The number of generators.

number_of_strong_generators(index_type) const

The number of strong generators at a given depth.

orbits_lookup(index_type, point_type)

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

size()

Returns the size of the group represented by this.

strong_generator(index_type,index_type) const

Get a strong generator.

transversal_element(index_type, point_type)

Get a transversal element.

Membership

contains(const_element_reference)

Test membership of an element.

sift(const_element_reference)

Sift an element through the stabiliser chain.