Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

**GAP** offers a data type *permutation* to describe the elements of permutation groups.

The points on which permutations in **GAP** act are the positive integers up to a certain architecture dependent limit, and the image of a point i under a permutation p is written i^p, which is expressed as i`^`

p in **GAP**. (This action is also implemented by the function `OnPoints`

(41.2-1).) If i`^`

p is different from i, we say that i is *moved* by p, otherwise it is *fixed*. Permutations in **GAP** are entered and displayed in cycle notation, such as `(1,2,3)(4,5)`

.

The preimage of the point i under the permutation p can be computed as i`/`

p, without constructing the inverse of p.

For arithmetic operations for permutations and their precedence, see 31.12.

In the names of the **GAP** functions that deal with permutations, the word "Permutation" is usually abbreviated to "Perm", to save typing. For example, the category test function for permutations is `IsPerm`

(42.1-1).

Internally, **GAP** stores a permutation as a list of the d images of the integers 1, ..., d, where the "internal degree" d is the largest integer moved by the permutation or bigger. When a permutation is read in in cycle notation, d is always set to the largest moved integer, but a bigger d can result from a multiplication of two permutations, because the product is not shortened if it fixes d. The images are stored all as 16-bit integers or all as 32-bit integers, depending on whether d ≤ 65536 or not. For example, if m≥ 65536, the permutation (1, 2, ..., m) has internal degree d=m and takes 4m bytes of memory for storage. But --- since the internal degree is not reduced --- this means that the identity permutation `()`

calculated as (1, 2, ..., m) * (1, 2, ..., m)^{-1} also takes 4m bytes of storage. It can take even more because the internal list has sometimes room for more than d images.

The operation `RestrictedPerm`

(42.5-4) reduces the storage degree of its result and therefore can be used to save memory if intermediate calculations in large degree result in a small degree result.

Permutations do not belong to a specific group. That means that one can work with permutations without defining a permutation group that contains them.

gap> (1,2,3); (1,2,3) gap> (1,2,3) * (2,3,4); (1,3)(2,4) gap> 17^(2,5,17,9,8); 9 gap> OnPoints(17,(2,5,17,9,8)); 9

The operation `Permuted`

(21.20-18) can be used to permute the entries of a list according to a permutation.

`‣ IsPerm` ( obj ) | ( category ) |

Each *permutation* in **GAP** lies in the category `IsPerm`

. Basic operations for permutations are `LargestMovedPoint`

(42.3-2), multiplication of two permutations via `*`

, and exponentiation `^`

with first argument a positive integer i and second argument a permutation π, the result being the image i^π of the point i under π.

`‣ IsPermCollection` ( obj ) | ( category ) |

`‣ IsPermCollColl` ( obj ) | ( category ) |

are the categories for collections of permutations and collections of collections of permutations, respectively.

`‣ PermutationsFamily` | ( family ) |

is the family of all permutations.

`‣ \=` ( p1, p2 ) | ( method ) |

`‣ \<` ( p1, p2 ) | ( method ) |

Two permutations are equal if they move the same points and all these points have the same images under both permutations.

The permutation `p1` is smaller than `p2` if `p1` ≠ `p2` and i^{`p1`} < i^{`p2`}, where i is the smallest point with i^{`p1`} ≠ i^{`p2`}. Therefore the identity permutation is the smallest permutation, see also Section 31.11.

Permutations can be compared with certain other **GAP** objects, see 4.12 for the details.

gap> (1,2,3) = (2,3,1); true gap> (1,2,3) * (2,3,4) = (1,3)(2,4); true gap> (1,2,3) < (1,3,2); # 1^(1,2,3) = 2 < 3 = 1^(1,3,2) true gap> (1,3,2,4) < (1,3,4,2); # 2^(1,3,2,4) = 4 > 1 = 2^(1,3,4,2) false

`‣ DistancePerms` ( perm1, perm2 ) | ( operation ) |

returns the number of points for which `perm1` and `perm2` have different images. This should always produce the same result as `NrMovePoints(`

but some methods may be much faster than this form, since no new permutation needs to be created.`perm1`/`perm2`)

`‣ SmallestGeneratorPerm` ( perm ) | ( attribute ) |

is the smallest permutation that generates the same cyclic group as the permutation `perm`. This is very efficient, even when `perm` has large order.

gap> SmallestGeneratorPerm( (1,4,3,2) ); (1,2,3,4)

`‣ SmallestMovedPoint` ( perm ) | ( attribute ) |

`‣ SmallestMovedPoint` ( C ) | ( attribute ) |

is the smallest positive integer that is moved by `perm` if such an integer exists, and `infinity`

(18.2-1) if `perm` is the identity. For `C` a collection or list of permutations, the smallest value of `SmallestMovedPoint`

for the elements of `C` is returned (and `infinity`

(18.2-1) if `C` is empty).

`‣ LargestMovedPoint` ( perm ) | ( attribute ) |

`‣ LargestMovedPoint` ( C ) | ( attribute ) |

For a permutation `perm`, this attribute contains the largest positive integer which is moved by `perm` if such an integer exists, and `0`

if `perm` is the identity. For `C` a collection or list of permutations, the largest value of `LargestMovedPoint`

for the elements of `C` is returned (and `0`

if `C` is empty).

`‣ MovedPoints` ( perm ) | ( attribute ) |

`‣ MovedPoints` ( C ) | ( attribute ) |

is the proper set of the positive integers moved by at least one permutation in the collection `C`, respectively by the permutation `perm`.

`‣ NrMovedPoints` ( perm ) | ( attribute ) |

`‣ NrMovedPoints` ( C ) | ( attribute ) |

is the number of positive integers that are moved by `perm`, respectively by at least one element in the collection `C`. (The actual moved points are returned by `MovedPoints`

(42.3-3).)

gap> SmallestMovedPointPerm((4,5,6)(7,2,8)); 2 gap> LargestMovedPointPerm((4,5,6)(7,2,8)); 8 gap> NrMovedPointsPerm((4,5,6)(7,2,8)); 6 gap> MovedPoints([(2,3,4),(7,6,3),(5,47)]); [ 2, 3, 4, 5, 6, 7, 47 ] gap> NrMovedPoints([(2,3,4),(7,6,3),(5,47)]); 7 gap> SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]); 2 gap> LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]); 47 gap> LargestMovedPoint([()]); 0

`‣ SignPerm` ( perm ) | ( attribute ) |

The *sign* of a permutation `perm` is defined as (-1)^k where k is the number of cycles of `perm` of even length.

The sign is a homomorphism from the symmetric group onto the multiplicative group { +1, -1 }, the kernel of which is the alternating group.

`‣ CycleStructurePerm` ( perm ) | ( attribute ) |

is the cycle structure (i.e. the numbers of cycles of different lengths) of the permutation `perm`. This is encoded in a list l in the following form: The i-th entry of l contains the number of cycles of `perm` of length i+1. If `perm` contains no cycles of length i+1 it is not bound. Cycles of length 1 are ignored.

gap> SignPerm((1,2,3)(4,5)); -1 gap> CycleStructurePerm((1,2,3)(4,5,9,7,8)); [ , 1,, 1 ]

`‣ ListPerm` ( perm[, length] ) | ( function ) |

is a list l that contains the images of the positive integers under the permutation `perm`. That means that l`[`

i`]`

= i`^`

`perm`, where i lies between 1 and the largest point moved by `perm` (see `LargestMovedPoint`

(42.3-2)).

An optional second argument specifies the length of the desired list.

`‣ PermList` ( list ) | ( function ) |

is the permutation π that moves points as described by the list `list`. That means that i^π = `list``[`

i`]`

if i lies between 1 and the length of `list`, and i^π = i if i is larger than the length of the list `list`. `PermList`

will return `fail`

if `list` does not define a permutation, i.e., if `list` is not dense, or if `list` contains a positive integer twice, or if `list` contains an integer not in the range `[ 1 .. Length( `

. If `list` ) ]`list` contains non-integer entries an error is raised.

`‣ MappingPermListList` ( src, dst ) | ( function ) |

Let `src` and `dst` be lists of positive integers of the same length, such that neither may contain an element twice. `MappingPermListList`

returns a permutation π such that `src``[`

i`]^`

π = `dst``[`

i`]`

. The permutation π fixes all points larger than the maximum of the entries in `src` and `dst`. If there are several such permutations, it is not specified which of them `MappingPermListList`

returns.

`‣ RestrictedPerm` ( perm, list ) | ( operation ) |

`‣ RestrictedPermNC` ( perm, list ) | ( operation ) |

`RestrictedPerm`

returns the new permutation that acts on the points in the list `list` in the same way as the permutation `perm`, and that fixes those points that are not in `list`. The resulting permutation is stored internally of degree given by the maximal entry of `list`. `list` must be a list of positive integers such that for each i in `list` the image i`^`

`perm` is also in `list`, i.e., `list` must be the union of cycles of `perm`.

`RestrictedPermNC`

does not check whether `list` is a union of cycles.

gap> ListPerm((3,4,5)); [ 1, 2, 4, 5, 3 ] gap> PermList([1,2,4,5,3]); (3,4,5) gap> MappingPermListList([2,5,1,6],[7,12,8,2]); (1,8,5,12,11,10,9,6,2,7,4,3) gap> RestrictedPerm((1,2)(3,4),[3..5]); (3,4)

`‣ AsPermutation` ( f ) | ( attribute ) |

Returns: A permutation or `fail`

.

Partial permutations and transformations which define permutations (mathematically) can be converted into **GAP** permutations using `AsPermutation`

; see Chapters 53 and 54 for more details about transformations and partial permutations.

**for partial permutations**If the partial permutation

`f`is a permutation of its image, then`AsPermutation`

returns this permutation. If`f`does not permute its image, then`fail`

is returned.**for transformations**A transformation is a permutation if and only if its rank equals its degree. If a transformation in

**GAP**is a permutation, then`AsPermutation`

returns this permutation. If`f`is not a permutation, then`fail`

is returned.

The function `Permutation`

(41.9-1) can also be used to convert partial permutations and transformations into permutations where appropriate.

gap> f:=PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ], > [ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] ); (1,2,7,5)(3,9)(4)(6,10,8) gap> AsPermutation(f); (1,2,7,5)(3,9)(6,10,8) gap> f:= PartialPerm( [ 1, 2, 3, 4, 5, 7, 8 ], [ 5, 3, 8, 1, 9, 4, 10 ] ); [2,3,8,10][7,4,1,5,9] gap> AsPermutation(f); fail gap> f:=Transformation( [ 5, 8, 3, 5, 8, 6, 2, 2, 7, 8 ] );; gap> AsPermutation(f); fail gap> f:=Transformation( [ 1, 3, 6, 6, 2, 10, 2, 3, 10, 5 ] );; gap> AsPermutation(f); fail gap> f:=Transformation( [ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] ); Transformation( [ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] ) gap> AsPermutation(f); (1,2,7,5)(3,9)(6,10,8)

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML