home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / permoper.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  43.8 KB  |  1,377 lines
  1. #############################################################################
  2. ##
  3. #A  permoper.g                  GAP library                  Martin Schoenert
  4. ##
  5. #A  @(#)$Id: permoper.g,v 3.24 1993/02/07 17:21:20 martin Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains the functions that mainly deal with the  operation  of
  10. ##  permutation groups.
  11. ##
  12. ##  Some of them fall back to functions from 'operatio.g', others  require  a
  13. ##  stabilizer chain computed in 'permgrp.g'.
  14. ##
  15. #H  $Log: permoper.g,v $
  16. #H  Revision 3.24  1993/02/07  17:21:20  martin
  17. #H  fixed operations on ranges
  18. #H
  19. #H  Revision 3.23  1992/10/13  16:02:44  martin
  20. #H  added '<G>.operationImages'
  21. #H
  22. #H  Revision 3.22  1992/06/03  16:29:42  martin
  23. #H  added 'MaximalBlocks'
  24. #H
  25. #H  Revision 3.21  1992/06/03  16:12:19  martin
  26. #H  improved 'PermGroupOps.Operation' for operation on disjoint sets of ints
  27. #H
  28. #H  Revision 3.20  1992/06/02  11:56:37  martin
  29. #H  improved the selection of random elements in 'BlocksNoSeed'
  30. #H
  31. #H  Revision 3.19  1992/06/01  19:11:16  martin
  32. #H  added a new method to compute block systems
  33. #H
  34. #H  Revision 3.18  1992/03/10  11:36:16  martin
  35. #H  added 'IsRegular' and 'IsSemiRegular'
  36. #H
  37. #H  Revision 3.17  1992/01/24  14:48:16  martin
  38. #H  renamed 'Representative' to 'RepresentativeOperation'
  39. #H
  40. #H  Revision 3.16  1991/12/12  09:19:59  martin
  41. #H  changed 'ONPOINTS' to 'OnPoints', etc
  42. #H
  43. #H  Revision 3.15  1991/11/28  09:41:59  martin
  44. #H  fixed 'OrbitLength' from thinking that 'Max(<orb1>) \< Max(<orb2>)'
  45. #H
  46. #H  Revision 3.14  1991/10/04  14:00:48  martin
  47. #H  fixed a trivial problem in 'Stabilizer'
  48. #H
  49. #H  Revision 3.13  1991/10/02  15:43:51  martin
  50. #H  fixed 'Stabilizer', the stabilizer of a subgroup is the normalizer
  51. #H
  52. #H  Revision 3.12  1991/10/02  15:42:21  martin
  53. #H  fixed a stupid bug in 'Representative'
  54. #H
  55. #H  Revision 3.11  1991/10/01  14:59:23  martin
  56. #H  changed stabchain, stabilizer are no subgroups
  57. #H
  58. #H  Revision 3.10  1991/09/28  12:17:50  martin
  59. #H  changed all functions to require the operation as argument
  60. #H
  61. #H  Revision 3.9  1991/09/27  13:34:55  martin
  62. #H  'Position' now returns 'false'
  63. #H
  64. #H  Revision 3.8  1991/09/27  09:12:56  martin
  65. #H  'Representative' now may return 'false'
  66. #H
  67. #H  Revision 3.7  1991/09/27  09:07:40  martin
  68. #H  made some minor name changes
  69. #H
  70. #H  Revision 3.6  1991/09/26  11:26:18  martin
  71. #H  added 'Representative'
  72. #H
  73. #H  Revision 3.5  1991/09/25  13:32:01  martin
  74. #H  added 'MovedPoints', ...
  75. #H
  76. #H  Revision 3.4  1991/09/25  13:26:00  martin
  77. #H  improved 'Stabilizer'
  78. #H
  79. #H  Revision 3.3  1991/09/23  15:49:31  martin
  80. #H  improved 'OrbitLength'
  81. #H
  82. #H  Revision 3.2  1991/09/23  15:47:09  martin
  83. #H  changed to use 'PermGroupOps'
  84. #H
  85. #H  Revision 3.1  1991/09/03  08:06:43  martin
  86. #H  fixed a small bug in 'OrbitsPermGroup'
  87. #H
  88. #H  Revision 3.0  1991/08/08  15:32:59  martin
  89. #H  initial revision under RCS
  90. #H
  91. ##
  92.  
  93. #############################################################################
  94. ##
  95. #F  InfoOperation1(...) . . .  information function for the operation package
  96. #F  InfoOperation2(...) . . .  information function for the operation package
  97. ##
  98. if not IsBound(InfoOperation1)  then InfoOperation1 := Ignore;  fi;
  99. if not IsBound(InfoOperation2)  then InfoOperation2 := Ignore;  fi;
  100.  
  101.  
  102. #############################################################################
  103. ##
  104. #F  PermGroupOps.IsSemiRegular(<G>,<D>) . . . . . test if a permutation group
  105. #F                                                       operates semiregular
  106. ##
  107. PermGroupOps.IsSemiRegular := function ( G, D, opr )
  108.     local   used,       #
  109.             perm,       #
  110.             orbs,       # orbits of <G> on <D>
  111.             gen,        # one of the generators of <G>
  112.             orb,        # orbit of '<D>[1]'
  113.             pnt,        # one point in the orbit
  114.             new,        # image of <pnt> under <gen>
  115.             img,        # image of '<prm>[<i>][<pnt>]' under <gen>
  116.             p, n,       # loop variables
  117.             i, l;       # loop variables
  118.  
  119.     # handle special case of standard operation on a list of integers
  120.     if opr = OnPoints  and ForAll( D, IsInt )  then
  121.  
  122.         # compute the orbits and check that they all have the same length
  123.         orbs := Orbits( G, D );
  124.         if Length( Set( List( orbs, Length ) ) ) <> 1  then
  125.             return false;
  126.         fi;
  127.  
  128.         # initialize the permutations that act like the generators
  129.         used := [];
  130.         perm := [];
  131.         for i  in [ 1 .. Length( G.generators ) ]  do
  132.             used[i] := [];
  133.             perm[i] := [];
  134.             for pnt  in orbs[1]  do
  135.                 used[i][pnt] := false;
  136.             od;
  137.             perm[i][ orbs[1][1] ] := orbs[1][1] ^ G.generators[i];
  138.             used[i][ orbs[1][1] ^ G.generators[i] ] := true;
  139.         od;
  140.  
  141.         # initialize the permutation that permutes the orbits
  142.         l := Length( G.generators ) + 1;
  143.         used[l] := [];
  144.         perm[l] := [];
  145.         for orb  in orbs  do
  146.             for pnt  in orb  do
  147.                 used[l][pnt] := false;
  148.             od;
  149.         od;
  150.         for i  in [ 1 .. Length(orbs)-1 ]  do
  151.             perm[l][orbs[i][1]] := orbs[i+1][1];
  152.             used[l][orbs[i+1][1]] := true;
  153.         od;
  154.         perm[l][orbs[Length(orbs)][1]] := orbs[1][1];
  155.         used[l][orbs[1][1]] := true;
  156.  
  157.         # compute the orbit of the first representative
  158.         orb := [ orbs[1][1] ];
  159.         for pnt  in orb  do
  160.             for gen  in G.generators  do
  161.  
  162.                 # if the image is new
  163.                 new := pnt ^ gen;
  164.                 if not new in orb  then
  165.  
  166.                     # add the new element to the orbit
  167.                     Add( orb, new );
  168.  
  169.                     # extend the permutations that act like the generators
  170.                     for i  in [ 1 .. Length( G.generators ) ]  do
  171.                         img := perm[i][pnt] ^ gen;
  172.                         if used[i][img]  then
  173.                             return false;
  174.                         else
  175.                             perm[i][new] := img;
  176.                             used[i][img] := true;
  177.                         fi;
  178.                     od;
  179.  
  180.                     # extend the permutation that permutates the orbits
  181.                     p := pnt;
  182.                     n := new;
  183.                     for i  in [ 1 .. Length( orbs ) ]  do
  184.                         img := perm[l][p] ^ gen;
  185.                         if used[l][img]  then
  186.                             return false;
  187.                         else
  188.                             perm[l][n] := img;
  189.                             used[l][img] := true;
  190.                         fi;
  191.                         p := perm[l][p];
  192.                         n := img;
  193.                     od;
  194.  
  195.                 fi;
  196.  
  197.             od;
  198.         od;
  199.  
  200.         # check that the permutations commute with the generators
  201.         for i  in [ 1 .. Length( G.generators ) ]  do
  202.             for gen  in G.generators  do
  203.                 for pnt  in orb  do
  204.                     if perm[i][pnt] ^ gen <> perm[i][pnt ^ gen]  then
  205.                         return false;
  206.                     fi;
  207.                 od;
  208.             od;
  209.         od;
  210.  
  211.         # check that the permutation commutes with the generators
  212.         for gen  in G.generators  do
  213.             for orb  in orbs  do
  214.                 for pnt  in orb  do
  215.                     if perm[l][pnt] ^ gen <> perm[l][pnt ^ gen]  then
  216.                         return false;
  217.                     fi;
  218.                 od;
  219.             od;
  220.         od;
  221.  
  222.         # everything is ok, the representation is semiregular
  223.         return true;
  224.  
  225.     # delegate nonstandard case
  226.     else
  227.         return GroupOps.IsSemiRegular( G, D, opr );
  228.     fi;
  229.  
  230. end;
  231.  
  232.  
  233. #############################################################################
  234. ##
  235. #F  PermGroupOps.Orbit(<G>,<d>)  . orbit of a point under a permutation group
  236. ##
  237. #N  13-Jun-91 martin 'PermGroupOps.Orbit' should handle 'OnPairs'
  238. #N  by keeping for all first points a list of known second points
  239. ##
  240. PermGroupOps.Orbit := function ( G, d, opr )
  241.     local   orb,        # orbit of <d> under <G>, result
  242.             max,        # largest point moved by the group <G>
  243.             new,        # boolean list indicating whether a point is new
  244.             gen,        # generator of the group <G>
  245.             pnt,        # point in the orbit <orb>
  246.             img;        # image of the point <pnt> under the generator <gen>
  247.  
  248.     # standard operation
  249.     if   opr = OnPoints  and IsInt(d)  then
  250.         InfoOperation1("#I  Orbit |<d>^<G>|=\c");
  251.  
  252.         # get the largest point <max> moved by the group <G>
  253.         max := 0;
  254.         for gen  in G.generators  do
  255.             if max < LargestMovedPointPerm(gen)  then
  256.                 max := LargestMovedPointPerm(gen);
  257.             fi;
  258.         od;
  259.  
  260.         # handle fixpoints
  261.         if not d in [1..max]  then
  262.             return [ d ];
  263.         fi;
  264.  
  265.         # start with the singleton orbit
  266.         orb := [ d ];
  267.         new := BlistList( [1..max], [1..max] );
  268.         new[d] := false;
  269.  
  270.         # loop over all points found
  271.         for pnt  in orb  do
  272.  
  273.             # apply all generators <gen>
  274.             for gen  in G.generators  do
  275.                 img := pnt ^ gen;
  276.  
  277.                 # add the image <img> to the orbit if it is new
  278.                 if new[img]  then
  279.                     Add( orb, img );
  280.                     new[img] := false;
  281.                 fi;
  282.  
  283.             od;
  284.  
  285.         od;
  286.         InfoOperation1("\r#I  Orbit |<d>^<G>|=",Length(orb),"\n");
  287.  
  288.     # other operation, fall back on default function
  289.     else
  290.         orb := GroupOps.Orbit( G, d, opr );
  291.     fi;
  292.  
  293.     # return the orbit <orb>
  294.     return orb;
  295. end;
  296.  
  297.  
  298. #############################################################################
  299. ##
  300. #F  PermGroupOps.OrbitLength(<G>,<d>) . . length of the orbit of a perm group
  301. ##
  302. PermGroupOps.OrbitLength := function ( G, d, opr )
  303.     local   len,        # length of orbit, result
  304.             rep,        # element of <G> mapping <d>[1] to <G>.orbit[1]
  305.             d1, d2;     # first and second point of a pair
  306.  
  307.     # standard operation, watch out if we know the orbit
  308.     if  opr = OnPoints  then
  309.         if IsBound(G.orbit)  and d in G.orbit  then
  310.             len := Length(G.orbit);
  311.         else
  312.             len := GroupOps.OrbitLength( G, d, OnPoints );
  313.         fi;
  314.  
  315.     # operation on trivial tuple
  316.     elif opr = OnTuples  and Length(d) = 0  then
  317.         len := 1;
  318.  
  319.     # operation on singleton tuples
  320.     elif opr = OnTuples  and Length(d) = 1  then
  321.         if IsBound(G.orbit)  and d[1] in G.orbit  then
  322.             len := Length(G.orbit);
  323.         else
  324.             len := GroupOps.OrbitLength( G, d[1], OnPoints );
  325.         fi;
  326.  
  327.     # operation on pairs $|d^G| = |{d_1}^G||{d_2}^G_{d_1}|$
  328.     elif opr = OnPairs  or (opr = OnTuples  and Length(d) = 2)  then
  329.         if IsBound(G.orbit)  and d[1] in G.orbit  then
  330.             d2 := d[2];
  331.             d1 := d[1];
  332.             while d1 <> G.orbit[1]  do
  333.                 d2 := d2 ^ G.transversal[d1];
  334.                 d1 := d1 ^ G.transversal[d1];
  335.             od;
  336.             len := Length( G.orbit )
  337.                    * G.operations.OrbitLength(
  338.                         G.operations.Stabilizer( G, G.orbit[1], OnPoints ),
  339.                         d2,
  340.                         OnPoints );
  341.         else
  342.             len := GroupOps.OrbitLength( G, d, OnPairs );
  343.         fi;
  344.  
  345.     # operation on longer tuples $|d^G| = |{d_1}^G||{d_2..d_k}^G_{d_1}|$
  346.     elif opr = OnTuples  then
  347.         if IsBound(G.orbit)  and d[1] in G.orbit  then
  348.             rep := G.transversal[d[1]];
  349.             while d[1]^rep <> G.orbit[1]  do
  350.                 rep := rep * G.transversal[d[1]^rep];
  351.             od;
  352.             len := Length( G.orbit )
  353.                    * G.operations.OrbitLength(
  354.                         G.operations.Stabilizer( G, G.orbit[1], OnPoints ),
  355.                         OnTuples( Sublist(d,[2..Length(d)]), rep ),
  356.                         OnTuples );
  357.         else
  358.             len := GroupOps.OrbitLength( G, d, OnTuples );
  359.         fi;
  360.  
  361.     # other operation, fall back to group operations
  362.     else
  363.         len := GroupOps.OrbitLength( G, d, opr );
  364.     fi;
  365.  
  366.     return len;
  367. end;
  368.  
  369.  
  370. #############################################################################
  371. ##
  372. #F  PermGroupOps.Orbits(<G>,<D>) orbits of a domain under a permutation group
  373. ##
  374. PermGroupOps.Orbits := function ( G, D, opr )
  375.     local   orbs,       # orbits, result
  376.             orb,        # orbit
  377.             max,        # largest point moved by the group <G>
  378.             dom,        # intersection of <D> and [1..<max>] as boolean list
  379.             new,        # boolean list indicating whether a point is new
  380.             gen,        # generator of the group <G>
  381.             pnt,        # point in the orbit <orb>
  382.             fst,        # first point in the orbit <orb>
  383.             img;        # image of the point <pnt> under the generator <gen>
  384.  
  385.     # standard operation
  386.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  387.         InfoOperation1("#I  Orbits |orbs|=\c");
  388.  
  389.         # get the group <G> and the domain <D>
  390.         D := Set( D );
  391.  
  392.         # get the largest point <max> moved by the group <G>
  393.         max := 0;
  394.         for gen  in G.generators  do
  395.             if max < LargestMovedPointPerm(gen)  then
  396.                 max := LargestMovedPointPerm(gen);
  397.             fi;
  398.         od;
  399.         dom := BlistList( [1..max], D );
  400.         new := BlistList( [1..max], [1..max] );
  401.         orbs := [];
  402.  
  403.         # repeat until the domain is exhausted
  404.         fst := Position( dom, true );
  405.         while fst <> false  do
  406.  
  407.             # start with the singleton orbit
  408.             orb := [ fst ];
  409.             new[fst] := false;
  410.             dom[fst] := false;
  411.  
  412.             # loop over all points found
  413.             for pnt  in orb  do
  414.  
  415.                 # apply all generators <gen>
  416.                 for gen  in G.generators  do
  417.                     img := pnt ^ gen;
  418.  
  419.                     # add the image <img> to the orbit if it is new
  420.                     if new[img]  then
  421.                         Add( orb, img );
  422.                         new[img] := false;
  423.                         dom[img] := false;
  424.                     fi;
  425.  
  426.                 od;
  427.  
  428.             od;
  429.  
  430.             # add the orbit to the list of orbits and take next point
  431.             Add( orbs, orb );
  432.             fst := Position( dom, true, fst );
  433.             InfoOperation2("\r#I  Orbits |orbs|=",Length(orbs),"\c");
  434.  
  435.         od;
  436.  
  437.         # add the remaining points of <D>, they are fixed
  438.         for pnt  in [ PositionSorted( D, max+1 ) .. Length(D) ]  do
  439.             Add( orbs, [ D[pnt] ] );
  440.         od;
  441.         InfoOperation1("\r#I  Orbits |orbs|=",Length(orbs),"\n");
  442.  
  443.     # the domain <D> contains other stuff
  444.     else
  445.         orbs := GroupOps.Orbits( G, D, opr );
  446.     fi;
  447.  
  448.     # return the orbits <orbs>
  449.     return orbs;
  450. end;
  451.  
  452.  
  453. #############################################################################
  454. ##
  455. #F  PermGroupOps.OrbitLengths(<G>,<D>) . .  lengths of orbits of a perm group
  456. ##
  457. PermGroupOps.OrbitLengths := function ( G, D, opr )
  458.     local   lens,       # orbit lengths, result
  459.             orb,        # orbit
  460.             max,        # largest point moved by the group <G>
  461.             dom,        # intersection of <D> and [1..<max>] as boolean list
  462.             new,        # boolean list indicating whether a point is new
  463.             gen,        # generator of the group <G>
  464.             pnt,        # point in the orbit <orb>
  465.             fst,        # first point in the orbit <orb>
  466.             img;        # image of the point <pnt> under the generator <gen>
  467.  
  468.     # standard operation
  469.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  470.         InfoOperation1("#I  OrbitLengths |orbs|=\c");
  471.  
  472.         # get the group <G> and the domain <D>
  473.         D := Set( D );
  474.  
  475.         # get the largest point <max> moved by the group <G>
  476.         max := 0;
  477.         for gen  in G.generators  do
  478.             if max < LargestMovedPointPerm(gen)  then
  479.                 max := LargestMovedPointPerm(gen);
  480.             fi;
  481.         od;
  482.         dom := BlistList( [1..max], D );
  483.         new := BlistList( [1..max], [1..max] );
  484.         lens := [];
  485.  
  486.         # repeat until the domain is exhausted
  487.         fst := Position( dom, true );
  488.         while fst <> false  do
  489.  
  490.             # start with the singleton orbit
  491.             orb := [ fst ];
  492.             new[fst] := false;
  493.             dom[fst] := false;
  494.  
  495.             # loop over all points found
  496.             for pnt  in orb  do
  497.  
  498.                 # apply all generators <gen>
  499.                 for gen  in G.generators  do
  500.                     img := pnt ^ gen;
  501.  
  502.                     # add the image <img> to the orbit if it is new
  503.                     if new[img]  then
  504.                         Add( orb, img );
  505.                         new[img] := false;
  506.                         dom[img] := false;
  507.                     fi;
  508.  
  509.                 od;
  510.  
  511.             od;
  512.  
  513.             # add the length to the list of lengths and take next point
  514.             Add( lens, Length(orb) );
  515.             fst := Position( dom, true, fst );
  516.             InfoOperation2("\r#I  OrbitLengths |orbs|=",
  517.                            Length(lens),"\c");
  518.  
  519.         od;
  520.  
  521.         # add the remaining points of <D>, they are fixed
  522.         for pnt  in [ PositionSorted( D, max+1 ) .. Length(D) ]  do
  523.             Add( lens, 1 );
  524.         od;
  525.         InfoOperation1("\r#I  OrbitLengths |orbs|=",
  526.                        Length(lens),"\n");
  527.  
  528.     # other operation
  529.     else
  530.         lens := GroupOps.OrbitLengths( G, D, opr );
  531.     fi;
  532.  
  533.     # return the orbit lengths <lens>
  534.     return lens;
  535. end;
  536.  
  537.  
  538. #############################################################################
  539. ##
  540. #F  PermGroupOps.Operation(<G>,<D>)   . operation of a perm group on a domain
  541. ##
  542. PermGroupOps.Operation := function ( G, D, opr )
  543.     local   grp,        # operation group, result
  544.             prms,       # generators of the operation group <grp>
  545.             prm,        # generator of the operation group <grp>
  546.             gen,        # generator of the group <G>
  547.             pos,        # inverse of the domain <D>
  548.             inc,        # increment if <D> is a range
  549.             disjoint,   # <D> is a list of disjoint sets of integers
  550.             i, k;       # loop variable
  551.  
  552.     # standard operation on a range
  553.     if opr = OnPoints  and IsRange(D)  then
  554.         InfoOperation1("#I  Operation(<G>,<range>) \c");
  555.         if Length(D) = 1  then
  556.             inc := 1;
  557.         else
  558.             inc := D[2] - D[1];
  559.         fi;
  560.  
  561.         # for each generator <gen> of the group <G>
  562.         InfoOperation2("\r#I  Operation(<G>,<range>) make perm");
  563.         prms := [];
  564.         for gen  in G.generators  do
  565.  
  566.             # compute the permutation <prm>
  567.             prm := [];
  568.             for i  in [1..Length(D)]  do
  569.                 prm[i] := (D[i]^gen - D[1]) / inc + 1;
  570.             od;
  571.  
  572.             # add it to the list of generators <prms>
  573.             Add( prms, PermList( prm ) );
  574.             InfoOperation2("\r#I  Operation(<G>,<range>) make perm",
  575.                            Position( G.generators, gen ), "\c" );
  576.  
  577.         od;
  578.  
  579.         # make the operation group <grp>
  580.         grp := Group( prms, () );
  581.         grp.operationImages := prms;
  582.         InfoOperation1("\r#I  Operation(<G>,<range>) returns   \n");
  583.  
  584.     # standard operation on a domain <D> that is not a range
  585.     elif opr = OnPoints  and ForAll( D, IsInt )  then
  586.         InfoOperation1("#I  Operation(<G>,<D>) \c");
  587.  
  588.         # find the inverse <pos> of the domain <D>
  589.         pos := [];
  590.         for i  in [1..Length(D)]  do
  591.             pos[D[i]] := i;
  592.         od;
  593.  
  594.         # for each generator <gen> of the group <G>
  595.         InfoOperation2("\r#I  Operation(<G>,<D>) make perm");
  596.         prms := [];
  597.         for gen  in G.generators  do
  598.  
  599.             # compute the permutation <prm>
  600.             prm := [];
  601.             for i  in [1..Length(D)]  do
  602.                 prm[i] := pos[ D[i]^gen ];
  603.             od;
  604.  
  605.             # add it to the list of generators <prms>
  606.             Add( prms, PermList( prm ) );
  607.             InfoOperation2("\r#I  Operation(<G>,<D>) make perm",
  608.                            Position( G.generators, gen ), "\c" );
  609.  
  610.         od;
  611.  
  612.         # make the operation group <grp>
  613.         grp := Group( prms, () );
  614.         grp.operationImages := prms;
  615.         InfoOperation1("\r#I  Operation(<G>,<D>) returns   \n");
  616.  
  617.     # operation on sets of integers
  618.     elif  opr = OnSets  and ForAll( D, d -> ForAll( d, IsInt ) )  then
  619.         InfoOperation1("#I  Operation(<G>,<D>) \c");
  620.  
  621.         # remember the block in which each element lies
  622.         disjoint := true;
  623.         pos := [];
  624.         for i  in [ 1 .. Length(D) ]  do
  625.             for k  in D[i]  do
  626.                 disjoint := disjoint and not IsBound( pos[k] );
  627.                 if disjoint  then
  628.                     pos[k] := i;
  629.                 fi;
  630.             od;
  631.         od;
  632.  
  633.         # we can only handle this case if all the sets are disjoint
  634.         if not disjoint  then
  635.             return GroupOps.Operation( G, D, opr );
  636.         fi;
  637.  
  638.         # for each generator <gen> of the group <G>
  639.         InfoOperation2("\r#I  Operation(<G>,<D>) make perm");
  640.         prms := [];
  641.         for gen  in G.generators  do
  642.  
  643.             # compute the permutation <prm>
  644.             prm := [];
  645.             for i  in [1..Length(D)]  do
  646.                 prm[i] := pos[ D[i][1]^gen ];
  647.             od;
  648.  
  649.             # add it to the list of generators <prms>
  650.             Add( prms, PermList( prm ) );
  651.             InfoOperation2("\r#I  Operation(<G>,<D>) make perm",
  652.                            Position( G.generators, gen ), "\c" );
  653.  
  654.         od;
  655.  
  656.         # make the operation group <grp>
  657.         grp := Group( prms, () );
  658.         grp.operationImages := prms;
  659.         InfoOperation1("\r#I  Operation(<G>,<D>) returns   \n");
  660.  
  661.     # other operation
  662.     else
  663.         grp := GroupOps.Operation( G, D, opr );
  664.     fi;
  665.  
  666.     # return the operation group <grp>
  667.     return grp;
  668. end;
  669.  
  670.  
  671. #############################################################################
  672. ##
  673. #F  PermGroupOps.Blocks( <G>, <D> [, <seed>] [, <operation>] )
  674. ##
  675. PermGroupOps.BlocksNoSeed := function ( G, D )
  676.     local   blocks,     # block system of <G>, result
  677.             orbit,      # orbit of 1 under <G>
  678.             trans,      # factored inverse transversal for <orbit>
  679.             eql,        # '<i> = <eql>[<k>]' means $\beta(i)  = \beta(k)$,
  680.             next,       # the points that are equivalent are linked
  681.             last,       # last point on the list linked through 'next'
  682.             leq,        # '<i> = <leq>[<k>]' means $\beta(i) <= \beta(k)$
  683.             gen,        # one generator of <G> or 'Stab(<G>,1)'
  684.             rnd,        # random element of <G>
  685.             pnt,        # one point in an orbit
  686.             img,        # the image of <pnt> under <gen>
  687.             cur,        # the current representative of an orbit
  688.             rep,        # the representative of a block in the block system
  689.             block,      # the block, result
  690.             changed,    # number of random Schreier generators
  691.             nrorbs,     # number of orbits of subgroup $H$ of $G_1$
  692.             i;          # loop variable
  693.  
  694.     # handle trivial domain
  695.     if Length( D ) = 1  or IsPrime( Length( D ) )  then
  696.         return [ D ];
  697.     fi;
  698.  
  699.     # handle trivial group
  700.     if IsTrivial( G )  then
  701.         Error("<G> must operate transitively on <D>");
  702.     fi;
  703.  
  704.     # compute the orbit of $G$ and a factored transversal
  705.     orbit := [ D[1] ];
  706.     trans := [];
  707.     trans[ D[1] ] := ();
  708.     for pnt  in orbit  do
  709.         for gen  in G.generators  do
  710.             if not IsBound( trans[ pnt / gen ] )  then
  711.                 Add( orbit, pnt / gen );
  712.                 trans[ pnt / gen ] := gen;
  713.             fi;
  714.         od;
  715.     od;
  716.  
  717.     # check that the group is transitive
  718.     if Length( orbit ) <> Length( D )  then
  719.         Error("<G> must operate transitively on <D>");
  720.     fi;
  721.     InfoOperation1("#I  BlocksNoSeed transversal computed\n");
  722.     nrorbs := Length( orbit );
  723.  
  724.     # since $i \in k^{G_1}$ implies $\beta(i)=\beta(k)$,  we initialize <eql>
  725.     # so that the connected components are orbits of some subgroup  $H < G_1$
  726.     eql := [];
  727.     leq := [];
  728.     next := [];
  729.     last := [];
  730.     for pnt  in orbit  do
  731.         eql[pnt]  := pnt;
  732.         leq[pnt]  := pnt;
  733.         next[pnt] := 0;
  734.         last[pnt] := pnt;
  735.     od;
  736.  
  737.     # repeat until we have a block system
  738.     changed := 0;
  739.     cur := orbit[2];
  740.     rnd := ();
  741.     repeat
  742.  
  743.         # compute such an $H$ by taking random  Schreier generators  of $G_1$
  744.         # and stop if 2 successive generators dont change the orbits any more
  745.         while changed < 2  do
  746.  
  747.             # compute a random Schreier generator of $G_1$
  748.             i := Length( orbit );
  749.             while 1 <= i  do
  750.                 rnd := rnd * Random( G.generators );
  751.                 i   := QuoInt( i, 2 );
  752.             od;
  753.             gen := rnd;
  754.             while D[1] ^ gen <> D[1]  do
  755.                 gen := gen * trans[ D[1] ^ gen ];
  756.             od;
  757.             changed := changed + 1;
  758.  
  759.             # compute the image of every point under <gen>
  760.             for pnt  in orbit  do
  761.                 img := pnt ^ gen;
  762.  
  763.                 # find the representative of the orbit of <pnt>
  764.                 while eql[pnt] <> pnt  do
  765.                     pnt := eql[pnt];
  766.                 od;
  767.  
  768.                 # find the representative of the orbit of <img>
  769.                 while eql[img] <> img  do
  770.                     img := eql[img];
  771.                 od;
  772.  
  773.                 # if the don't agree merge their orbits
  774.                 if   pnt < img  then
  775.                     eql[img] := pnt;
  776.                     next[ last[pnt] ] := img;
  777.                     last[pnt] := last[img];
  778.                     nrorbs := nrorbs - 1;
  779.                     changed := 0;
  780.                 elif img < pnt  then
  781.                     eql[pnt] := img;
  782.                     next[ last[img] ] := pnt;
  783.                     last[img] := last[pnt];
  784.                     nrorbs := nrorbs - 1;
  785.                     changed := 0;
  786.                 fi;
  787.  
  788.             od;
  789.  
  790.         od;
  791.         InfoOperation1("#I  BlocksNoSeed ",
  792.                        "number of orbits of <H> < <G>_1 is ",nrorbs,"\n");
  793.  
  794.         # take arbitrary point <cur>,  and an element <gen> taking 1 to <cur>
  795.         while eql[cur] <> cur  do
  796.             cur := eql[cur];
  797.         od;
  798.         gen := [];
  799.         img := cur;
  800.         while img <> D[1]  do
  801.             Add( gen, trans[img] );
  802.             img := img ^ trans[img];
  803.         od;
  804.         gen := Reversed( gen );
  805.  
  806.         # compute an alleged block as orbit of 1 under $< H, gen >$
  807.         pnt := cur;
  808.         while pnt <> 0  do
  809.  
  810.             # compute the representative of the block containing the image
  811.             img := pnt;
  812.             for i  in gen  do
  813.                 img := img / i;
  814.             od;
  815.             while eql[img] <> img  do
  816.                 img := eql[img];
  817.             od;
  818.  
  819.             # if its not our current block but a minimal block
  820.             if   img <> D[1]  and img <> cur  and leq[img] = img  then
  821.  
  822.                 # then try <img> as a new start
  823.                 leq[cur] := img;
  824.                 cur := img;
  825.                 gen := [];
  826.                 img := cur;
  827.                 while img <> D[1]  do
  828.                     Add( gen, trans[img] );
  829.                     img := img ^ trans[img];
  830.                 od;
  831.                 gen := Reversed( gen );
  832.                 pnt := cur;
  833.  
  834.             # otherwise if its not our current block but contains it
  835.             # by construction a nonminimal block contains the current block
  836.             elif img <> D[1]  and img <> cur  and leq[img] <> img  then
  837.  
  838.                 # then merge all blocks it contains with <cur>
  839.                 while img <> cur  do
  840.                     eql[img] := cur;
  841.                     next[ last[cur] ] := img;
  842.                     last[ cur ] := last[ img ];
  843.                     img := leq[img];
  844.                     while img <> eql[img]  do
  845.                         img := eql[img];
  846.                     od;
  847.                 od;
  848.                 pnt := next[pnt];
  849.  
  850.             # go on to the next point in the orbit
  851.             else
  852.  
  853.                 pnt := next[pnt];
  854.  
  855.             fi;
  856.  
  857.         od;
  858.  
  859.         # make the alleged block
  860.         block := [ D[1] ];
  861.         pnt := cur;
  862.         while pnt <> 0  do
  863.             Add( block, pnt );
  864.             pnt := next[pnt];
  865.         od;
  866.         block := Set( block );
  867.         blocks := [ block ];
  868.         InfoOperation1("#I  BlocksNoSeed ",
  869.                        "length of alleged block is ",Length(block),"\n");
  870.  
  871.         # quick test to see if the group is primitive
  872.         if Length( block ) = Length( orbit )  then
  873.             InfoOperation1("#I  BlocksNoSeed <G> is primitive\n");
  874.             return [ D ];
  875.         fi;
  876.  
  877.         # quick test to see if the orbit can be a block
  878.         if Length( orbit ) mod Length( block ) <> 0  then
  879.             InfoOperation1("#I  BlocksNoSeed ",
  880.                            "alleged block is clearly not a block\n");
  881.             changed := -1000;
  882.         fi;
  883.  
  884.         # '<rep>[<i>]' is the representative of the block containing <i>
  885.         rep := [];
  886.         for pnt  in orbit  do
  887.             rep[pnt] := 0;
  888.         od;
  889.         for pnt  in block  do
  890.             rep[pnt] := 1;
  891.         od;
  892.  
  893.         # compute the block system with an orbit algorithm
  894.         i := 1;
  895.         while 0 <= changed  and i <= Length( blocks )  do
  896.  
  897.             # loop over the generators
  898.             for gen  in G.generators  do
  899.  
  900.                 # compute the image of the block under the generator
  901.                 img := OnSets( blocks[i], gen );
  902.  
  903.                 # if this block is new
  904.                 if rep[ img[1] ] = 0  then
  905.  
  906.                     # add the new block to the list of blocks
  907.                     Add( blocks, img );
  908.  
  909.                     # check that all points in the image are new
  910.                     for pnt  in img  do
  911.                         if rep[pnt] <> 0  then
  912.                             InfoOperation1("#I  BlocksNoSeed ",
  913.                                            "alleged block is not a block\n");
  914.                             changed := -1000;
  915.                         fi;
  916.                         rep[pnt] := img[1];
  917.                     od;
  918.  
  919.                 # if this block is old
  920.                 else
  921.  
  922.                     # check that all points in the image lie in the block
  923.                     for pnt  in img  do
  924.                         if rep[pnt] <> rep[img[1]]  then
  925.                            InfoOperation1("#I  BlocksNoSeed ",
  926.                                            "alleged block is not a block\n");
  927.                             changed := -1000;
  928.                         fi;
  929.                     od;
  930.  
  931.                 fi;
  932.  
  933.             od;
  934.  
  935.             # on to the next block in the orbit
  936.             i := i + 1;
  937.         od;
  938.  
  939.     until 0 <= changed;
  940.  
  941.     # return the block system
  942.     return blocks;
  943. end;
  944.  
  945. PermGroupOps.BlocksSeed := function ( G, D, seed )
  946.     local   blks,       # list of blocks, result
  947.             rep,        # representative of a point
  948.             siz,        # siz[a] of the size of the block with rep <a>
  949.             fst,        # first point still to be merged into another block
  950.             nxt,        # next  point still to be merged into another block
  951.             lst,        # last  point still to be merged into another block
  952.             gen,        # generator of the group <G>
  953.             nrb,        # number of blocks so far
  954.             a, b, c, d; # loop variables for points
  955.  
  956.     nrb := Length(D) - Length(seed) + 1;
  957.     InfoOperation1("#I  BlocksSeed |<blocks>|=",nrb,"  \c");
  958.  
  959.     # in the beginning each point <d> is in a block by itself
  960.     rep := [];
  961.     siz := [];
  962.     for d  in D  do
  963.         rep[d] := d;
  964.         siz[d] := 1;
  965.     od;
  966.  
  967.     # except the points in <seed>, which form one block with rep <seed>[1]
  968.     fst := 0;
  969.     nxt := siz;
  970.     lst := 0;
  971.     c   := seed[1];
  972.     for d  in seed  do
  973.         if d <> c  then
  974.             rep[d] := c;
  975.             siz[c] := siz[c] + siz[d];
  976.             if fst = 0  then
  977.                 fst      := d;
  978.             else
  979.                 nxt[lst] := d;
  980.             fi;
  981.             lst      := d;
  982.             nxt[lst] := 0;
  983.         fi;
  984.     od;
  985.  
  986.     # while there are points still to be merged into another block
  987.     while fst <> 0  do
  988.  
  989.         # get this point <a> and its repesentative <b>
  990.         a := fst;
  991.         b := rep[fst];
  992.  
  993.         # for each generator <gen> merge the blocks of <a>^<gen>, <b>^<gen>
  994.         for gen  in G.generators  do
  995.             c := a^gen;
  996.             while rep[c] <> c  do
  997.                 c := rep[c];
  998.             od;
  999.             d := b^gen;
  1000.             while rep[d] <> d  do
  1001.                 d := rep[d];
  1002.             od;
  1003.             if c <> d  then
  1004.                 if Length(D) < 2*(siz[c] + siz[d])  then
  1005.                     InfoOperation1("\r#I  BlocksSeed |<blocks>|=1 ",
  1006.                                    "(one block too large)\n");
  1007.                     return [ D ];
  1008.                 fi;
  1009.                 nrb := nrb - 1;
  1010.                 InfoOperation2("\r#I  BlocksSeed |<blocks>|=",
  1011.                                nrb,"  \c");
  1012.                 if siz[d] <= siz[c]  then
  1013.                     rep[d]   := c;
  1014.                     siz[c]   := siz[c] + siz[d];
  1015.                     nxt[lst] := d;
  1016.                     lst      := d;
  1017.                     nxt[lst] := 0;
  1018.                 else
  1019.                     rep[c]   := d;
  1020.                     siz[d]   := siz[d] + siz[c];
  1021.                     nxt[lst] := c;
  1022.                     lst      := c;
  1023.                     nxt[lst] := 0;
  1024.                 fi;
  1025.             fi;
  1026.         od;
  1027.  
  1028.         # on to the next point still to be merged into another block
  1029.         fst := nxt[fst];
  1030.     od;
  1031.  
  1032.     # turn the list of representatives <rep> into a list of blocks <blks>
  1033.     blks := [];
  1034.     for d  in D  do
  1035.         c := d;
  1036.         while rep[c] <> c  do
  1037.            c := rep[c];
  1038.         od;
  1039.         if IsInt( nxt[c] )  then
  1040.             nxt[c] := [ d ];
  1041.             Add( blks, nxt[c] );
  1042.         else
  1043.             AddSet( nxt[c], d );
  1044.         fi;
  1045.     od;
  1046.  
  1047.     # return the set of blocks <blks>
  1048.     InfoOperation1("\r#I  BlocksSeed |<blocks>|=",nrb,"  \n");
  1049.     return Set( blks );
  1050. end;
  1051.  
  1052. PermGroupOps.Blocks := function ( G, D, seed, opr )
  1053.     local   blks,       # blocks, result
  1054.             i;          # loop variable
  1055.  
  1056.     # standard operation on points
  1057.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  1058.         InfoOperation1("#I  Blocks called\n");
  1059.  
  1060.         # dispatch to appropriate function
  1061.         if seed = []  then
  1062.             blks := G.operations.BlocksNoSeed( G, D );
  1063.         else
  1064.             blks := G.operations.BlocksSeed( G, D, seed );
  1065.         fi;
  1066.  
  1067.         # give some information
  1068.         InfoOperation1("#I  Blocks |<blocks>|=",Length(blks),"\n");
  1069.  
  1070.     # other operation
  1071.     else
  1072.         blks := GroupOps.Blocks( G, D, seed, opr );
  1073.     fi;
  1074.  
  1075.     # return the blocks <blks>
  1076.     return blks;
  1077. end;
  1078.  
  1079.  
  1080. #############################################################################
  1081. ##
  1082. #F  PermGroupOps.MaximalBlocks( <G>, <D> [, <seed>] [, <operation>] )
  1083. ##
  1084. PermGroupOps.MaximalBlocks := function ( G, D, seed, opr )
  1085.     local   blks,       # blocks, result
  1086.             H,          # image of <G>
  1087.             blksH,      # blocks of <H>
  1088.             i;          # loop variable
  1089.  
  1090.     # standard operation on points
  1091.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  1092.         InfoOperation1("#I  MaximalBlocks called\n");
  1093.  
  1094.         # dispatch to appropriate function
  1095.         if seed = []  then
  1096.             blks := G.operations.BlocksNoSeed( G, D );
  1097.         else
  1098.             blks := G.operations.BlocksSeed( G, D, seed );
  1099.         fi;
  1100.  
  1101.         # iterate until the operation becomes primitive
  1102.         H := G;
  1103.         blksH := blks;
  1104.         while Length( blksH ) <> 1  do
  1105.             H     := Operation( H, blksH, OnSets );
  1106.             blksH := Blocks( H, [1..Length(blksH)] );
  1107.             if Length( blksH ) <> 1  then
  1108.                 blks := List( blksH, bl -> Union( Sublist( blks, bl ) ) );
  1109.             fi;
  1110.         od;
  1111.  
  1112.         # give some information
  1113.         InfoOperation1("#I  MaximalBlocks |<blocks>|=",Length(blks),"\n");
  1114.  
  1115.     # other operation
  1116.     else
  1117.         blks := GroupOps.MaximalBlocks( G, D, seed, opr );
  1118.     fi;
  1119.  
  1120.     # return the blocks <blks>
  1121.     return blks;
  1122. end;
  1123.  
  1124.  
  1125. #############################################################################
  1126. ##
  1127. #F  PermGroupOps.Stabilizer(<G>,<d>)  . . . stabilizer of a permutation group
  1128. ##
  1129. PermGroupOps.Stabilizer := function ( G, d, opr )
  1130.     local   K,          # stabilizer <K>, result
  1131.             S;          # stabilizer of <G>, not a subgroup
  1132.  
  1133.     # standard operation on points, make a stabchain beginning with <d>
  1134.     if   opr = OnPoints  and IsInt(d)  then
  1135.         MakeStabChain( G, [d] );
  1136.         if G.generators <> []  and G.orbit[1] = d  then
  1137.             K := Subgroup( Parent(G), G.stabilizer.generators );
  1138.             if IsBound( G.stabilizer.orbit )  then
  1139.                 K.orbit       := ShallowCopy(G.stabilizer.orbit);
  1140.                 K.transversal := ShallowCopy(G.stabilizer.transversal);
  1141.                 K.stabilizer  := Copy( G.stabilizer.stabilizer );
  1142.             fi;
  1143.         else
  1144.             K := ShallowCopy( G );
  1145.             if IsBound( G.orbit )  then
  1146.                 K.orbit       := ShallowCopy( G.orbit );
  1147.                 K.transversal := ShallowCopy( G.transversal );
  1148.                 K.stabilizer  := Copy( G.stabilizer );
  1149.             fi;
  1150.         fi;
  1151.  
  1152.     # standard operation on a permutation, take the centralizer
  1153.     elif opr = OnPoints  and IsPerm(d)  then
  1154.         K := G.operations.Centralizer( G, d );
  1155.  
  1156.     # standard operation on a permutation group, take the normalizer
  1157.     elif opr = OnPoints  and IsPermGroup(d)  then
  1158.         K := G.operations.Normalizer( G, d );
  1159.  
  1160.     # operation on tuples of points, make a stabchain beginning with <d>
  1161.     elif (opr = OnPairs  or opr = OnTuples)  and ForAll( d, IsInt )  then
  1162.         MakeStabChain( G, d );
  1163.         S := G;
  1164.         while S.generators <> []  and S.orbit[1] in d  do
  1165.             S := S.stabilizer;
  1166.         od;
  1167.         K := Subgroup( Parent(G), S.generators );
  1168.         if IsBound( S.orbit )  then
  1169.             K.orbit       := ShallowCopy( S.orbit );
  1170.             K.transversal := ShallowCopy( S.transversal );
  1171.             K.stabilizer  := Copy( S.stabilizer );
  1172.         fi;
  1173.  
  1174.     # operation on pairs or tuples of permutations, take the centralizer
  1175.     elif (opr = OnPairs  or opr = OnTuples)  and ForAll( d, IsPerm )  then
  1176.         K := G.operations.Centralizer( G, Subgroup( Parent(G), d ) );
  1177.  
  1178.     # operation on sets of points, use a backtrack
  1179.     elif opr = OnSets  and ForAll( d, IsInt )  then
  1180.         K := G.operations.StabilizerSet( G, d );
  1181.  
  1182.     # other operation
  1183.     else
  1184.         K := GroupOps.Stabilizer( G, d, opr );
  1185.     fi;
  1186.  
  1187.     # return the stabilizer
  1188.     return K;
  1189. end;
  1190.  
  1191.  
  1192. #############################################################################
  1193. ##
  1194. #F  PermGroupOps.RepresentativeOperation(<G>,<d>,<e>,<opr>) .  representative
  1195. #F                                          of a point in a permutation group
  1196. ##
  1197. PermGroupOps.RepresentativeOperation := function ( G, d, e, opr )
  1198.     local   rep,                # representative, result
  1199.             S,                  # stabilizer of <G>
  1200.             rep2,               # representative in <S>
  1201.             i;                  # loop variable
  1202.  
  1203.     # standard operation on points, make a basechange and trace the rep
  1204.     if   opr = OnPoints  and IsInt(d)  then
  1205.         MakeStabChain( G, [d] );
  1206.         rep := G.identity;
  1207.         if G.generators <> []  and d = G.orbit[1]  then
  1208.             if e in G.orbit  then
  1209.                 while d^rep <> e  do
  1210.                     rep := G.transversal[e/rep] mod rep;
  1211.                 od;
  1212.             else
  1213.                 rep := false;
  1214.             fi;
  1215.         elif d <> e  then
  1216.             rep := false;
  1217.         fi;
  1218.  
  1219.     # operation on permutations, use backtrack
  1220.     elif opr = OnPoints  and IsPerm(d)  then
  1221.         rep := G.operations.RepresentativeConjugationElements( G, d, e );
  1222.  
  1223.     # operation on permgroups, use backtrack
  1224.     elif opr = OnPoints  and IsPermGroup(d)  then
  1225.         rep := G.operations.RepresentativeConjugationGroups( G, d, e );
  1226.  
  1227.     # operation on pairs or tuples of points, iterate
  1228.     elif (opr = OnPairs  or opr = OnTuples)  and ForAll( d, IsInt )  then
  1229.         MakeStabChain( G, d );
  1230.         rep := G.identity;
  1231.         S   := G;
  1232.         i   := 1;
  1233.         while i <= Length(d)  and rep <> false  do
  1234.             if S.generators <> []  and S.orbit[1] = d[i]  then
  1235.                 if e[i]/rep in S.orbit  then
  1236.                     while d[i]^rep <> e[i]  do
  1237.                         rep := S.transversal[e[i]/rep] mod rep;
  1238.                     od;
  1239.                 else
  1240.                     rep := false;
  1241.                 fi;
  1242.                 S := S.stabilizer;
  1243.             elif d[i] <> e[i]/rep  then
  1244.                 rep := false;
  1245.             fi;
  1246.             i := i + 1;
  1247.         od;
  1248.  
  1249.     # operation on pairs on tuples of other objects, iterate
  1250.     elif opr = OnPairs  or opr = OnTuples  then
  1251.         rep := G.identity;
  1252.         S   := G;
  1253.         i   := 1;
  1254.         while i <= Length(d)  and rep <> false  do
  1255.             rep2 := G.operations.RepresentativeOperation(
  1256.                                           S, d[i], e[i]^(rep^-1), OnPoints );
  1257.             if rep2 <> false  then
  1258.                 rep := rep2 * rep;
  1259.                 S   := G.operations.Stabilizer( S, d[i], OnPoints );
  1260.             else
  1261.                 rep := false;
  1262.             fi;
  1263.             i := i + 1;
  1264.         od;
  1265.  
  1266.     # operation on sets of points, use backtrack
  1267.     elif opr = OnSets  and ForAll( d, IsInt )  then
  1268.         rep := G.operations.RepresentativeSet( G, d, e );
  1269.  
  1270.     # other operation, fall back on default representative
  1271.     else
  1272.         rep := GroupOps.RepresentativeOperation( G, d, e, opr );
  1273.     fi;
  1274.  
  1275.     # return the representative
  1276.     return rep;
  1277. end;
  1278.  
  1279.  
  1280. #############################################################################
  1281. ##
  1282. #F  PermGroupOps.SmallestMovedPoint( <G> )  . . . . . .  smallest point moved
  1283. #F                                                     by a permutation group
  1284. ##
  1285. PermGroupOps.SmallestMovedPoint := function ( G )
  1286.     local   min,  minp,  i;
  1287.     if G.generators = []  then
  1288.         Error("<G> must not be trivial");
  1289.     else
  1290.         min := SmallestMovedPointPerm( G.generators[1] );
  1291.         for i  in [2..Length(G.generators)]  do
  1292.             minp := SmallestMovedPointPerm( G.generators[i] );
  1293.             if minp < min  then
  1294.                 min := minp;
  1295.             fi;
  1296.         od;
  1297.     fi;
  1298.     return min;
  1299. end;
  1300.  
  1301.  
  1302. #############################################################################
  1303. ##
  1304. #F  PermGroupOps.LargestMovedPoint( <G> ) . . . . . . . . largest point moved
  1305. #F                                                     by a permutation group
  1306. ##
  1307. PermGroupOps.LargestMovedPoint := function ( G )
  1308.     local   max,  maxp,  i;
  1309.     if G.generators = []  then
  1310.         Error("<G> must not be trivial");
  1311.     else
  1312.         max := LargestMovedPointPerm( G.generators[1] );
  1313.         for i  in [2..Length(G.generators)]  do
  1314.             maxp := LargestMovedPointPerm( G.generators[i] );
  1315.             if max < maxp  then
  1316.                 max := maxp;
  1317.             fi;
  1318.         od;
  1319.     fi;
  1320.     return max;
  1321. end;
  1322.  
  1323.  
  1324. #############################################################################
  1325. ##
  1326. #F  PermGroupOps.MovedPoints( <G> ) . . . . . . . . . . . set of points moved
  1327. #F                                                     by a permutation group
  1328. ##
  1329. PermGroupOps.MovedPoints := function ( G )
  1330.     local   mov, gen, pnt;
  1331.     mov := [];
  1332.     for gen  in G.generators  do
  1333.         for pnt  in [1..LargestMovedPointPerm(gen)]  do
  1334.             if pnt ^ gen <> pnt  then
  1335.                 AddSet( mov, pnt );
  1336.             fi;
  1337.         od;
  1338.     od;
  1339.     return mov;
  1340. end;
  1341.  
  1342.  
  1343. #############################################################################
  1344. ##
  1345. #F  PermGroupOps.NrMovedPoints( <G> ) . . . . . . . .  number of points moved
  1346. #F                                                     by a permutation group
  1347. ##
  1348. PermGroupOps.NrMovedPoints := function ( G )
  1349.     local   mov, gen, pnt;
  1350.     mov := [];
  1351.     for gen  in G.generators  do
  1352.         for pnt  in [1..LargestMovedPointPerm(gen)]  do
  1353.             if pnt ^ gen <> pnt  then
  1354.                 AddSet( mov, pnt );
  1355.             fi;
  1356.         od;
  1357.     od;
  1358.     return Length(mov);
  1359. end;
  1360.  
  1361.  
  1362. #############################################################################
  1363. ##
  1364. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1365. ##
  1366. ##  Local Variables:
  1367. ##  mode:               outline
  1368. ##  outline-regexp:     "#F\\|#V\\|#E"
  1369. ##  fill-column:        73
  1370. ##  fill-prefix:        "##  "
  1371. ##  eval:               (hide-body)
  1372. ##  End:
  1373. ##
  1374.  
  1375.  
  1376.  
  1377.