% This file was created automatically from permutat.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A permutat.msk GAP documentation Martin Schoenert
%A Alexander Hulpke
%%
%A @(#)$Id: permutat.msk,v 1.15 2002/04/15 10:02:33 sal Exp $
%%
%Y (C) 1998 School Math and Comp. Sci., University of St. Andrews, Scotland
%Y Copyright (C) 2002 The GAP Group
%%
\Chapter{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 $2^{28}-1$, 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',
see~"OnPoints".)
If `<i>^$p\ne 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~"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
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 $\pi$, the result
being the image of the point $i$ under $\pi$.
\>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,\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 either all stored as 16-bit integers or all as 32-bit integers
(actually as {\GAP} immediate integers less than $2^{28}$), depending on
whether $d\le 65536$ or not. This means that the identity permutation
`()' takes $4<m>$ bytes if it was calculated as `(1, \dots, <m>) \* (1,
\dots, <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^{22}-1024 = 4{,}193{,}280$,
because bigger permutations would have an internal list with room for
more than $2^{22}$ images, requiring more than $2^{24}$~bytes. $2^{24}$,
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.
\beginexample
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
\endexample
The operation `Permuted' (see~"Permuted") can be used to permute the entries
of a list according to a permutation.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparison of Permutations}
\>`<p_1> = <p_2>'{equality test}!{for permutations}
\>`<p_1> \< <p_2>'{precedence test}!{for 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_1$ is smaller than $p_2$ if $p_1\not=p_2$ and
$i^{p_1}\<i^{p_2}$ where $i$ is the smallest point with
$i^{p_1}\not=i^{p_2}$.
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.
\beginexample
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
\endexample
\>SmallestGeneratorPerm( <perm> ) F
is the smallest permutation that generates the same cyclic group
as the permutation <perm>.
This is very efficient, even when <perm> has large order.
\beginexample
gap> SmallestGeneratorPerm( (1,4,3,2) );
(1,2,3,4)
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Moved Points of Permutations}
\>SmallestMovedPoint( <perm> ) A
\>SmallestMovedPoint( <C> ) A
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).
\>LargestMovedPoint( <perm> ) A
\>LargestMovedPoint( <C> ) A
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).
\>MovedPoints( <perm> ) A
\>MovedPoints( <C> ) A
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> ) A
\>NrMovedPoints( <C> ) A
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")
\beginexample
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
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Sign and Cycle Structure}
\>SignPerm( <perm> ) A
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> ) A
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.
\beginexample
gap> SignPerm((1,2,3)(4,5));
-1
gap> CycleStructurePerm((1,2,3)(4,5,9,7,8));
[ , 1,, 1 ]
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creating Permutations}
\>ListPerm( <perm> ) F
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").
\>PermList( <list> ) F
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.
\>MappingPermListList( <src>, <dst> ) F
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( <perm>, <list> ) O
\>RestrictedPermNC( <perm>, <list> ) O
`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.
\beginexample
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)
\endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
