SchreierSimsAlgorithm

SchreierSimsAlgorithm

A high-performance engine for computing the Base and Strong Generating Set (BSGS) of a permutation group. This implementation is designed for the group-engine ecosystem, leveraging the global PermutationRepository for efficient memory management.

Constructor

new SchreierSimsAlgorithm(initialBaseopt)

Description:

  • Constructs a new Schreier-Sims Algorithm instance. The instance can be initialized with an optional initialBase to prioritize certain points in the base.

Source:
Parameters:
Name Type Attributes Default Description
initialBase Array.<number> <optional>
 []

An optional array of points to form the initial base. These points will be stabilized first.

Classes

SchreierSimsAlgorithm

Members

(protected) base :Array.<number>

Description:

  • The Base sequence B = [b_1, b_2, ..., b_k]. This is the sequence of points that define the stabilizer chain.

Source:

The Base sequence B = [b_1, b_2, ..., b_k]. This is the sequence of points that define the stabilizer chain.

Type:
  • Array.<number>

degree

Description:

  • Gets the current degree (number of points) on which the permutations act. This value is dynamically managed by the underlying PermutationRepository.

Source:

Gets the current degree (number of points) on which the permutations act. This value is dynamically managed by the underlying PermutationRepository.

(protected) generators :Array.<Array.<number>>

Description:

  • Strong Generators for each level of the stabilizer chain. generators[i] is an array of permutation IDs that, along with the elements stabilizing base[i], generate the stabilizer G^(i) (the subgroup fixing base[0], ..., base[i-1]).

Source:

Strong Generators for each level of the stabilizer chain. generators[i] is an array of permutation IDs that, along with the elements stabilizing base[i], generate the stabilizer G^(i) (the subgroup fixing base[0], ..., base[i-1]).

Type:
  • Array.<Array.<number>>

order

Description:

  • Calculates the exact order (size) of the group represented by the BSGS. The order is computed as the product of the sizes of the orbits (transversals) at each level of the base.

Source:

Calculates the exact order (size) of the group represented by the BSGS. The order is computed as the product of the sizes of the orbits (transversals) at each level of the base.

(protected) transversals :Array.<Map>

Description:

  • Transversals (Orbit Lookup Tables) for each level of the stabilizer chain. transversals[i] stores the orbit of base[i] under the group G^(i) (the stabilizer of base[0], ..., base[i-1]). Each map: Key: Point p in orbit, Value: Permutation ID u such that u(base[i]) = p.

Source:

Transversals (Orbit Lookup Tables) for each level of the stabilizer chain. transversals[i] stores the orbit of base[i] under the group G^(i) (the stabilizer of base[0], ..., base[i-1]). Each map: Key: Point p in orbit, Value: Permutation ID u such that u(base[i]) = p.

Type:
  • Array.<Map>

Methods

contains(perm) → {boolean}

Description:

  • Checks if a given permutation is an element of the group represented by this BSGS. The permutation is "sifted" through the stabilizer chain. If the process reduces the permutation to the identity element, it is in the group.

Source:
Parameters:
Name Type Description
perm number | Int32Array | Array.<number>

The permutation to check, either as an ID or a raw array.
Returns:

True if the permutation belongs to the group, false otherwise.

Type
boolean

getGeneratorsAsPermutationSet() → {PermutationSet}

Description:

  • Get generators as PermutationSet

Source:
Returns:
Type
PermutationSet

getStabilizer(point) → {PermutationSet}

Description:

  • Computes the stabilizer subgroup G_p of a specific point p. G_p is defined as the set of all permutations g in the group G such that g(p) = p.

Source:
Parameters:
Name Type Description
point number

The point (0-based index) for which to compute the stabilizer.
Returns:

A PermutationSet containing the generators of the stabilizer subgroup.

Type
PermutationSet

isTransitive(domainSize) → {boolean}

Description:

  • Checks if the group acts transitively on a specified domain. A group is transitive if, for any two points x and y in the domain, there exists a group element g such that g(x) = y. This implementation checks if the orbit of the first base point (base[0]) under the full group covers the entire domainSize.

Source:
Parameters:
Name Type Description
domainSize number

The size of the domain (e.g., globalDegree) to check for transitivity.
Returns:

True if the group is transitive on the given domain, false otherwise.

Type
boolean

siftAndInsert(gId)

Description:

  • The main incremental construction method for the BSGS. It sifts a given permutation gId. If gId is not already in the group generated by the current BSGS, the algorithm updates the stabilizer chain (base, transversals, generators) to include gId, ensuring that the BSGS correctly represents the expanded group.

Source:
Parameters:
Name Type Description
gId number

The permutation ID to be inserted into the BSGS.

toString() → {string}

Description:

  • Returns a string representation.

Source:
Returns:

A result string.

Type
string

(static) compute(groupSet, initialBaseopt) → {SchreierSimsAlgorithm}

Description:

  • Factory method: Computes the Base and Strong Generating Set (BSGS) for a given set of generators.

Source:
Parameters:
Name Type Attributes Default Description
groupSet PermutationSet | Array.<number>

The set of permutations that generate the group.
initialBase Array.<number> <optional>
 []

An optional array of points to serve as a prefix for the base.
Returns:

A new SchreierSimsAlgorithm instance with the computed BSGS.

Type
SchreierSimsAlgorithm