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, see `PERM_INVERSE_THRESHOLD`

(42.1-4).

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

On 32-bit systems, the limit on the degree of permutations is, for technical reasons, 2^28-1. On 64-bit systems, it is 2^32-1 because only a 32-bit integer is used to represent each image internally. Error messages should be given if any command would require creating a permutation exceeding this limit.

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-17) 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.

`‣ PERM_INVERSE_THRESHOLD` | ( global variable ) |

For permutations of degree up to `PERM_INVERSE_THRESHOLD`

whenever the inverse image of a point under a permutations is needed, the entire inverse is computed and stored. Otherwise, if the inverse is not stored, the point is traced around the cycle it is part of to find the inverse image. This takes time when it happens, and uses memory, but saves time on a variety of subsequent computations. This threshold can be adjusted by simply assigning to the variable. The default is 10000.

`42.2-1 \=`

`‣ \=` ( 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.13 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 `NrMovedPoints(`

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

, or if `list` ) ]`list` contains non-integer entries, etc.

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

Let `src` and `dst` be lists of positive integers of the same length, such that there is a permutation π such that `OnTuples(`

π`src`,`) = `

. `dst``MappingPermListList`

returns the permutation `p`

from the previous sentence, i.e. `src``[`

i`]^`

p = `dst``[`

i`]`

. The permutation π fixes any point which is not in `src` or `dst`. If there are several such permutations, it is not specified which of them `MappingPermListList`

returns. If there is no such permutation, then `MappingPermListList`

returns `fail`

.

`‣ 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,6,2,7) gap> RestrictedPerm((1,2)(3,4),[3..5]); (3,4)

`‣ CycleFromList` ( list ) | ( function ) |

For the given dense, duplicate-free list of positive integers [a_1, a_2, ..., a_n] return the n-cycle (a_1,a_2,...,a_n). For the empty list the trivial permutation () is returned.

If the given `list` contains duplicates or holes, return `fail`

.

gap> CycleFromList( [1,2,3,4] ); (1,2,3,4) gap> CycleFromList( [3,2,6,4,5] ); (2,6,4,5,3) gap> CycleFromList( [2,3,2] ); fail gap> CycleFromList( [1,,3] ); fail

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