[MathJax on]

42 Permutations

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

42.1 IsPerm (Filter)

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.

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-18) can be used to permute the entries of a list according to a permutation.

42.1-1 IsPerm

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

42.1-2 IsPermCollection

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

42.1-3 PermutationsFamily

is the family of all permutations.

42.1-4 PERM_INVERSE_THRESHOLD

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 Comparison of Permutations

42.2-1 \=

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

42.2-2 DistancePerms

returns the number of points for which perm1 and perm2 have different images. This should always produce the same result as NrMovePoints(perm1/perm2) but some methods may be much faster than this form, since no new permutation needs to be created.

42.2-3 SmallestGeneratorPerm

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)

42.3 Moved Points of Permutations

42.3-1 SmallestMovedPoint

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

42.3-2 LargestMovedPoint

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

42.3-3 MovedPoints

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

42.3-4 NrMovedPoints