**GAP** is a system especially designed for the computations in groups.
Permutation groups are a very important class of groups and **GAP** offers
a data type **permutation** to describe the elements of permutation groups.

Permutations in **GAP** operate on **positive integers**. Whenever group
elements operate on a domain we call the elements of this domain
**points**. Thus in this chapter we often call positive integers points,
if we want to emphasize that a permutation operates on them. An integer
*i* is said to be **moved** by a permutation *p* if the image *i^p* of *i*
under *p* is not *i*. The largest integer moved by any permutation may
not be larger than *2^{28}-1*.

Note that permutations do not belong to a specific group. That means
that you can work with permutations without defining a permutation group
that contains them. This is just like it is with integers, with which
you can compute without caring about the domain `Integers`

that contains
them. It also means that you can multiply any two permutations.

Permutations are entered and displayed in cycle notation.

gap> (1,2,3); (1,2,3) gap> (1,2,3) * (2,3,4); (1,3)(2,4)

The first sections in this chapter describe the operations that are available for permutations (see Comparisons of Permutations and Operations for Permutations). The next section describes the function that tests whether an object is a permutation (see IsPerm). The next sections describe the functions that find the largest and smallest point moved by a permutation (see LargestMovedPointPerm and SmallestMovedPointPerm). The next section describes the function that computes the sign of a permutation (see SignPerm). The next section describes the function that computes the smallest permutation that generates the same cyclic subgroup as a given permutation (see SmallestGeneratorPerm). The final sections describe the functions that convert between lists and permutations (see ListPerm, PermList, RestrictedPerm, and MappingPermListList).

Permutations are elements of groups operating on positive integers in a natural way, thus see chapter Groups and chapter Operations for more functions.

The external functions are in the file `LIBNAME/"permutat.g"`

.

- Comparisons of Permutations
- Operations for Permutations
- IsPerm
- LargestMovedPointPerm
- SmallestMovedPointPerm
- SignPerm
- SmallestGeneratorPerm
- ListPerm
- PermList
- RestrictedPerm
- MappingPermListList

`p1` = `p2`

`p1` < `p2`

The equality operator `=`

evaluates to `true`

if the two permutations
`p1` and `p2` are equal, and to `false`

otherwise. The inequality
operator `<`

evaluates to `true`

if the two permutations `p1` and `p2`
are not equal, and to `false`

otherwise. You can also compare
permutations with objects of other types, of course they are never equal.

Two permutations are considered equal if and only if they move the same points and if the images of the moved points are the same under the operation of both permutations.

gap> (1,2,3) = (2,3,1); true gap> (1,2,3) * (2,3,4) = (1,3)(2,4); true

`p1` < `p2`

`p1` <= `p2`

`p1` `p2`

`p1` = `p2`

The operators `<`

, `<=`

, `, and `

`=`

evaluate to `true`

if the
permutation `p1` is less than, less than or equal to, greater than, or
greater than or equal to the permutation `p2`, and to `false`

otherwise.

Let *p_1* and *p_2* be two permutations that are not equal. Then there
exists at least one point *i* such that *i^{p_1} <> i^{p_2}*. Let *k*
be the smallest such point. Then *p_1* is considered smaller than *p_2*
if and only if *k^{p_1} < k^{p_2}*. Note that this implies that the
identity permutation is the smallest permutation.

You can also compare permutations with objects of other types. Integers, rationals, cyclotomics, unknowns, and finite field elements are smaller than permutations. Everything else is larger.

gap> (1,2,3) < (1,3,2); true # $1^{(1,2,3)} = 2 \<\ 3 = 1^{(1,3,2)}$ gap> (1,3,2,4) < (1,3,4,2); false # $2^{(1,3,2,4)} = 4 > 1 = 2^{(1,3,4,2)}$

`p1` * `p2`

The operator `*`

evaluates to the product of the two permutations `p1`
and `p2`.

`p1` / `p2`

The operator `/`

evaluates to the quotient *p1 * p2^{-1}* of the two
permutations `p1` and `p2`.

`LeftQuotient( `

`p1`, `p2` )

`LeftQuotient`

returns the left quotient *p1^{-1} * p2* of the two
permutations `p1` and `p2`. (This can also be written

.)
`p1` mod `p2`

`p` ^ `i`

The operator `^`

evaluates to the `i`-th power of the permutation `p`.

`p1` ^ `p2`

The operator `^`

evaluates to the conjugate *p2^{-1} * p1 * p2* of the
permutation `p1` by the permutation `p2`.

`Comm( `

`p1`, `p2` )

`Comm`

returns the commutator *p1^{-1} * p2^{-1} * p1 * p2* of the two
permutations `p1` and `p2`.

`i` ^ `p`

The operator `^`

evaluates to the image *i^p* of the positive integer
`i` under the permutation `p`.

`i` / `p`

The operator `/`

evaluates to the preimage *i^{p^{-1}}* of the integer
`i` under the permutation `p`.

`list` * `p`

`p` * `list`

The operator `*`

evaluates to the list of products of the permutations
in `list` with the permutation `p`. That means that the value is a new
list `new` such that

respectively
`new`[`i`] = `list`[`i`] * `p`

.
`new`[`i`] = `p` * `list`[`i`]

`list` / `p`

The operator `/`

evaluates to the list of quotients of the permutations
in `list` with the permutation `p`. That means that the value is a new
list `new` such that

.
`new`[`i`] = `list`[`i`] / `p`

For the precedence of the operators see Operations.

`IsPerm( `

`obj` )

`IsPerm`

returns `true`

if `obj`, which may be an object of arbitrary
type, is a permutation and `false`

otherwise. It will signal an error if
`obj` is an unbound variable.

gap> IsPerm( (1,2) ); true gap> IsPerm( 1 ); false

`LargestMovedPointPerm( `

`perm` )

`LargestMoverPointPerm`

returns the largest point moved by the
permutation `perm`, i.e., the largest positive integer `i` such that

. It will signal an error if `i`^`perm` < `i``perm` is trivial
(see also SmallestMovedPointPerm).

gap> LargestMovedPointPerm( (2,3,1) ); 3 gap> LargestMovedPointPerm( (1,2)(1000,1001) ); 1001

`SmallestMovedPointPerm( `

`perm` )

`SmallestMovedPointPerm`

returns the smallest point moved by the
permutation `perm`, i.e., the smallest positive integer `i` such that

. It will signal an error if `i`^`perm` < `i``perm` is trivial
(see also LargestMovedPointPerm).

gap> SmallestMovedPointPerm( (4,7,5) ); 4

`SignPerm( `

`perm` )

`SignPerm`

returns the **sign** of the permutation `perm`.

The sign *s* of a permutation *p* is defined by
*s = prod_{i < j}{(i^p - j^p)} / prod_{i < j}{(i - j)}*,
where *n* is the largest point moved by *p* and *i,j* range over *1...n*.

One can easily show that **sign** is equivalent to the **determinant** of the
**permutation matrix** of `perm`. Thus it is obvious that the function
**sign** is a homomorphism.

gap> SignPerm( (1,2,3)(5,6) ); -1

`SmallestGeneratorPerm( `

`perm` )

`SmallestGeneratorPerm`

returns the smallest permutation that generates
the same cyclic group as the permutation `perm`.

gap> SmallestGeneratorPerm( (1,4,3,2) ); (1,2,3,4)

Note that `SmallestGeneratorPerm`

is very efficient, even when `perm` has
huge order.

`ListPerm( `

`perm` )

`ListPerm`

returns a list `list` that contains the images of the positive
integers under the permutation `perm`. That means that

, where `list`[`i`] =
`i`^`perm``i` lies between 1 and the largest point moved by
`perm` (see LargestMovedPointPerm).

gap> ListPerm( (1,2,3,4) ); [ 2, 3, 4, 1 ] gap> ListPerm( () ); [ ]

`PermList`

(see PermList) performs the inverse operation.

`PermList( `

`list` )

`PermList`

returns the permutation `perm` that moves points as describes
by the list `list`. That means that

if `i`^`perm` = `list`[`i`]`i`
lies between 1 and the length of `list`, and

if `i`^`perm` = `i``i`
is larger than the length of the list `list`. It will signal an error if
`list` does not define a permutation, i.e., if `list` is not a list of
integers without holes, or if `list` contains an integer twice, or if
`list` contains an integer not in the range `[1..Length(`

.
`list`)]

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

`ListPerm`

(see ListPerm) performs the inverse operation.

`RestrictedPerm( `

`perm`, `list` )

`RestrictedPerm`

returns the new permutation `new` that operates 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

is also in `i`^`perm``list`, i.e., it must be the union of cycles of
`perm`.

gap> RestrictedPerm( (1,2,3)(4,5), [4,5] ); (4,5)

`MappingPermListList( `

`list1`, `list2` )

`MappingPermListList`

returns a permutation `perm` such that

. `list1`[`i`] ^ `perm` = `list2`[`i`]`perm` fixes all points larger
then the maximum of the entries in `list1` and `list2`. If there are
several such permutations, it is not specified which
`MappingPermListList`

returns. `list1` and `list2` must be lists of
positive integers of the same length, and neither may contain an element
twice.

gap> MappingPermListList( [3,4], [6,9] ); (3,6,4,9,8,7,5) gap> MappingPermListList( [], [] ); ()

GAP 3.4.4

April 1997