40 Permutations

Each permutation in GAP lies in the category IsPerm. Basic operations for permutations are LargestMovedPoint (see LargestMovedPoint), multiplication of two permutations via *, and exponentiation ^ with first argument a positive integer i and second argument a permutation π, the result being the image of the point i under π.

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

is the family of all permutations.

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 either all stored as 16-bit integers or all as 32-bit integers (actually as GAP immediate integers less than 2²⁸), depending on whether d ≤ 65536 or not. This means that the identity permutation () takes 4m bytes if it was calculated as (1, ..., m) * (1, ..., m)^-1. It can take even more because the internal list has sometimes room for more than d images. For example, the maximal degree of any permutation in GAP is m = 2²²−1024 = 4,193,280, because bigger permutations would have an internal list with room for more than 2²² images, requiring more than 2²⁴ bytes. 2²⁴, however, is the largest possible size of an object that the GAP storage manager can deal with.

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

40.1 Comparison of Permutations

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

The permutation p₁ is smaller than p₂ if p₁ ≠ p₂ and i^p₁ < i^p₂ where i is the smallest point with i^p₁ ≠ i^p₂. Therefore the identity permutation is the smallest permutation. (see also Comparison Operations for Elements)

Permutations can be compared with certain other GAP objects, see Comparisons 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

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)

40.2 Moved Points of Permutations

is the smallest positive integer that is moved by perm if such an integer exists, and infinity if perm = (). For C a collection or list of permutations, the smallest value of SmallestMovedPoint for the elements of C is returned (and infinity if C is empty).

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

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

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, see MovedPoints)

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

40.3 Sign and Cycle Structure

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.

is the cycle structure (i.e. the numbers of cycles of different lengths) of 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 ]

40.4 Creating Permutations

is a list list that contains the images of the positive integers under the permutation perm. That means that list[i] = i^perm, where i lies between 1 and the largest point moved by perm (see LargestMovedPoint).

is the permutation perm that moves points as described by the list list. That means that i^perm = list[i] if i lies between 1 and the length of list, and i^perm = i if i is larger than the length of the list list. It 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( list ) ]. If list contains non-integer entries an error is raised.

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 perm such that src[i]^perm = dst[i]. perm 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 returns the new permutation new 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. 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)

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
March 2006