8.16 Orbits

Orbits( G, D )
Orbits( G, D, operation )

Orbits returns the orbits of the group G on the domain D, which must be a list of points of arbitrary type, as a set of lists of points. See Orbit for the definition of orbits.

It is allowed that D is a proper subset of a domain, i.e., that D is not invariant under the operation of G. In this case D is silently replaced by the smallest superset of D which is invariant.

The first point in each orbit is the smallest point, the other points of each orbit are ordered in the standard order defined for orbits (see Orbit). Because Orbits returns a set of orbits, i.e., a sorted list, and because those orbits are compared lexicographically, and because the first point in each orbit is the smallest point in that orbit, the list returned by Orbits is in fact sorted with respect to the smallest points the orbits.

Orbits accepts a function operation of two arguments d and g as optional third argument, which specifies how the elements of G operate (see Other Operations).

    gap> g := Group( (1,2,3)(6,7), (3,4,5)(7,8) );;
    gap> Orbits( g, [1..8] );
    [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8 ] ]
    gap> Orbits( g, [1,6] );
    [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8 ] ]    # the domain is not invariant
    gap> sets := Combinations( [1..8], 3 );; Length( sets );
    56    # a list of all three element subsets of '[1..8]'
    gap> Orbits( g, sets, OnSets );
    [ [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 2, 3, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ],
          [ 2, 4, 5 ], [ 2, 3, 5 ], [ 1, 4, 5 ], [ 3, 4, 5 ], [ 1, 3, 5 ]
         ],
      [ [ 1, 2, 6 ], [ 2, 3, 7 ], [ 1, 3, 6 ], [ 2, 4, 8 ], [ 1, 2, 7 ],
          [ 1, 4, 6 ], [ 3, 4, 8 ], [ 2, 5, 7 ], [ 2, 3, 6 ],
          [ 1, 2, 8 ], [ 2, 4, 7 ], [ 1, 5, 6 ], [ 1, 4, 8 ],
          [ 4, 5, 7 ], [ 3, 5, 6 ], [ 2, 3, 8 ], [ 1, 3, 7 ],
          [ 2, 4, 6 ], [ 3, 4, 6 ], [ 2, 5, 8 ], [ 1, 5, 7 ],
          [ 4, 5, 6 ], [ 3, 5, 8 ], [ 1, 3, 8 ], [ 3, 4, 7 ],
          [ 2, 5, 6 ], [ 1, 4, 7 ], [ 1, 5, 8 ], [ 4, 5, 8 ], [ 3, 5, 7 ]
         ],
      [ [ 1, 6, 7 ], [ 2, 6, 7 ], [ 1, 6, 8 ], [ 3, 6, 7 ], [ 2, 6, 8 ],
          [ 2, 7, 8 ], [ 4, 6, 8 ], [ 3, 7, 8 ], [ 3, 6, 8 ],
          [ 4, 7, 8 ], [ 5, 6, 7 ], [ 1, 7, 8 ], [ 4, 6, 7 ],
          [ 5, 7, 8 ], [ 5, 6, 8 ] ], [ [ 6, 7, 8 ] ] ] 

Orbits calls
G.operations.Orbits( G, D, operation )
and returns the value. Note that the third argument is not optional for functions called this way.

The default function called this way is GroupOps.Orbits, which takes an element from D, computes its orbit, removes all points in the orbit from D, and repeats this until D has been emptied. Special categories of groups overlay this default function with more efficient functions.

Previous Up Top Next
Index