1#############################################################################
2##
3##  This file is part of GAP, a system for computational discrete algebra.
4##  This file's authors include Thomas Breuer, Frank Celler.
5##
6##  Copyright of GAP belongs to its developers, whose names are too numerous
7##  to list here. Please refer to the COPYRIGHT file for details.
8##
9##  SPDX-License-Identifier: GPL-2.0-or-later
10##
11##  This file deals with permutations.
12##
13
14#############################################################################
15##
16##  <#GAPDoc Label="[1]{permutat}">
17##  Internally, &GAP; stores a permutation as a list of the <M>d</M> images
18##  of the integers <M>1, \ldots, d</M>, where the <Q>internal degree</Q>
19##  <M>d</M> is the largest integer moved by the permutation or bigger.
20##  When a permutation is read in in cycle notation, <M>d</M> is always set
21##  to the largest moved integer, but a bigger <M>d</M> can result from a
22##  multiplication of two permutations, because the product is not shortened
23##  if it fixes&nbsp;<M>d</M>.
24##  The images are stored all as <M>16</M>-bit integers or all as
25##  <M>32</M>-bit integers, depending on whether <M>d \leq 65536</M> or not.
26##  For example, if <M>m\geq 65536</M>, the permutation
27##  <M>(1, 2, \ldots, m)</M> has internal degree <M>d=m</M> and takes
28##  <M>4m</M> bytes of memory for storage. But --- since the internal degree
29##  is not reduced  --- this
30##  means that the identity permutation <C>()</C> calculated as
31##  <M>(1, 2, \ldots, m) * (1, 2, \ldots, m)^{{-1}}</M> also
32##  takes <M>4m</M> bytes of storage.
33##  It can take even more because the internal list has sometimes room for
34##  more than <M>d</M> images.
35##  <P/> On 32-bit systems, the limit on the degree of permutations is, for
36##  technical reasons, <M>2^{28}-1</M>.
37##  On 64-bit systems, it is <M>2^{32}-1</M> because only a 32-bit integer
38##  is used to represent each image internally. Error messages should be given
39##  if any command would require creating a permutation exceeding this limit.
40##  <P/>
41##  The operation <Ref Oper="RestrictedPerm"/> reduces the storage degree of
42##  its result and therefore can be used to save memory if intermediate
43##  calculations in large degree result in a small degree result.
44##  <P/>
45##  Permutations do not belong to a specific group.
46##  That means that one can work with permutations without defining
47##  a permutation group that contains them.
48##  <P/>
49##  <Example><![CDATA[
50##  gap> (1,2,3);
51##  (1,2,3)
52##  gap> (1,2,3) * (2,3,4);
53##  (1,3)(2,4)
54##  gap> 17^(2,5,17,9,8);
55##  9
56##  gap> OnPoints(17,(2,5,17,9,8));
57##  9
58##  ]]></Example>
59##  <P/>
60##  The operation <Ref Oper="Permuted"/> can be used to permute the entries
61##  of a list according to a permutation.
62##  <#/GAPDoc>
63##
64
65
66#############################################################################
67##
68#C  IsPerm( <obj> )
69##
70##  <#GAPDoc Label="IsPerm">
71##  <ManSection>
72##  <Filt Name="IsPerm" Arg='obj' Type='Category'/>
73##
74##  <Description>
75##  Each <E>permutation</E> in &GAP; lies in the category
76##  <Ref Filt="IsPerm"/>.
77##  Basic operations for permutations are
78##  <Ref Attr="LargestMovedPoint" Label="for a permutation"/>,
79##  multiplication of two permutations via <C>*</C>,
80##  and exponentiation <C>^</C> with first argument a positive integer
81##  <M>i</M> and second argument a permutation <M>\pi</M>,
82##  the result being the image <M>i^{\pi}</M> of the point <M>i</M>
83##  under <M>\pi</M>.
84##  <!-- other arith. ops.?-->
85##  </Description>
86##  </ManSection>
87##  <#/GAPDoc>
88##
89DeclareCategoryKernel( "IsPerm",
90    IsMultiplicativeElementWithInverse and IsAssociativeElement and
91    IsFiniteOrderElement,
92    IS_PERM );
93
94
95#############################################################################
96##
97#C  IsPermCollection( <obj> )
98#C  IsPermCollColl( <obj> )
99##
100##  <#GAPDoc Label="IsPermCollection">
101##  <ManSection>
102##  <Filt Name="IsPermCollection" Arg='obj' Type='Category'/>
103##  <Filt Name="IsPermCollColl" Arg='obj' Type='Category'/>
104##
105##  <Description>
106##  are the categories for collections of permutations and collections of
107##  collections of permutations, respectively.
108##  </Description>
109##  </ManSection>
110##  <#/GAPDoc>
111##
112DeclareCategoryCollections( "IsPerm" );
113DeclareCategoryCollections( "IsPermCollection" );
114
115
116#############################################################################
117##
118#F  SmallestGeneratorPerm( <perm> )
119##
120##  <#GAPDoc Label="SmallestGeneratorPerm">
121##  <ManSection>
122##  <Attr Name="SmallestGeneratorPerm" Arg='perm'/>
123##
124##  <Description>
125##  is the smallest permutation that generates the same cyclic group
126##  as the permutation <A>perm</A>.
127##  This is very efficient, even when <A>perm</A> has large order.
128##  <Example><![CDATA[
129##  gap> SmallestGeneratorPerm( (1,4,3,2) );
130##  (1,2,3,4)
131##  ]]></Example>
132##  </Description>
133##  </ManSection>
134##  <#/GAPDoc>
135##
136DeclareAttribute( "SmallestGeneratorPerm",IsPerm);
137
138InstallMethod( SmallestGeneratorPerm,"for internally represented permutation",
139    [ IsPerm and IsInternalRep ],
140    SMALLEST_GENERATOR_PERM );
141
142
143#############################################################################
144##
145#A  SmallestMovedPoint( <perm> )
146#A  SmallestMovedPoint( <C> )
147##
148##  <#GAPDoc Label="SmallestMovedPoint">
149##  <ManSection>
150##  <Attr Name="SmallestMovedPoint" Arg='perm' Label="for a permutation"/>
151##  <Attr Name="SmallestMovedPoint" Arg='C'
152##   Label="for a list or collection of permutations"/>
153##
154##  <Description>
155##  is the smallest positive integer that is moved by <A>perm</A>
156##  if such an integer exists, and <Ref Var="infinity"/> if
157##  <A>perm</A> is the identity.
158##  For <A>C</A> a collection or list of permutations,
159##  the smallest value of
160##  <Ref Attr="SmallestMovedPoint" Label="for a permutation"/> for the
161##  elements of <A>C</A> is returned
162##  (and <Ref Var="infinity"/> if <A>C</A> is empty).
163##  </Description>
164##  </ManSection>
165##  <#/GAPDoc>
166##
167DeclareAttribute( "SmallestMovedPoint", IsPerm );
168DeclareAttribute( "SmallestMovedPoint", IsPermCollection );
169DeclareAttribute( "SmallestMovedPoint", IsList and IsEmpty );
170
171DeclareSynonymAttr( "SmallestMovedPointPerm", SmallestMovedPoint );
172
173
174#############################################################################
175##
176#A  LargestMovedPoint( <perm> ) . . . . . . . . . . . . . . largest point
177#A  LargestMovedPoint( <C> )
178##
179##  <#GAPDoc Label="LargestMovedPoint">
180##  <ManSection>
181##  <Attr Name="LargestMovedPoint" Arg='perm' Label="for a permutation"/>
182##  <Attr Name="LargestMovedPoint" Arg='C'
183##   Label="for a list or collection of permutations"/>
184##
185##  <Description>
186##  For a permutation <A>perm</A>, this attribute contains
187##  the largest positive integer which is moved by <A>perm</A>
188##  if such an integer exists, and <C>0</C> if <A>perm</A> is the identity.
189##  For <A>C</A> a collection or list of permutations,
190##  the largest value of
191##  <Ref Attr="LargestMovedPoint" Label="for a permutation"/> for the
192##  elements of <A>C</A> is returned (and <C>0</C> if <A>C</A> is empty).
193##  </Description>
194##  </ManSection>
195##  <#/GAPDoc>
196##
197DeclareAttribute( "LargestMovedPoint", IsPerm );
198DeclareAttribute( "LargestMovedPoint", IsPermCollection );
199DeclareAttribute( "LargestMovedPoint", IsList and IsEmpty );
200
201DeclareSynonymAttr( "LargestMovedPointPerm", LargestMovedPoint );
202
203
204#############################################################################
205##
206#A  NrMovedPoints( <perm> )
207#A  NrMovedPoints( <C> )
208##
209##  <#GAPDoc Label="NrMovedPoints">
210##  <ManSection>
211##  <Attr Name="NrMovedPoints" Arg='perm' Label="for a permutation"/>
212##  <Attr Name="NrMovedPoints" Arg='C'
213##   Label="for a list or collection of permutations"/>
214##
215##  <Description>
216##  is the number of positive integers that are moved by <A>perm</A>,
217##  respectively by at least one element in the collection <A>C</A>.
218##  (The actual moved points are returned by
219##  <Ref Attr="MovedPoints" Label="for a permutation"/>.)
220##  <Example><![CDATA[
221##  gap> SmallestMovedPointPerm((4,5,6)(7,2,8));
222##  2
223##  gap> LargestMovedPointPerm((4,5,6)(7,2,8));
224##  8
225##  gap> NrMovedPointsPerm((4,5,6)(7,2,8));
226##  6
227##  gap> MovedPoints([(2,3,4),(7,6,3),(5,47)]);
228##  [ 2, 3, 4, 5, 6, 7, 47 ]
229##  gap> NrMovedPoints([(2,3,4),(7,6,3),(5,47)]);
230##  7
231##  gap> SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
232##  2
233##  gap> LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]);
234##  47
235##  gap> LargestMovedPoint([()]);
236##  0
237##  ]]></Example>
238##  </Description>
239##  </ManSection>
240##  <#/GAPDoc>
241##
242DeclareAttribute( "NrMovedPoints", IsPerm );
243DeclareAttribute( "NrMovedPoints", IsPermCollection );
244DeclareAttribute( "NrMovedPoints", IsList and IsEmpty );
245
246DeclareSynonymAttr( "NrMovedPointsPerm", NrMovedPoints );
247DeclareSynonymAttr( "DegreeAction", NrMovedPoints );
248DeclareSynonymAttr( "DegreeOperation", NrMovedPoints );
249
250
251#############################################################################
252##
253#A  MovedPoints( <perm> )
254#A  MovedPoints( <C> )
255##
256##  <#GAPDoc Label="MovedPoints">
257##  <ManSection>
258##  <Attr Name="MovedPoints" Arg='perm' Label="for a permutation"/>
259##  <Attr Name="MovedPoints" Arg='C'
260##   Label="for a list or collection of permutations"/>
261##
262##  <Description>
263##  is the proper set of the positive integers moved by at least one
264##  permutation in the collection <A>C</A>, respectively by the permutation
265##  <A>perm</A>.
266##  </Description>
267##  </ManSection>
268##  <#/GAPDoc>
269##
270DeclareAttribute( "MovedPoints", IsPerm);
271DeclareAttribute( "MovedPoints", IsPermCollection );
272DeclareAttribute( "MovedPoints", IsList and IsEmpty );
273
274
275#############################################################################
276##
277#A  SignPerm( <perm> )
278##
279##  <#GAPDoc Label="SignPerm">
280##  <ManSection>
281##  <Attr Name="SignPerm" Arg='perm'/>
282##
283##  <Description>
284##  The <E>sign</E> of a permutation <A>perm</A> is defined as <M>(-1)^k</M>
285##  where <M>k</M> is the number of cycles of <A>perm</A> of even length.
286##  <P/>
287##  The sign is a homomorphism from the symmetric group onto the
288##  multiplicative  group <M>\{ +1, -1 \}</M>,
289##  the kernel of which is the alternating group.
290##  </Description>
291##  </ManSection>
292##  <#/GAPDoc>
293##
294DeclareAttribute( "SignPerm", IsPerm );
295
296InstallMethod( SignPerm,
297    "for internally represented permutation",
298    [ IsPerm and IsInternalRep ],
299    SIGN_PERM );
300
301
302#############################################################################
303##
304#A  CycleStructurePerm( <perm> )  . . . . . . . . . . . . . . cycle structure
305##
306##  <#GAPDoc Label="CycleStructurePerm">
307##  <ManSection>
308##  <Attr Name="CycleStructurePerm" Arg='perm'/>
309##
310##  <Description>
311##  is the cycle structure (i.e. the numbers of cycles of different lengths)
312##  of the permutation <A>perm</A>.
313##  This is encoded in a list <M>l</M> in the following form:
314##  The <M>i</M>-th entry of <M>l</M> contains the number of cycles of
315##  <A>perm</A> of length <M>i+1</M>.
316##  If <A>perm</A> contains no cycles of length <M>i+1</M> it is not
317##  bound.
318##  Cycles of length 1 are ignored.
319##  <Example><![CDATA[
320##  gap> SignPerm((1,2,3)(4,5));
321##  -1
322##  gap> CycleStructurePerm((1,2,3)(4,5,9,7,8));
323##  [ , 1,, 1 ]
324##  ]]></Example>
325##  </Description>
326##  </ManSection>
327##  <#/GAPDoc>
328##
329DeclareAttribute( "CycleStructurePerm", IsPerm );
330
331
332#############################################################################
333##
334#R  IsPerm2Rep  . . . . . . . . . . . . . .  permutation with 2 bytes entries
335##
336##  <ManSection>
337##  <Filt Name="IsPerm2Rep" Arg='obj' Type='Representation'/>
338##
339##  <Description>
340##  </Description>
341##  </ManSection>
342##
343DeclareRepresentation( "IsPerm2Rep", IsInternalRep, [] );
344
345
346#############################################################################
347##
348#R  IsPerm4Rep  . . . . . . . . . . . . . .  permutation with 4 bytes entries
349##
350##  <ManSection>
351##  <Filt Name="IsPerm4Rep" Arg='obj' Type='Representation'/>
352##
353##  <Description>
354##  </Description>
355##  </ManSection>
356##
357DeclareRepresentation( "IsPerm4Rep", IsInternalRep, [] );
358
359
360#############################################################################
361##
362#V  PermutationsFamily  . . . . . . . . . . . . .  family of all permutations
363##
364##  <#GAPDoc Label="PermutationsFamily">
365##  <ManSection>
366##  <Fam Name="PermutationsFamily"/>
367##
368##  <Description>
369##  is the family of all permutations.
370##  </Description>
371##  </ManSection>
372##  <#/GAPDoc>
373##
374BIND_GLOBAL( "PermutationsFamily",
375    NewFamily( "PermutationsFamily",
376    IsPerm,CanEasilySortElements,CanEasilySortElements ) );
377#    IsMultiplicativeElementWithOne,CanEasilySortElements,CanEasilySortElements ) );
378
379
380#############################################################################
381##
382#V  TYPE_PERM2  . . . . . . . . . .  type of permutation with 2 bytes entries
383##
384##  <ManSection>
385##  <Var Name="TYPE_PERM2"/>
386##
387##  <Description>
388##  </Description>
389##  </ManSection>
390##
391BIND_GLOBAL( "TYPE_PERM2",
392    NewType( PermutationsFamily, IsPerm and IsPerm2Rep ) );
393
394
395#############################################################################
396##
397#V  TYPE_PERM4  . . . . . . . . . .  type of permutation with 4 bytes entries
398##
399##  <ManSection>
400##  <Var Name="TYPE_PERM4"/>
401##
402##  <Description>
403##  </Description>
404##  </ManSection>
405##
406BIND_GLOBAL( "TYPE_PERM4",
407    NewType( PermutationsFamily, IsPerm and IsPerm4Rep ) );
408
409
410#############################################################################
411##
412#v  One . . . . . . . . . . . . . . . . . . . . . . . . .  one of permutation
413##
414SetOne( PermutationsFamily, () );
415
416
417#############################################################################
418##
419#F  PermList( <list> )
420##
421##  <#GAPDoc Label="PermList">
422##  <ManSection>
423##  <Func Name="PermList" Arg='list'/>
424##
425##  <Description>
426##  is the permutation <M>\pi</M> that moves points as described by the
427##  list <A>list</A>.
428##  That means that <M>i^{\pi} =</M> <A>list</A><C>[</C><M>i</M><C>]</C> if
429##  <M>i</M> lies between <M>1</M> and the length of <A>list</A>,
430##  and <M>i^{\pi} = i</M> if <M>i</M> is
431##  larger than the length of the list <A>list</A>.
432##  <Ref Func="PermList"/> will return <K>fail</K>
433##  if <A>list</A> does not define a permutation,
434##  i.e., if <A>list</A> is not dense,
435##  or if <A>list</A> contains a positive integer twice,
436##  or if <A>list</A> contains an
437##  integer not in the range <C>[ 1 .. Length( <A>list</A> ) ]</C>,
438##  of if <A>list</A> contains non-integer entries, etc.
439##  </Description>
440##  </ManSection>
441##  <#/GAPDoc>
442##
443
444
445#############################################################################
446##
447#F  ListPerm( <perm>[, <length>] )  . . . . . . . . . . . . .  list of images
448##
449##  <#GAPDoc Label="ListPerm">
450##  <ManSection>
451##  <Func Name="ListPerm" Arg='perm[, length]'/>
452##
453##  <Description>
454##  is a list <M>l</M> that contains the images of the positive integers
455##  under the permutation <A>perm</A>.
456##  That means that
457##  <M>l</M><C>[</C><M>i</M><C>]</C> <M>= i</M><C>^</C><A>perm</A>,
458##  where <M>i</M> lies between 1
459##  and the largest point moved by <A>perm</A>
460##  (see&nbsp;<Ref Attr="LargestMovedPoint" Label="for a permutation"/>).
461##  <P/>
462##  An optional second argument specifies the length of the desired list.
463##  </Description>
464##  </ManSection>
465##  <#/GAPDoc>
466##
467BIND_GLOBAL( "ListPerm", function( arg )
468    local n;
469    if Length(arg)=2 then
470        n := arg[2];
471    else
472        n := LargestMovedPoint(arg[1]);
473    fi;
474    if IsOne(arg[1]) then
475        return [1..n];
476    else
477        return OnTuples( [1..n], arg[1] );
478    fi;
479end );
480
481
482#############################################################################
483##
484#F  CycleFromList( <list> )  . . . . . . . . . . . cycle defined from a list
485##
486##  <#GAPDoc Label="CycleFromList">
487##  <ManSection>
488##  <Func Name="CycleFromList" Arg='list'/>
489##
490##  <Description>
491##  For the given dense, duplicate-free list of positive integers
492##  <M>[a_1, a_2, ..., a_n]</M>
493##  return the <M>n</M>-cycle <M>(a_1,a_2,...,a_n)</M>. For the empty list
494##  the trivial permutation <M>()</M> is returned.
495##  <P/>
496##  If the given <A>list</A> contains duplicates or holes, return <K>fail</K>.
497##  <P/>
498##  <Example><![CDATA[
499##  gap> CycleFromList( [1,2,3,4] );
500##  (1,2,3,4)
501##  gap> CycleFromList( [3,2,6,4,5] );
502##  (2,6,4,5,3)
503##  gap> CycleFromList( [2,3,2] );
504##  fail
505##  gap> CycleFromList( [1,,3] );
506##  fail
507##  ]]></Example>
508##  </Description>
509##  </ManSection>
510##  <#/GAPDoc>
511##
512BIND_GLOBAL( "CycleFromList", function( list )
513    local max, images, set, i;
514
515    # Trivial case
516    if Length(list) = 0 then
517        return ();
518    fi;
519
520    if ForAny( list, i -> not IsPosInt(i) ) then
521        Error("CycleFromList: List must only contain positive integers.");
522    fi;
523
524    set := Set(list);
525    if Length(set) <> Length(list) then
526        # we found duplicates (or list was not dense)
527        return fail;
528    fi;
529    max := Maximum( set );
530    images := [1..max];
531    for i in [1..Length(list)-1] do
532        images[ list[i] ] := list[i+1];
533    od;
534    images[ list[Length(list)] ] := list[1];
535
536    return PermList(images);
537end );
538
539
540#############################################################################
541##
542#O  RestrictedPerm(<perm>,<list>)  restriction of a perm. to an invariant set
543#O  RestrictedPermNC(<perm>,<list>)  restriction of a perm. to an invariant set
544##
545##  <#GAPDoc Label="RestrictedPerm">
546##  <ManSection>
547##  <Oper Name="RestrictedPerm" Arg='perm, list'/>
548##  <Oper Name="RestrictedPermNC" Arg='perm, list'/>
549##
550##  <Description>
551##  <Ref Oper="RestrictedPerm"/> returns the new permutation
552##  that acts on the points in the list <A>list</A> in the same way as
553##  the permutation <A>perm</A>,
554##  and that fixes those points that are not in <A>list</A>. The resulting
555##  permutation is stored internally of degree given by the maximal entry of
556##  <A>list</A>.
557##  <A>list</A> must be a list of positive integers such that for each
558##  <M>i</M> in <A>list</A> the image <M>i</M><C>^</C><A>perm</A> is also in
559##  <A>list</A>,
560##  i.e., <A>list</A> must be the union of cycles of <A>perm</A>.
561##  <P/>
562##  <Ref Oper="RestrictedPermNC"/> does not check whether <A>list</A>
563##  is a union of cycles.
564##  <P/>
565##  <Example><![CDATA[
566##  gap> ListPerm((3,4,5));
567##  [ 1, 2, 4, 5, 3 ]
568##  gap> PermList([1,2,4,5,3]);
569##  (3,4,5)
570##  gap> MappingPermListList([2,5,1,6],[7,12,8,2]);
571##  (1,8,5,12,6,2,7)
572##  gap> RestrictedPerm((1,2)(3,4),[3..5]);
573##  (3,4)
574##  ]]></Example>
575##  </Description>
576##  </ManSection>
577##  <#/GAPDoc>
578##
579DeclareOperation( "RestrictedPerm", [ IsPerm, IsList ] );
580DeclareOperation( "RestrictedPermNC", [ IsPerm, IsList ] );
581
582InstallMethod(RestrictedPermNC,"kernel method",true,
583  [IsPerm and IsInternalRep, IsList],0,
584function(g,D)
585local p;
586  p:=RESTRICTED_PERM(g,D,false);
587  if p=fail then
588    Error("<g> must be a permutation and <D> a plain list or range,\n",
589	  "   consisting of a union of cycles of <g>");
590  fi;
591  return p;
592end);
593
594InstallMethod( RestrictedPerm,"use kernel method, test",true,
595  [IsPerm and IsInternalRep, IsList],0,
596function(g,D)
597  local p;
598  p:=RESTRICTED_PERM(g,D,true);
599  if p=fail then
600    Error("<g> must be a permutation and <D> a plain list or range,\n",
601	  "   consisting of a union of cycles of <g>");
602  fi;
603  return p;
604end);
605
606#############################################################################
607##
608#F  MappingPermListList( <src>, <dst> ) . . perm. mapping one list to another
609##
610##  <#GAPDoc Label="MappingPermListList">
611##  <ManSection>
612##  <Func Name="MappingPermListList" Arg='src, dst'/>
613##
614##  <Description>
615##  Let <A>src</A> and <A>dst</A> be lists of positive integers of the same
616##  length, such that there is a permutation <M>\pi</M> such that
617##  <C>OnTuples(<A>src</A>,</C> <M>\pi</M><C>) = <A>dst</A></C>.
618##  <Ref Func="MappingPermListList"/> returns the permutation <C>p</C> from the
619##  previous sentence, i.e.  <A>src</A><C>[</C><M>i</M><C>]^</C><M>p =</M>
620##  <A>dst</A><C>[</C><M>i</M><C>]</C>.
621##  The permutation <M>\pi</M> fixes any point which is not in <A>src</A> or
622##  <A>dst</A>.
623##  If there are several such permutations, it is not specified which of them
624##  <Ref Func="MappingPermListList"/> returns. If there is no such
625##  permutation, then <Ref Func="MappingPermListList"/> returns <K>fail</K>.
626##  </Description>
627##  </ManSection>
628##  <#/GAPDoc>
629##
630
631#############################################################################
632##
633#m  SmallestMovedPoint( <perm> )  . . . . . . . . . . .  for permutations
634##
635InstallMethod( SmallestMovedPoint,
636    "for a permutation",
637    [ IsPerm ],
638    function( p )
639    local   i;
640
641    if IsOne(p)  then
642        return infinity;
643    fi;
644    i := 1;
645    while i ^ p = i  do
646        i := i + 1;
647    od;
648    return i;
649end );
650
651
652#############################################################################
653##
654#m  LargestMovedPoint( <perm> ) . . . . . . . .  for internal permutation
655##
656InstallMethod( LargestMovedPoint,
657    "for an internal permutation",
658    [ IsPerm and IsInternalRep ],
659    LARGEST_MOVED_POINT_PERM );
660
661
662#############################################################################
663##
664#m  NrMovedPoints( <perm> ) . . . . . . . . . . . . . . . for permutation
665##
666InstallMethod( NrMovedPoints,
667    "for a permutation",
668    [ IsPerm ],
669    function( perm )
670    local mov, pnt;
671    mov:= 0;
672    if not IsOne( perm ) then
673      for pnt in [ SmallestMovedPoint( perm )
674                   .. LargestMovedPoint( perm ) ] do
675        if pnt ^ perm <> pnt then
676          mov:= mov + 1;
677        fi;
678      od;
679    fi;
680    return mov;
681    end );
682
683
684#############################################################################
685##
686#m  CycleStructurePerm( <perm> )  . . . . . . . . .  length of cycles of perm
687##
688InstallMethod( CycleStructurePerm, "internal", [ IsPerm and IsInternalRep],0,
689  CYCLE_STRUCT_PERM);
690
691InstallMethod( CycleStructurePerm, "generic method", [ IsPerm ],0,
692function ( perm )
693    local   cys,    # collected cycle lengths, result
694            degree, # degree of perm
695            mark,   # boolean list to mark elements already processed
696            i,j,    # loop variables
697            len,    # length of a cycle
698            cyc;    # a cycle of perm
699
700    if IsOne(perm) then
701        cys := [];
702    else
703        degree := LargestMovedPoint(perm);
704        mark := BlistList([1..degree], []);
705        cys := [];
706        for i in [1..degree] do
707            if not mark[i] then
708               cyc := CYCLE_PERM_INT( perm, i );
709               len := Length(cyc) - 1;
710               if 0 < len  then
711                  if IsBound(cys[len])  then
712                     cys[len] := cys[len]+1;
713                  else
714                     cys[len] := 1;
715                  fi;
716               fi;
717               for j in cyc do
718                  mark[j] := true;
719               od;
720            fi;
721        od;
722    fi;
723    return cys;
724end );
725
726
727#############################################################################
728##
729#m  String( <perm> )  . . . . . . . . . . . . . . . . . . . for a permutation
730##
731BIND_GLOBAL("DoStringPerm",function( perm,hint )
732local   str,  i,  j;
733
734  if IsOne( perm ) then
735      str := "()";
736  else
737      str := "";
738      for i  in [ 1 .. LargestMovedPoint( perm ) ]  do
739	  j := i ^ perm;
740	  while j > i  do j := j ^ perm;  od;
741	  if j = i and i ^ perm <> i  then
742	      Append( str, "(" );
743	      Append( str, String( i ) );
744	      j := i ^ perm;
745	      while j > i do
746		  Append( str, "," );
747		  if hint then Append(str,"\<\>"); fi;
748		  Append( str, String( j ) );
749		  j := j ^ perm;
750	      od;
751	      Append( str, ")" );
752	      if hint then Append(str,"\<\<\>\>"); fi;
753	  fi;
754      od;
755      if Length(str)>4 and str{[Length(str)-3..Length(str)]}="\<\<\>\>" then
756	str:=str{[1..Length(str)-4]}; # remove tailing line breaker
757      fi;
758      ConvertToStringRep( str );
759  fi;
760  return str;
761end );
762
763InstallMethod( String, "for a permutation", [ IsPerm ],function(perm)
764  return DoStringPerm(perm,false);
765end);
766
767InstallMethod( ViewString, "for a permutation", [ IsPerm ],function(perm)
768  return DoStringPerm(perm,true);
769end);
770
771
772
773
774#############################################################################
775##
776#M  Order( <perm> ) . . . . . . . . . . . . . . . . .  order of a permutation
777##
778InstallMethod( Order,
779    "for a permutation",
780    [ IsPerm ],
781    ORDER_PERM );
782
783
784#############################################################################
785##
786#O  DistancePerms( <perm1>, <perm2> ) . returns NrMovedPoints( <perm1>/<perm2> )
787##        but possibly faster
788##
789##  <#GAPDoc Label="DistancePerms">
790##  <ManSection>
791##  <Oper Name="DistancePerms" Arg="perm1, perm2"/>
792##
793##  <Description>
794##  returns the number of points for which <A>perm1</A> and <A>perm2</A>
795##  have different images. This should always produce the same result as
796##  <C>NrMovePoints(<A>perm1</A>/<A>perm2</A>)</C> but some methods may be
797##  much faster than this form, since no new permutation needs to be created.
798##  </Description>
799##  </ManSection>
800##  <#/GAPDoc>
801
802DeclareOperation( "DistancePerms", [IsPerm, IsPerm] );
803
804
805#############################################################################
806##
807#M  DistancePerms( <perm1>, <perm2> ) . returns NrMovedPoints( <perm1>/<perm2> )
808##    for kernel permutations
809##
810InstallMethod( DistancePerms, "for kernel permutations",
811        [ IsPerm and IsInternalRep, IsPerm and IsInternalRep ],
812        DISTANCE_PERMS);
813
814#############################################################################
815##
816#M  DistancePerms( <perm1>, <perm2> ) . returns NrMovedPoints( <perm1>/<perm2> )
817##    generic
818##
819
820InstallMethod( DistancePerms, "for general permutations",
821        [ IsPerm, IsPerm ],
822        function(x,y)
823    return NrMovedPoints(x/y); end);
824
825#############################################################################
826##
827#V  PERM_INVERSE_THRESHOLD . . . . cut off for when inverses are computed
828##                                 eagerly
829##
830##  <#GAPDoc Label="PERM_INVERSE_THRESHOLD">
831##  <ManSection>
832##  <Var Name="PERM_INVERSE_THRESHOLD"/>
833##
834##  <Description>
835##  For permutations of degree up to <C>PERM_INVERSE_THRESHOLD</C> whenever
836##  the inverse image of a point under a permutations is needed, the entire
837##  inverse is computed and stored. Otherwise, if the inverse is not stored,
838##  the point is traced around the cycle it is part of to find the inverse
839##  image. This takes time when it happens, and uses memory, but saves time
840##  on a variety of subsequent computations. This threshold can be adjusted
841##  by simply assigning to the variable. The default is 10000.
842##  </Description>
843##  </ManSection>
844##  <#/GAPDoc>
845
846PERM_INVERSE_THRESHOLD := 10000;
847
848
849
850#############################################################################
851##
852#m  ViewObj( <perm> )  . . . . . . . . . . . . . . . . . . . for a permutation
853##
854InstallMethod( ViewObj, "for a permutation", [ IsPerm ],
855function( perm )
856local dom,l,i,n,p,c;
857  dom:=[];
858  l:=LargestMovedPoint(perm);
859  i:=SmallestMovedPoint(perm);
860  n:=0;
861  while n<200 and i<l do
862    p:=i;
863    if p^perm<>p and not p in dom then
864      c:=false;
865      while not p in dom do
866	AddSet(dom,p);
867	n:=n+1;
868	# deliberately *no ugly blanks* printed!
869	if c then
870	  Print(",",p);
871	else
872	  Print(Concatenation("(",String(p)));
873	fi;
874	p:=p^perm;
875	c:=true;
876      od;
877      Print(")");
878    fi;
879    i:=i+1;
880  od;
881  if i<l and ForAny([i..l],j->j^perm<>j and not j in dom) then
882    Print("( [...] )");
883  elif i>l+1 then
884    Print("()");
885  fi;
886end );
887