home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / permutat.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  12.2 KB  |  446 lines
  1. #############################################################################
  2. ##
  3. #A  permutat.g                  GAP library                  Martin Schoenert
  4. #A                                                                & Udo Polis
  5. ##
  6. #A  @(#)$Id: permutat.g,v 3.11 1993/02/09 11:07:40 martin Rel $
  7. ##
  8. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  9. ##
  10. ##  This  file  contains  those  functions  that  deal   with   permutations.
  11. ##
  12. #H  $Log: permutat.g,v $
  13. #H  Revision 3.11  1993/02/09  11:07:40  martin
  14. #H  fixed 'ListPerm' for the empty permutation
  15. #H
  16. #H  Revision 3.10  1993/02/07  17:21:20  martin
  17. #H  fixed operations on ranges
  18. #H
  19. #H  Revision 3.9  1993/01/18  18:56:16  martin
  20. #H  added 'CycleStructurePerm'
  21. #H
  22. #H  Revision 3.8  1992/12/16  19:47:27  martin
  23. #H  replaced quoted record names with escaped ones
  24. #H
  25. #H  Revision 3.7  1992/11/24  17:10:50  martin
  26. #H  fixed 'RestrictedPerm' for the identity
  27. #H
  28. #H  Revision 3.6  1992/03/19  15:42:13  martin
  29. #H  added basic groups
  30. #H
  31. #H  Revision 3.5  1991/12/06  15:37:09  martin
  32. #H  changed 'Cycle' to default to 'GroupElementsOps.Cycle' etc.
  33. #H
  34. #H  Revision 3.4  1991/11/28  14:19:52  martin
  35. #H  moved 'PermutationsOps.Group' from 'permutat.g' to 'permgrp.g'
  36. #H
  37. #H  Revision 3.3  1991/09/30  12:47:07  martin
  38. #H  'Group' binds the generators to '<G>.<i>'
  39. #H
  40. #H  Revision 3.2  1991/09/30  11:43:15  martin
  41. #H  added 'PermutationsOps.Group'
  42. #H
  43. #H  Revision 3.1  1991/09/25  14:03:58  martin
  44. #H  added 'ListPerm', 'SmallestMovedPointPerm', and 'MappingPermListList'
  45. #H
  46. #H  Revision 3.0  1991/08/08  15:33:40  martin
  47. #H  initial revision under RCS
  48. #H
  49. ##
  50.  
  51.  
  52. #############################################################################
  53. ##
  54. #F  InfoOperation?(...) . . .  information function for the operation package
  55. ##
  56. if not IsBound(InfoOperation1)  then InfoOperation1 := Ignore;  fi;
  57. if not IsBound(InfoOperation2)  then InfoOperation2 := Ignore;  fi;
  58.  
  59.  
  60. #############################################################################
  61. ##
  62. #V  Permutations  . . . . . . . . . . . . . . . .  domain of all permutations
  63. #V  PermutationsOps . . . . . . . . . . .  operations record for permutations
  64. ##
  65. PermutationsOps := Copy( GroupElementsOps );
  66.  
  67. PermutationsOps.\in            := function ( g, Permutations )
  68.     return IsPerm( g );
  69. end;
  70.  
  71. Permutations                    := rec();
  72. Permutations.isDomain           := true;
  73.  
  74. Permutations.name               := "Permutations";
  75.  
  76. Permutations.isFinite           := false;
  77. Permutations.size               := "infinity";
  78.  
  79. Permutations.operations         := PermutationsOps;
  80.  
  81.  
  82. #############################################################################
  83. ##
  84. #F  PermutationsOps.Cycle(<g>,<d>)  . .  orbit of a point under a permutation
  85. ##
  86. PermutationsOps.Cycle := function ( g, d, opr )
  87.     local   cyc;
  88.  
  89.     # standard operation on integers
  90.     if   opr = OnPoints  and IsInt( d )  then
  91.         cyc := CyclePermInt( g, d );
  92.  
  93.     # other operation
  94.     else
  95.         cyc := GroupElementsOps.Cycle( g, d, opr );
  96.  
  97.     fi;
  98.  
  99.     # return the cycle <cyc>
  100.     return cyc;
  101. end;
  102.  
  103.  
  104. #############################################################################
  105. ##
  106. #F  PermutationsOps.CycleLength(<g>,<d>)  . . . .  length of orbit of a point
  107. #F                                                        under a permutation
  108. ##
  109. PermutationsOps.CycleLength := function ( g, d, opr )
  110.     local   len;
  111.  
  112.     # standard operation on integers
  113.     if  opr = OnPoints  and IsInt( d )  then
  114.         len := CycleLengthPermInt( g, d );
  115.  
  116.     # other operation
  117.     else
  118.         len := GroupElementsOps.CycleLength( g, d, opr );
  119.  
  120.     fi;
  121.  
  122.     # return the length <len>
  123.     return len;
  124. end;
  125.  
  126.  
  127. #############################################################################
  128. ##
  129. #F  PermutationsOps.Cycles(<g>,<D>)   cycles of a domain under an permutation
  130. ##
  131. #N  26-Apr-91 martin 'CyclesPerm' should be internal
  132. ##
  133. PermutationsOps.Cycles := function ( g, D, opr )
  134.     local   cycs,       # cycles, result
  135.             cyc;        # cycle
  136.  
  137.     # standard operation
  138.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  139.  
  140.         # make a sorted copy of the domain <D>
  141.         D := Set( D );
  142.  
  143.         # compute the cycles <cycs>
  144.         cycs := [];
  145.         while D <> []  do
  146.             cyc := CyclePermInt( g, D[1] );
  147.             Add( cycs, cyc );
  148.             SubtractSet( D, cyc );
  149.         od;
  150.  
  151.     # other operation
  152.     else
  153.         cycs := GroupElementsOps.Cycles( g, D, opr );
  154.  
  155.     fi;
  156.  
  157.     # return the cycles <cycs>
  158.     return cycs;
  159. end;
  160.  
  161.  
  162. #############################################################################
  163. ##
  164. #F  PermutationsOps.CycleLengths(<g>,<D>) . . . . . . . lengths of the cycles
  165. #F                                                           of a permutation
  166. ##
  167. #N  26-Apr-91 martin 'CycleLengthsPermInt' should be internal
  168. ##
  169. PermutationsOps.CycleLengths := function ( g, D, opr )
  170.     local   lens,       # cycle lengths, result
  171.             cyc;        # cycle
  172.  
  173.     # standard operation
  174.     if   opr = OnPoints  and ForAll( D, IsInt )  then
  175.  
  176.         # make a sorted copy of the domain <D>
  177.         D := Set( D );
  178.  
  179.         # compute the cycles <cycs>
  180.         lens := [];
  181.         while D <> []  do
  182.             cyc := CyclePermInt( g, D[1] );
  183.             Add( lens, Length(cyc) );
  184.             SubtractSet( D, cyc );
  185.         od;
  186.  
  187.     # other operation
  188.     else
  189.         lens := GroupElementsOps.CycleLengths( g, D, opr );
  190.  
  191.     fi;
  192.  
  193.     # return the lengths <lens>
  194.     return lens;
  195. end;
  196.  
  197.  
  198. #############################################################################
  199. ##
  200. #F  CycleStructurePerm( <perm> )  . . . . . . . . .  length of cycles of perm
  201. ##
  202. CycleStructurePerm := function ( perm )
  203.     local   cys, dom, len, cyc;
  204.     if perm = () then
  205.         cys := [];
  206.     else
  207.         dom := [1..LargestMovedPointPerm(perm)];
  208.         cys := [];
  209.         while dom <> []  do
  210.             cyc := CyclePermInt( perm, dom[1] );
  211.             len := Length(cyc) - 1;
  212.             if 0 < len  then
  213.                 if IsBound(cys[len])  then
  214.                     cys[len] := cys[len]+1;
  215.                 else
  216.                     cys[len] := 1;
  217.                 fi;
  218.             fi;
  219.             SubtractSet( dom, cyc );
  220.         od;
  221.     fi;
  222.     return cys;
  223. end;
  224.  
  225.  
  226. #############################################################################
  227. ##
  228. #F  PermutationsOps.Permutation(<g>,<D>)  . . .  permutation of a permutation
  229. #F                                                                on a domain
  230. ##
  231. PermutationsOps.Permutation := function ( g, D, opr )
  232.     local   prm,        # permutation, result
  233.             pos,        # position of point in D
  234.             inc,        # increment if <D> is a range
  235.             i;          # loop variable
  236.  
  237.     # standard operation
  238.     if   opr = OnPoints  then
  239.  
  240.         # standard operation on a range
  241.         if IsRange( D )  then
  242.             InfoOperation1("#I  PermutationPerm(<g>,<range>)\c");
  243.             if Length( D ) = 1  then
  244.                inc := 1;
  245.             else
  246.                inc := D[2] - D[1];
  247.             fi;
  248.  
  249.             # compute the permutation <prm>
  250.             prm := [];
  251.             for i  in [1..Length(D)]  do
  252.                 prm[i] := (D[i]^g - D[1]) / inc + 1;
  253.             od;
  254.  
  255.             prm := PermList( prm );
  256.             InfoOperation1("\r#I  PermutationPerm(<g>,<range>) returns\n");
  257.  
  258.         # standard operation on another list of integers
  259.         elif D = []  or ForAll( D, IsInt )  then
  260.             InfoOperation1("#I  PermutationPerm(<g>,<D>)\c");
  261.  
  262.             # first find the position of every point of <D>
  263.             pos := [];
  264.             for i  in [1..Length(D)]  do
  265.                 pos[D[i]] := i;
  266.             od;
  267.  
  268.             # then compute the permutation <prm>
  269.             prm := [];
  270.             for i  in [1..Length(D)]  do
  271.                 prm[i] := pos[ D[i]^g ];
  272.             od;
  273.  
  274.             prm := PermList( prm );
  275.             InfoOperation1("\r#I  PermutationPerm(<g>,<D>) returns\n");
  276.  
  277.         # standard operation on a list of nonintegers
  278.         else
  279.             prm := GroupElementsOps.Permutation( g, D, opr );
  280.         fi;
  281.  
  282.     # other operation
  283.     else
  284.         prm := GroupElementsOps.Permutation( g, D, opr );
  285.  
  286.     fi;
  287.  
  288.     # return the permutation <prm>
  289.     return prm;
  290. end;
  291.  
  292.  
  293. #############################################################################
  294. ##
  295. #F  SmallestMovedPointPerm( <g> ) . . . smallest point moved by a permutation
  296. ##
  297. SmallestMovedPointPerm := function ( g )
  298.     local   p;
  299.     if g = ()  then
  300.         Error("<g> must not be the identity");
  301.     else
  302.         p := 1;
  303.         while p^g = p  do
  304.             p := p + 1;
  305.         od;
  306.     fi;
  307.     return p;
  308. end;
  309.  
  310.  
  311. #############################################################################
  312. ##
  313. #F  ListPerm( <g> ) . . . . . . . . . . . . . list of images of a permutation
  314. ##
  315. ListPerm := function ( g )
  316.     local   lst,  p;
  317.  
  318.     lst := [];
  319.     if g <> ()  then
  320.         for p  in [ 1 .. LargestMovedPointPerm(g) ]  do
  321.             lst[p] := p ^ g;
  322.         od;
  323.     fi;
  324.  
  325.     return lst;
  326. end;
  327.  
  328.  
  329. #############################################################################
  330. ##
  331. #F  MappingPermListList(<src>,<dst>)  permutation mapping one list to another
  332. ##
  333. MappingPermListList := function( src, dst )
  334.  
  335.     if not IsList(src) or not IsList(dst) or Length(src) <> Length(dst)  then
  336.        Error("usage: MappingPermListList( <lst1>, <lst2> )");
  337.     fi;
  338.  
  339.     if Length(src) = 0  then
  340.         return ();
  341.     fi;
  342.  
  343.     src := Concatenation( src, Difference( [1..Maximum(src)], src ) );
  344.     dst := Concatenation( dst, Difference( [1..Maximum(dst)], dst ) );
  345.  
  346.     return PermList( src ) mod PermList( dst );
  347. end;
  348.  
  349.  
  350. ##############################################################################
  351. ##
  352. #F  RestrictedPerm(<g>,<D>) . restriction of a permutation to an invariant set
  353. ##
  354. RestrictedPerm := function( g, D )
  355.     local   res, d;
  356.  
  357.     # check the arguments
  358.     if not IsPerm( g )  then
  359.         Error("<g> must be a permutation");
  360.     elif not IsList( D )  then
  361.         Error("<D> must be a list");
  362.     fi;
  363.  
  364.     # special case for the identity
  365.     if g = ()  then return ();  fi;
  366.  
  367.     # compute the restricted permutation <res>
  368.     res := [ 1 .. Maximum( LargestMovedPointPerm(g), Maximum(D) ) ];
  369.     for d  in D  do
  370.         if not d^g in D  then
  371.             Error("<D> must be invariant under the action of <g>");
  372.         fi;
  373.         res[d] := d^g;
  374.     od;
  375.  
  376.     # return the restricted permutation <res>
  377.     return PermList( res );
  378. end;
  379.  
  380.  
  381. #############################################################################
  382. ##
  383. #F  PermutationsOps.CyclicGroup(<P>,<n>)  . . . . .  cyclic permutation group
  384. #F  PermutationsOps.AbelianGroup(<P>,<ords>)  . . . abelian permutation group
  385. #F  PermutationsOps.ElementaryAbelianGroup(<P>,<n>) . . .  elementary abelian
  386. #F                                                          permutation group
  387. #F  PermutationsOps.DihedralGroup(<P>,<n>)  . . .  dihedral permutation group
  388. #F  PermutationsOps.PolyhedralGroup(<P>,<p>,<q>) polyhedral permutation group
  389. #F  PermutationsOps.AlternatingGroup(<P>,<n>) . alternating permutation group
  390. #F  PermutationsOps.SymmetricGroup(<P>,<n>) . . . symmetric permutation group
  391. ##
  392. PermutationsOps.CyclicGroup := function ( P, n )
  393.     return PermGroupLib( "CyclicGroup", n );
  394. end;
  395.  
  396. PermutationsOps.AbelianGroup := function ( P, ords )
  397.     return PermGroupLib( "AbelianGroup", ords );
  398. end;
  399.  
  400. PermutationsOps.ElementaryAbelianGroup := function ( P, n )
  401.     return PermGroupLib( "ElementaryAbelianGroup", n );
  402. end;
  403.  
  404. PermutationsOps.DihedralGroup := function ( P, n )
  405.     return PermGroupLib( "DihedralGroup", n );
  406. end;
  407.  
  408. PermutationsOps.PolyhedralGroup := function ( P, p, q )
  409.     return PermGroupLib( "PolyhedralGroup", p, q );
  410. end;
  411.  
  412. PermutationsOps.AlternatingGroup := function ( P, n )
  413.     return PermGroupLib( "AlternatingGroup", n );
  414. end;
  415.  
  416. PermutationsOps.SymmetricGroup := function ( P, n )
  417.     return PermGroupLib( "SymmetricGroup", n );
  418. end;
  419.  
  420.  
  421. #############################################################################
  422. ##
  423. ##  other functions are in 'permgrp.g'
  424. ##
  425. ##  AUTO( ReadLib("permgrp"),
  426. ##      PermutationsOps.Group )
  427. ##
  428. ReadLib("permgrp");
  429.  
  430.  
  431. #############################################################################
  432. ##
  433. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  434. ##
  435. ##  Local Variables:
  436. ##  mode:               outline
  437. ##  outline-regexp:     "#F\\|#V\\|#E"
  438. ##  fill-column:        73
  439. ##  fill-prefix:        "##  "
  440. ##  eval:               (hide-body)
  441. ##  End:
  442. ##
  443.  
  444.  
  445.  
  446.