3 Basic orbit enumeration
  
  This package contains a new implementation of the standard orbit enumeration
  algorithm. The design principles for this implementation have been:
  
  --    Allow partial orbit enumeration and later continuation.
  
  --    Consequently use hashing techniques.
  
  --    Implement stabiliser calculation and Schreier transversals on demand.
  
  --    Allow for searching in orbits during orbit enumeration.
  
  Some  of  these  design  principles  made  it  necessary  to change the user
  interface in comparison to the standard GAP one.
  
  
  3.1 Enumerating orbits
  
  The  enumeration  of  an  orbit works in at least two stages: First an orbit
  object  is created with all the necessary information to describe the orbit.
  Then  the actual enumeration is started. The latter stage can be repeated as
  many times as needed in the case that the orbit enumeration stopped for some
  reason  before the orbit was enumerated completely. See below for conditions
  under which this happens.
  
  For orbit object creation there is the following function:
  
  3.1-1 Orb
  
  > Orb( gens, point, op[, opt] ) ____________________________________function
  Returns:  An orbit object
  
  The  argument  gens  is either a GAP group object or a list of generators of
  the  group  acting,  point is a point in the orbit to be enumerated, op is a
  GAP  function describing the action of the generators on points in the usual
  way,  that  is, op(p,g) returns the result of the action of the element g on
  the point p.
  
  The  optional  argument  opt  is  a GAP record which can contain quite a few
  options  changing  the orbit enumeration. For a list of possible options see
  Subsection 3.1-4 at the end of this section.
  
  The  function  returns an "orbit" object that can later be used to enumerate
  (a  part  of)  the orbit of point under the action of the group generated by
  gens.
  
  If  gens  is  a  group  object, then its generators are taken as the list of
  generators  acting.  If  the  group object knows its size, then this size is
  used to speed up orbit and in particular stabiliser computations.
  
  The following operation actually starts the orbit enumeration:
  
  3.1-2 Enumerate
  
  > Enumerate( orb[, limit] ) _______________________________________operation
  Returns:  The orbit object orb
  
  orb  must  be  an orbit object created by Orb (3.1-1). The optional argument
  limit  must  be a positive integer meaning that the orbit enumeration should
  stop  if  limit  points  have  been  found,  regardless whether the orbit is
  complete  or  not. Note that the orbit enumeration can be continued by again
  calling the Enumerate operation. If the argument limit is omitted, the whole
  orbit is enumerated, unless other options lead to prior termination.
  
  To see whether an orbit is closed you can use the following filter:
  
  3.1-3 IsClosed
  
  > IsClosed( orb ) ____________________________________________________filter
  Returns:  true or false
  
  The result indicates, whether the orbit orb is already complete or not.
  
  Here is an example of an orbit enumeration:
  
  ---------------------------  Example  ----------------------------
    gap> g := GeneratorsOfGroup(MathieuGroup(24)); 
    [ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), 
      (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), 
      (1,24)(2,23)(3,12)(4,16)(5,18)(6,10)(7,20)(8,14)(9,21)(11,17)
      (13,22)(15,19) 
     ]
    gap> o := Orb(g,2,OnPoints);
    <open Int-orbit, 1 points>
    gap> Enumerate(o,20);
    <open Int-orbit, 21 points>
    gap> IsClosed(o);
    false
    gap> Enumerate(o);   
    <closed Int-orbit, 24 points>
    gap> IsClosed(o);    
    true
  ------------------------------------------------------------------
  
  The  orbit object o now behaves like an immutable dense list, the entries of
  which are the points in the orbit in the order as they were found during the
  orbit  enumeration  (note  that  this  is  not always true when one uses the
  function  AddGeneratorsToOrbit  (3.1-15)).  So you can ask the orbit for its
  length,  access entries, and ask, whether a given point lies in the orbit or
  not.  Due  to  the hashing techniques used such lookups are quite fast, they
  usually only use a constant time regardless of the length of the orbit!
  
  ---------------------------  Example  ----------------------------
    gap> Length(o);
    24
    gap> o[1];
    2
    gap> o[2];
    3
    gap> o{[3..5]};
    [ 23, 4, 17 ]
    gap> 17 in o;
    true
    gap> Position(o,17);
    5
  ------------------------------------------------------------------
  
  
  3.1-4 Options for orbits
  
  The optional fourth argument opt of the function Orb (3.1-1) is a GAP record
  and  its  components  change the behaviour of the orbit enumeration. In this
  subsection  we explain the use of the components of this options record. All
  components are themselves optional. For every component we also describe the
  possible values in the following list:
  
  eqfunc
        This  component  always  has  to  be given together with the component
        hashfunc.  If  both are given, they are used to set up a hash table to
        store  the  points in the orbit. You have to use this if the automatic
        mechanism  to  find  a  suitable  hash function does not work for your
        starting point in the orbit.
  
        Note  that  if  you  use  this  feature,  the  hash  table cannot grow
        automatically  any  more, unless you also use the components hfbig and
        hfdbig  as  well.  See  the  description  of  GrowHT  (4.3-5)  for  an
        explanation how to use this feature.
  
  genstoapply
        This is only used internally and is intentionally not documented.
  
  grpsizebound
        Possible  values  for this component are positive integers. By setting
        this value one can help the orbit enumeration to complete earlier. The
        given number must be an upper bound for the order of the group. If the
        exact group order is given and the stabiliser is calculated during the
        orbit enumeration (see component permgens), then the orbit enumeration
        can  stop  as soon as the orbit is found completely and the stabiliser
        is  complete,  which  is usually much earlier than after all generator
        are applied to all points in the orbit.
  
  hashfunc
        See component eqfunc.
  
  hashlen
        Possible  values  are positive integers. This component determines the
        initial  size  of the hash used for the orbit enumeration. The default
        value is 10000. If the hash table turns out not to be large enough, it
        is  automatically increased by a factor of two during the calculation.
        Although  this  process is quite fast it still improves performance to
        give a sensible hash size in advance.
  
  hfbig and hfdbig
        These  components  can  only  be  used  in  connection with eqfunc and
        hashfunc  and are otherwise ignored. There values are simply passed on
        to  the  hash  table created. The idea is to still be able to grow the
        hash table if need be. See Section 4.4 for more details.
  
  log
        If  this component is set to true then a log of the enumeration of the
        orbit  is  written  into  the components log, logind and logpos. Every
        time  a  new  point is found in the orbit enumeration, two numbers are
        appended  to  the log, first the number of the generator applied, then
        the  index, under which the new point is stored in the orbit. For each
        point  in the orbit, the start of the entries for that point in log is
        stored in logind and the end of those entries is marked by storing the
        number of the last generator producing a new point negated.
  
        The  purpose  of  a log is the following: With a log one can later add
        group  generators to the orbit and thus get a different Schreier tree,
        such  that  the  resulting  orbit enumeration is still a breadth first
        enumeration  using  the  new  generating  set!  This  is  desirable to
        decrease  the  depth  of the Schreier tree. The log helps to implement
        this  in  a  way, such that the old generators do not again have to be
        applied  to  all  the  points  in  the orbit. See AddGeneratorsToOrbit
        (3.1-15) for details.
  
        A log needs roughly 3 machine words per point in the orbit as memory.
  
  lookingfor
        This  component is used to search for something in the orbit. The idea
        is  that  the orbit enumeration is stopped when some condition is met.
        This  condition  can  be specified with a great flexibility. The first
        way is to store a list of points into orb.lookingfor. In that case the
        orbit enumeration stops, when a point is found that is in that list. A
        second possiblity is to store a hash table object into orb.lookingfor.
        Then  every  newly  found point in the orbit is looked up in that hash
        table and the orbit enumeration stops as soon as a point is found that
        is  also  in  the hash table. The third possibility is functional: You
        can store a GAP function into opt.lookingfor which is called for every
        newly  found point in the orbit. It gets both the orbit object and the
        point  as its two arguments. This function has to return false or true
        and in the latter case the orbit enumeration is stopped.
  
        Whenever  the  orbit enumeration is stopped the component found is set
        to the number of the found point in the orbit. Access this information
        using PositionOfFound(orb).
  
  matgens
        This is not yet implemented. It will allow for stabiliser computations
        in matrix groups.
  
  onlystab
        If  this  boolean flag is set to true then the orbit enumeration stops
        once  the stabiliser is completely determined. Note that this can only
        be   known,   if   a  bound  for  the  group  size  is  given  in  the
        opt.grpsizebound  option  and  when  more  than  half  of the orbit is
        already found, or when opt.stabsizebound is given.
  
  orbsizebound
        Possible  values  for  this component are positive integers. The given
        number must be an upper bound for the orbit length. Giving this number
        helps  the  orbit enumeration to stop earlier, when the orbit is found
        completely.
  
  permbase
        This  component  is  used  to tell the orbit enumerator that a certain
        list  of  points  is a base of the permutation representation given in
        the  opt.permgens  component.  This  information  is  often  available
        beforehand  and  can  drastically speed up the calculation of Schreier
        generators,  especially for the common case that they are trivial. The
        value is just a list of integers.
  
  permgens
        If  this  component  is set, it must be set to a list of permutations,
        that  represent  the  same  group as the generators used to define the
        orbit.  This  permutation representation is then used to calculate the
        stabiliser  of  the  starting  point.  After  the orbit enumeration is
        complete, you can call Stabilizer(orb) with orb being the orbit object
        and  get the stabiliser as a permutation group. The stabiliser is also
        stored  in  the  stab  component of the orbit object. Furthermore, the
        size  of  the  stabiliser  is  stored in the stabsize component of the
        orbit  object  and  the  component  stabwords  contains the stabiliser
        generators  as  words  in  the original group generators. Access these
        words  with  StabWords(orb). Here, a word is a list of integers, where
        positive  integers  are numbers of generators and a negative integer i
        indicates  the  inverse  of the generator with number -i. In this way,
        complete  information  about  the  stabiliser  can be derived from the
        orbit object.
  
  report
        Possible  values  are  non-negative  integers.  This  value asks for a
        status   report   whenever  the  orbit  enumeration  has  applied  all
        generators  to  opt.report points. A value of 0, which is the default,
        switches  off  this report. In each report, the total number of points
        already found are given.
  
  schreier
        This  boolean flag decides, whether a Schreier tree is stored together
        with  the  orbit.  A  Schreier  tree just stores for each point, which
        generator  was  applied  to  which other point in the orbit to get it.
        Thus,  having  the  Schreier  tree enables the usage of the operations
        TraceSchreierTreeForward  (3.1-11) and TraceSchreierTreeBack (3.1-12).
        A Schreier tree needs two additional machine words of memory per point
        in  the  orbit.  The  opt.schreier  flag  is  automatically set when a
        stabiliser  is  computed  during  orbit  enumeration  (see  components
        opt.permgens and opt.matgens).
  
  schreiergenaction
        The  value  of this component must be a function with 4 arguments: the
        orbit  object,  an  index  i,  an  integer  j, and an index pos. It is
        called,  whenever  during the orbit enumeration generator number j was
        applied  to  point  number i and the result was an already known point
        with   number  pos.  This  is  no  longer  done,  once  the  component
        stabcomplete is set to true, which happens when there is evidence that
        the stabiliser is already completely determined.
  
        This  component is used internally when the permgens component was set
        and the stabiliser is calculated.
  
  stab
        This component is used to tell the orbit enumerator that a subgroup of
        the  stabiliser  of  the  starting  point  is  already  known. Store a
        subgroup  of  the  group generated by the permutations in opt.permgens
        stabilising the starting point into this component.
  
  stabchainrandom
        This  value  can  be  a  positive  integer  between  1  and  1000.  If
        opt.permgens  is  given,  an  integer  value is used to set the random
        option  when calculating a stabiliser chain to compute the size of the
        group  generated  by  the  Schreier  generators.  Although  this  size
        computation  can  be speeded up considerably, the user should be aware
        that  for  values  smaller  than  1000  this  triggers  a  Monte Carlo
        algorithm  that  can  produce  wrong  results  with  a  certain  error
        probability. A verification of the obtained results is advisable. Note
        however,  that such computations can only err in one direction, namely
        underestimating the size of the group.
  
  stabsizebound
        Possible  values  for  this component are positive integers. The given
        number  must  be an upper bound for the size of the stabiliser. Giving
        this  number  helps  the  orbit enumeration to stop earlier, when also
        opt.orbsizebound or opt.grpsizebound are given or when opt.onlystab is
        set.
  
  storenumbers
        This  boolean  flag  decides,  whether  the positions of points in the
        orbit  are  stored in the hash. The memory requirement for this is one
        machine word (4 or 8 bytes depending on the architecture) per point in
        the orbit. If you just need the orbit itself this is not necessary. If
        you  however  want  to  find  the  position  of  a  point in the orbit
        efficiently  after  enumeration,  then you should switch this on. That
        is, the operation \in is always fast, but Position(orb, point) is only
        fast if opt.storenumbers was set to true or the orbit is "permutations
        acting on positive integers". In the latter case this flag is ignored.
  
  For some examples using these options see Chapter 10.
  
  
  3.1-5 Output components of orbits
  
  The  following  components are bound in an orbit object. There might be some
  more,  but  those are implementation specific and not guaranteed to be there
  in  future versions. Note that you have to access these components using the
  ".~"  dot  exclamation  mark notation and you should avoid using these if at
  all possible.
  
  depth and depthmarks
        If  the  orbit has either a Schreier tree or a log, then the component
        depth  holds  its  depth,  that  is  the  maximal  number of generator
        applications needed to reach any point in the orbit. The corresponding
        component  depthmarks is a list of indices, at position i it holds the
        index of the first point in the orbit in depth i in the Schreier tree.
  
  gens
        The list of group generators.
  
  ht
        If the orbit uses a hash table it is stored in this component.
  
  op
        The operation function.
  
  orbind
        If  generators  have  been  added to the orbit later then the order in
        which the points are actually stored in the orbit might not correspond
        to  a  breadth  first search. To cover this case, the component orbind
        contains  in  position  i  the index under which the i-th point in the
        breadth-first  search  using the new generating set is actually stored
        in the orbit.
  
  schreiergen and schreierpos
        If  a  Schreier  tree of the orbit was kept then both these components
        are lists containing integers. If point number i was found by applying
        generator number j to point number p then position i of schreiergen is
        j  and  position  i  of  schreierpos  is p. You can use the operations
        TraceSchreierTreeForward  (3.1-11)  and TraceSchreierTreeBack (3.1-12)
        to compute words in the generators using these two components.
  
  tab
        For  an  orbit  in  which  permutations  act on positive integers this
        component is bound to a list containing in position i the index in the
        orbit, where the number i is stored.
  
  The  following  operations  help  to  ask additional information about orbit
  objects:
  
  3.1-6 StabWords
  
  > StabWords( orb ) ________________________________________________operation
  Returns:  A list of words
  
  If  the  stabiliser  was  computed  during  the orbit enumeration, then this
  function returns the stabiliser generators found as words in the generators.
  A  word  is  a  sequence  of  integers,  where  positive  integers stand for
  generators and negative numbers for their inverses.
  
  3.1-7 PositionOfFound
  
  > PositionOfFound( orb ) __________________________________________operation
  Returns:  An integer
  
  If during the orbit enumeration the option lookingfor was used and the orbit
  enumerator  looked  for  something, then this operation returns the index in
  the orbit, where the something was found most recently.
  
  3.1-8 DepthOfSchreierTree
  
  > DepthOfSchreierTree( orb ) ______________________________________operation
  Returns:  An integer
  
  If  a  Schreier tree or a log was stored during orbit enumeration, then this
  operation returns the depth of the Schreier tree.
  
  We  present  a  few  more  operations one can do with orbit objects. One can
  express  the  action  of a given group element in the group generated by the
  generators given in the Orb command on this orbit as a permutation:
  
  3.1-9 ActionOnOrbit
  
  > ActionOnOrbit( orb, grpels ) ____________________________________operation
  Returns:  A permutation or fail
  
  orb  must  be  an orbit object and grpels a list of group elements acting on
  the  orbit.  This  operation  calculates  the action of grpels on orb as GAP
  permutations,  where the numbering of the points is in the same order as the
  points   have  been  found  in  the  orbit.  Note  that  this  operation  is
  particularly  fast if the orbit is an orbit of a permutation group acting on
  positive  integers  or  if  you  used  the  option storenumbers described in
  Subsection 3.1-4.
  
  3.1-10 OrbActionHomomorphism
  
  > OrbActionHomomorphism( g, orb ) _________________________________operation
  Returns:  An action homomorphism
  
  The  argument  g  must  be  a  group and orb an orbit on which g acts in the
  action  of  the  orbit  object. This operation returns a homomorphism into a
  permutation group acquired by taking the action of g on the orbit.
  
  3.1-11 TraceSchreierTreeForward
  
  > TraceSchreierTreeForward( orb, nr ) _____________________________operation
  Returns:  A word in the generators
  
  orb  must  be  an  orbit  object  with  a Schreier tree, that is, the option
  schreier  must have been set during creation, and nr must be the number of a
  point  in  the  orbit. This operation traces the Schreier tree and returns a
  word in the generators that maps the starting point to the point with number
  nr.  Here, a word is a list of integers, where positive integers are numbers
  of  generators  and  a  negative  integer  i  indicates  the  inverse of the
  generator with number -i.
  
  3.1-12 TraceSchreierTreeBack
  
  > TraceSchreierTreeBack( orb, nr ) ________________________________operation
  Returns:  A word in the generators
  
  orb  must  be  an  orbit  object  with  a Schreier tree, that is, the option
  schreier  must have been set during creation, and nr must be the number of a
  point  in  the  orbit. This operation traces the Schreier tree and returns a
  word  in  the  generators that maps the point with number nr to the starting
  point.  As above, a word is here a list of integers, where positive integers
  are  numbers of generators and a negative integer i indicates the inverse of
  the generator with number -i.
  
  3.1-13 ActWithWord
  
  > ActWithWord( gens, w, op, p ) ___________________________________operation
  Returns:  A point
  
  gens  must be a list of group generators, w a list of positive integers less
  than  or  equal  to the length of gens, op an action function and p a point.
  This  operation  computes the action of the word w in the generators gens on
  the point p and returns the result.
  
  3.1-14 EvaluateWord
  
  > EvaluateWord( gens, w ) _________________________________________operation
  Returns:  A group element
  
  gens  must be a list of group generators, w a list of positive integers less
  than  or equal to the length of gens. This operation evaluates the word w in
  the generators gens and returns the result.
  
  3.1-15 AddGeneratorsToOrbit
  
  > AddGeneratorsToOrbit( orb, l[, p] ) _____________________________operation
  Returns:  The orbit object orb
  
  orb  must  be  an  orbit object, l a list of new generators and, if given, p
  must  be a list of permutations of equal length. p must be given if and only
  if  the  component permgens was specified upon creation of the orbit object.
  The  new  generators  are  appended to the old list of generators. The orbit
  object  is  changed  such  that it then shows the outcome of a breadth-first
  orbit  enumeration  with  the new list of generators. Note that the order of
  the  points  already  enumerated  will not be changed. However, the Schreier
  tree changes, the component orbind is changed to indicate the order in which
  the  points  were  found in the breadth-first search with the new generators
  and the components depth and depthmarks are changed.
  
  Note  that all this is particularly efficient if the orbit has a log. If you
  add  generators  to  an orbit with log, the old generators do not have to be
  applied again to all points!
  
  Note  that  new  generators can actually enlarge an orbit if they generate a
  larger group than the old ones alone. Note also that when adding generators,
  the orbit is automatically enumerated completely
  
  3.1-16 MakeSchreierTreeShallow
  
  > MakeSchreierTreeShallow( orb[, d] ) _____________________________operation
  Returns:  The orbit object orb
  
  Uses  AddGeneratorsToOrbit  (3.1-15)  to add more generators to the orbit in
  order  to make the Schreier tree shallower. If d it is given, generators are
  added  until  the  depth  is  less  than  or  equal to d or until three more
  generators  did  not  reduce the depth any more. If d is not given, then the
  logarithm to base 2 of the orbit length is taken as a default value.
  
  3.1-17 FindSuborbits
  
  > FindSuborbits( orb, subgens[, nrsuborbits] ) ____________________operation
  Returns:  A record
  
  The  argument  orb  must  be  a  closed orbit object with a Schreier vector,
  subgens  a list of generators for a subgroup of the originally acting group.
  If given, nrsuborbits must be a lower limit for the number of suborbits.
  
  The  returned record describes the suborbit structure of orb with respect to
  the   group   generated   by   subgens   using   the  following  components:
  issuborbitrecord  is  bound to true, o is bound to orb, nrsuborbits is bound
  to  the  number  of  suborbits  and  reps  is  a  list of length nrsuborbits
  containing  the  index  in  the orbit of a representative for each suborbit.
  Likewise, words contains words in the original group generators of the orbit
  that map the starting point of the orbit to those representatives. lens is a
  list containing the lengths of the suborbits. The component suborbs is bound
  to  a  list  of  lists,  one for each suborbit containing the indices of the
  points  in  the orbit. The component suborbnr is a list with the same length
  as  the  orbit, containing in position i the number of the suborbit in which
  point i in the orbit is contained.
  
  Finally,   the   component  conjsuborbit  is  bound  to  a  list  of  length
  nrsuborbits,  containing  for  each suborbit the number the suborbit reached
  from  the  starting point by the inverse of the word used to reach the orbit
  representative.  This  latter information probably only makes sense when the
  subgroup  generated  by  subgens is contained in the point stabiliser of the
  starting  point  of  the orbit, because then this is the so-called conjugate
  suborbit of a suborbit.
  
  3.1-18 OrbitIntersectionMatrix
  
  > OrbitIntersectionMatrix( r, g ) _________________________________operation
  Returns:  An integer matrix
  
  The  argument  r  must  be  a  suborbit  record as returned by the operation
  FindSuborbits  (3.1-17) above, describing the suborbit structure of an orbit
  with  respect  to a subgroup. g must be an element of the acting group. If k
  is  the  number  of  suborbits and the suborbits are O_1, ..., O_k, then the
  matrix  returned  by this operation has the integer |O_i * g cap O_j| in its
  (i,j)-entry.