% 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