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 <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 <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