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, \ldots, 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 \leq 65536\) or not. For example, if \(m\geq 65536\), the permutation \((1, 2, \ldots, 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, \ldots, m) * (1, 2, \ldots, 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 \(\pi\), the result being the image \(i^{\pi}\) of the point \(i\) under \(\pi\).

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

`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` \(\neq\) `p2` and \(i^{{\textit{p1}}} < i^{{\textit{p2}}}\), where \(i\) is the smallest point with \(i^{{\textit{p1}}} \neq i^{{\textit{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 \(\pi\) that moves points as described by the list `list`. That means that \(i^{\pi} =\) `list``[`

\(i\)`]`

if \(i\) lies between \(1\) and the length of `list`, and \(i^{\pi} = 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 \(\pi\) such that `src``[`

\(i\)`]^`

\(\pi =\) `dst``[`

\(i\)`]`

. The permutation \(\pi\) 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