39 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 less than 228-1, and the image of a point i under a permutation p is written ip, which is expressed as i^p in GAP. (This action is also implemented by the function OnPoints, see OnPoints.) If i^ p ¹ 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 compputed as i / p, without constructing the inverse of p.

For arithmetic operations for permutations and their precedence, see Arithmetic Operations for Elements.

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

  • IsPerm( obj ) C

  • IsPermCollection( obj ) C
  • IsPermCollColl( obj ) C

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

  • PermutationsFamily V

    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 228), 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 = 222-1024 = 4,193,280, because bigger permutations would have an internal list with room for more than 222 images, requiring more than 224 bytes. 224, 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.

    Sections

    1. Comparison of Permutations
    2. Moved Points of Permutations
    3. Sign and Cycle Structure
    4. Creating Permutations

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

    GAP 4 manual
    February 2000