Schreier–Sims algorithm: Difference between revisions

Revision as of 04:41, 10 April 2017

Revision as of 04:47, 10 April 2017

Line 44:

void Group::Extend( const Permutation& generator, uint* base )

{

return; // Reject the generator! This is the major optimization of Schreier-Sims. Weed out redundant Schreier generators.

// Sift the given generator to determine whether or not it is redundant.

if( IsMember( generator ) )

return;

return; // Reject the generator! This is the major optimization of Schreier-Sims.

// Our group just got bigger, but the stabilizer chain rooted at our subgroup is still the same.

Line 83:

Notable details left out here include the growing of the orbit tree and the calculation of each new Schreier generator. In place of the orbit tree, a [[Schreier vector]] can be used, but the idea is essentially the same. The tree is rooted at the identity element, which fixes the point stabilized by the subgroup. Each node of the tree can represent a permutation that, when combined with all permutations in the path from the root to it, takes that point to some new point not visited by any other node of the tree. By the [[orbit-stabilizer theorem]], these form a [[transversal]] of the subgroup of our group that stabilizes the point whose entire orbit is maintained by the tree. Calculating a Schreier generator is a simple matter of applying [[Schreier's subgroup lemma]].

Another detail left out is the membership test. This is a simple matter of siftingfinding the givencoset permutationthat down the chain. The trivial group is reached in this process if and only ifcontains the given permutation is a member of the group. ToA siftlinear asearch permutation,is startusually byfine findingas the cosetsubgroup that itindex is in. Ifusually not found, it's not a member. Otherwise, multiply by the inverse of the coset's representative to get a permutation in the subgroup and recurse until we've hit the bottom of the chainhigh.

==References==