40.11 Backtrack

Pr must be a one-argument function that returns true or false for elements of G and the subset of elements of G that fulfill Pr must be a subgroup. (If the latter is not true the result of this operation is unpredictable!) This command computes this subgroup. The optional argument L must be a subgroup of the set of all elements fulfilling Pr and can be given if known in order to speed up the calculation.

ElementProperty returns an element p of the permutation group G such that the one-argument function Pr returns true for p. It returns fail if no such element exists in G. The optional arguments L and R are subgroups of G such that the property Pr has the same value for all elements in the cosets Lg and gR, respectively.

A typical example of using the optional subgroups L and R is the conjugacy test for elements a and b for which one can set L : = C_G(a ) and R : = C_G(b ).

gap> propfun:= el -> (1,2,3)^el in [ (1,2,3), (1,3,2) ];;
gap> SubgroupProperty( g, propfun, Subgroup( g, [ (1,2,3) ] ) );
Group( [ (1,2,3), (2,3) ] )
gap> ElementProperty( g, el -> Order( el ) = 2 );
(2,4)

Chapter Permutations describes special operations to construct permutations in the symmetric group without using backtrack constructions.

Backtrack routines are also called by the methods for permutation groups that compute centralizers, normalizers, intersections, conjugating elements as well as stabilizers for the operations of a permutation group OnPoints, OnSets, OnTuples and OnSetSets. Some of these methods use more specific refinements than SubgroupProperty or ElementProperty. For the definition of refinements, and how one can define refinements, see Section The General Backtrack Algorithm with Ordered Partitions in ``Extending GAP''.

The 2-closure of a transitive permutation group G on n points is the largest subgroup of S_n which has the same orbits on sets of ordered pairs of points as the group G has. It also can be interpreted as the stabilizer of the orbital graphs of G.

gap> TwoClosure(Group((1,2,3),(2,3,4)));
Sym([ 1 .. 4 ])

is the info class for the partition backtrack routines.

[Top] [Previous] [Up] [Index]