Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

4 Constraints
 4.1 The concept of constraints in BacktrackKit
 4.2 The Constraints record
 4.3 Constraints via the Constraint record

4 Constraints

4.1 The concept of constraints in BacktrackKit

Fundamentally, the partition backtrack algorithm (and its generalisations) performs a search for permutations that satisfy a collection of constraints.

A constraint is a true/false mathematical property of permutations, such that if the set of permutations satisfying the property is nonempty, then that set must be a (possibly infinite) permutation group, or a coset thereof. Furthermore, it must be ‘easy’ to test whether any given permutation satisfies the property.

For example:

are all examples of constraints. On the other hand:

do not qualify, unless generating sets for the socle and the largest maximal subgroups of G are already known, and there is a unique such maximal subgroup (in which case these properties become instances of the constraint “is a member of the group defined by the generating set...”).

The term ‘constraint’ comes from the computer science field of constraint satisfaction problems, constraint programming, and constraint solvers, with which backtrack search algorithms are very closely linked.

BacktrackKit provides a number of built-in constraints. Constraints, and the functions to create them, are contained in the Constraint (4.2-1) record. The members of this record are documented individually in Section 4.3.

To use BacktrackKit, it is necessary to (at least implicitly) specify constraints that, in conjunction, define the permutation(s) that you wish to find. This is documented in Chapter 2. A constraint will typically be converted into one or more refiners by that the time that a search takes place. Refiners are introduced in Chapter 5. We do not yet explicitly document the conversion of BacktrackKit constraints into refiners; the conversion may change in future versions of BacktrackKit.

4.2 The Constraints record

4.2-1 Constraint
‣ Constraint( global variable )

Constraint is a record that contains functions for producing all of the constraints that BacktrackKit provides.

The members of Constraint are documented individually in Section 4.3.

The members whose names differ only by their “-ise” and “-ize” endings are synonyms, included to accommodate different spellings in English.

gap> LoadPackage("BacktrackKit", false);;
gap> Set(RecNames(Constraint));
[ "Centralise", "Centralize", "Conjugate", "InCoset", "InGroup", 
  "InLeftCoset", "InRightCoset", "IsEven", "IsOdd", "IsTrivial", 
  "LargestMovedPoint", "MovedPoints", "None", "Normalise", "Normalize", 
  "Nothing", "Stabilise", "Stabilize", "Transport" ]

4.3 Constraints via the Constraint record

In this section, we individually document the functions of the Constraint (4.2-1) record, which can be used to create the built-in constraints provided by BacktrackKit.

Many of these constraints come in pairs, with a “group” version, and a corresponding “coset” version. These relationships are given in the following table.

Group version Coset version
Constraint.InGroup (4.3-1) Constraint.InCoset (4.3-2)

Constraint.InRightCoset (4.3-3)

Constraint.InLeftCoset (4.3-4)

Constraint.Stabilise (4.3-6) Constraint.Transport (4.3-5)
Constraint.Normalise (4.3-7) Constraint.Conjugate (4.3-9)
Constraint.Centralise (4.3-8) Constraint.Conjugate (4.3-9)
Constraint.MovedPoints (4.3-10) N/A
Constraint.LargestMovedPoint (4.3-11) N/A
Constraint.IsEven (4.3-12) Constraint.IsOdd (4.3-13)
Constraint.IsTrivial (4.3-14) N/A
N/A Constraint.None (4.3-15)

 


4.3-1 Constraint.InGroup
‣ Constraint.InGroup( G )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations in the permutation group G.

gap> con1 := Constraint.InGroup(DihedralGroup(IsPermGroup, 8));
<constraint: in group: Group( [ (1,2,3,4), (2,4) ] )>
gap> con2 := Constraint.InGroup(AlternatingGroup(4));
<constraint: in group: AlternatingGroup( [ 1 .. 4 ] )>

4.3-2 Constraint.InCoset
‣ Constraint.InCoset( U )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations in the GAP right coset object U.

See also Constraint.InLeftCoset (4.3-4) and Constraint.InRightCoset (4.3-3), which allow a coset to be specifed by a subgroup and a representative element.

gap> U := PSL(2,5) * (3,4,6);
RightCoset(Group([ (3,5)(4,6), (1,2,5)(3,4,6) ]),(3,4,6))
gap> Constraint.InCoset(U);
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-3 Constraint.InRightCoset
‣ Constraint.InRightCoset( G, x )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations in the right coset of the group G determined by the permutation x.

See also Constraint.InLeftCoset (4.3-4) for the left-hand version, and Constraint.InCoset (4.3-2) for a GAP right coset object.

gap> Constraint.InRightCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-4 Constraint.InLeftCoset
‣ Constraint.InLeftCoset( G, x )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations in the left coset of the group G determined by the permutation x.

See also Constraint.InRightCoset (4.3-3) for the right-hand version, and Constraint.InCoset (4.3-2) for a GAP right coset object.

gap> Constraint.InLeftCoset(PSL(2,5), (3,4,6));
<constraint: in coset: Group( [ (3,6)(4,5), (1,2,5)(3,4,6) ] ) * (3,4,6)

4.3-5 Constraint.Transport
‣ Constraint.Transport( object1, object2[, action] )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations that map object1 to object2 under the given group action, i.e. all permutations g such that action(object1,g)=object2. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Transport are given in the table below.

gap> setofsets1 := [[1, 3, 6], [2, 3, 6]];;
gap> setofsets2 := [[1, 2, 5], [1, 5, 7]];;
gap> con := Constraint.Transport(setofsets1, setofsets2, OnSetsSets);
<constraint: transporter of [ [ 1, 3, 6 ], [ 2, 3, 6 ] ] to [ [ 1, 2, 5 ], [ 1\
, 5, 7 ] ] under OnSetsSets>

4.3-6 Constraint.Stabilise
‣ Constraint.Stabilise( object[, action] )( function )
‣ Constraint.Stabilize( object[, action] )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations that fix object under the given group action, i.e. all permutations g such that action(object,g)=object. Note that the set of such permutations may be infinite.

The combinations of objects and actions that are supported by Constraint.Stabilise are given in the table below.

gap> con1 := Constraint.Stabilise(CycleDigraph(6), OnDigraphs);
<constraint: stabiliser of CycleDigraph(6) under OnDigraphs>
gap> con2 := Constraint.Stabilise([2,4,6], OnSets);
<constraint: stabiliser of [ 2, 4, 6 ] under OnSets>

4.3-7 Constraint.Normalise
‣ Constraint.Normalise( G )( function )
‣ Constraint.Normalize( G )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations that normalise the permutation group G, i.e. that preserve G under conjugation.

Note that the set of such permutations is infinite.

gap> Constraint.Normalise(PSL(2,5));
<constraint: normalise Group( [ (3,5)(4,6), (1,2,5)(3,4,6) ] )>

4.3-8 Constraint.Centralise
‣ Constraint.Centralise( G )( function )
‣ Constraint.Centralize( G )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations that commute with G, if G is a permutation, or that commute with every element of G, if G is a permutation group.

Note that the set of such permutations is infinite.

gap> D12 := DihedralGroup(IsPermGroup, 12);;
gap> Constraint.Centralise(D12);
<constraint: centralise group Group( [ (1,2,3,4,5,6), (2,6)(3,5) ] )>
gap> x := (1,6)(2,5)(3,4);;
gap> Constraint.Centralise(x);
<constraint: centralise perm (1,6)(2,5)(3,4)>

4.3-9 Constraint.Conjugate
‣ Constraint.Conjugate( x, y )( function )

Returns: A constraint

This constraint is satisfied by precisely those permutations that conjugate x to y, where x and y are either both permutations, or both permutation groups.

Note that the set of such permutations may be infinite.

This constraint is equivalent to Constraint.Transport(x,y,OnPoints).

gap> Constraint.Conjugate((3,4)(2,5,1), (1,2,3)(4,5));
<constraint: conjugate perm (1,2,5)(3,4) to (1,2,3)(4,5)>

4.3-10 Constraint.MovedPoints
‣ Constraint.MovedPoints( pointlist )( function )

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(pointlist)). See Constraint.InGroup (4.3-1).

gap> con1 := Constraint.MovedPoints([1..5]);
<constraint: moved points: [ 1 .. 5 ]>
gap> con2 := Constraint.MovedPoints([2,6,4,5]);
<constraint: moved points: [ 2, 6, 4, 5 ]>

4.3-11 Constraint.LargestMovedPoint
‣ Constraint.LargestMovedPoint( point )( function )

Returns: A constraint

This constraint is a shorthand for Constraint.InGroup(SymmetricGroup(point)), where point is a nonnegative integer. See Constraint.InGroup (4.3-1).

gap> con := Constraint.LargestMovedPoint(5);
<constraint: largest moved point: 5>

4.3-12 Constraint.IsEven
‣ Constraint.IsEven( global variable )

This constraint is satisfied by the even permutations, i.e. those permutations with sign 1. In other words, this constraint restricts a search to some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsEven;
<constraint: is even permutation>
gap> Representative(Constraint.IsEven);
()

4.3-13 Constraint.IsOdd
‣ Constraint.IsOdd( global variable )

This constraint is satisfied by the odd permutations, i.e. those permutations with sign -1. In other words, this constraint restricts a search to the unique coset of some alternating group.

Note that the set of such permutations is infinite.

gap> Constraint.IsOdd;
<constraint: is odd permutation>
gap> Representative(Constraint.IsOdd);
(1,2)

4.3-14 Constraint.IsTrivial
‣ Constraint.IsTrivial( global variable )

This constraint is satisfied by the identity permutation and no others.

This constraint will typically not be required by the user.

gap> Constraint.IsTrivial;
<trivial constraint: is identity permutation>
gap> Representative(Constraint.IsTrivial);
()

4.3-15 Constraint.None
‣ Constraint.None( global variable )

This constraint is satisfied by no permutations.

This constraint will typically not be required by the user.

gap> Constraint.None;
<empty constraint: satisfied by no permutations>
gap> Representative(Constraint.None);
fail
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 Bib Ind

generated by GAPDoc2HTML