<html><head><title>[ref] 40 Permutations</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP039.htm">Previous</a>] [<a href ="CHAP041.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>40 Permutations</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP040.htm#SECT001">Comparison of Permutations</a>
<li> <A HREF="CHAP040.htm#SECT002">Moved Points of Permutations</a>
<li> <A HREF="CHAP040.htm#SECT003">Sign and Cycle Structure</a>
<li> <A HREF="CHAP040.htm#SECT004">Creating Permutations</a>
</ol><p>
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> offers a data type <strong>permutation</strong> to describe the elements
of permutation groups.
<p>
The points on which permutations in <font face="Gill Sans,Helvetica,Arial">GAP</font> act are the positive
integers less than 2<sup>28</sup>−1, and the image of a point <var>i</var> under a
permutation <var>p</var> is written <i>i</i><sup><i>p</i></sup>, which is expressed as <code></code><var>i</var><code>^</code><var>p</var><code></code> in
<font face="Gill Sans,Helvetica,Arial">GAP</font>.
(This action is also implemented by the function <code>OnPoints</code>,
see <a href="CHAP039.htm#SSEC002.1">OnPoints</a>.)
If <code></code><var>i</var><code>^<i>p</i> ≠ <i>i</i></code>, we say that <var>i</var> is <strong>moved</strong> by <var>p</var>, otherwise
it is <strong>fixed</strong>. Permutations in <font face="Gill Sans,Helvetica,Arial">GAP</font> are entered and displayed in cycle
notation, such as <code>(1,2,3)(4,5)</code>.
<p>
The preimage of the point <var>i</var> under the permutation <var>p</var> can be computed
as <code></code><var>i</var><code> / </code><var>p</var><code></code>, without constructing the inverse of <var>p</var>.
<p>
For arithmetic operations for permutations and their precedence,
see <a href="CHAP030.htm#SECT012">Arithmetic Operations for Elements</a>.
<p>
In the names of the <font face="Gill Sans,Helvetica,Arial">GAP</font> functions that deal with permutations, the
word <code>Permutation</code> is usually abbreviated to <code>Perm</code>, to save typing.
For example, the category test function for permutations is called
<code>IsPerm</code>.
<p>
<a name = ""></a>
<li><code>IsPerm( </code><var>obj</var><code> ) C</code>
<p>
Each <strong>permutation</strong> in <font face="Gill Sans,Helvetica,Arial">GAP</font> lies in the category <code>IsPerm</code>.
Basic operations for permutations are <code>LargestMovedPoint</code>
(see <a href="CHAP040.htm#SSEC002.2">LargestMovedPoint</a>), multiplication of two permutations via <code>*</code>,
and exponentiation <code>^</code> with first argument a
positive integer <i>i</i> and second argument a permutation π, the result
being the image of the point <i>i</i> under π.
<p>
<a name = ""></a>
<li><code>IsPermCollection( </code><var>obj</var><code> ) C</code>
<a name = ""></a>
<li><code>IsPermCollColl( </code><var>obj</var><code> ) C</code>
<p>
are the categories for collections of permutations and collections of
collections of permutations, respectively.
<p>
<a name = ""></a>
<li><code>PermutationsFamily V</code>
<p>
is the family of all permutations.
<p>
Internally, <font face="Gill Sans,Helvetica,Arial">GAP</font> stores a permutation as a list of the <var>d</var> images of
the integers 1,…, <i>d</i>, where the ``internal degree'' <var>d</var> is the
largest integer moved by the permutation or bigger. When a permutation is
read in in cycle notation, <var>d</var> is always set to the largest moved
integer, but a bigger <var>d</var> can result from a multiplication of two
permutations, because the product is not shortened if it fixes <var>d</var>. The
images are either all stored as 16-bit integers or all as 32-bit integers
(actually as <font face="Gill Sans,Helvetica,Arial">GAP</font> immediate integers less than 2<sup>28</sup>), depending on
whether <i>d</i> ≤ 65536 or not. This means that the identity permutation
<code>()</code> takes 4<i>m</i> bytes if it was calculated as <code>(1, ..., </code><var>m</var><code>) * (1,
..., </code><var>m</var><code>)^-1</code>. It can take even more because the internal list has
sometimes room for more than <var>d</var> images. For example, the maximal degree
of any permutation in <font face="Gill Sans,Helvetica,Arial">GAP</font> is <i>m</i> = 2<sup>22</sup>−1024 = 4,193,280,
because bigger permutations would have an internal list with room for
more than 2<sup>22</sup> images, requiring more than 2<sup>24</sup> bytes. 2<sup>24</sup>,
however, is the largest possible size of an object that the <font face="Gill Sans,Helvetica,Arial">GAP</font>
storage manager can deal with.
<p>
Permutations do not belong to a specific group. That means
that one can work with permutations without defining a permutation group
that contains them.
<p>
<pre>
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
</pre>
<p>
The operation <code>Permuted</code> (see <a href="CHAP021.htm#SSEC020.16">Permuted</a>) can be used to permute the entries
of a list according to a permutation.
<p>
<p>
<h2><a name="SECT001">40.1 Comparison of Permutations</a></h2>
<p><p>
<a name = "SSEC001.1"></a>
<li><code></code><var>p_1</var><code> = </code><var>p_2</var><code></code>
<a name = "SSEC001.1"></a>
<li><code></code><var>p_1</var><code> < </code><var>p_2</var><code></code>
<p>
Two permutations are equal if they move the same points and all these points
have the same images under both permutations.
<p>
The permutation <i>p</i><sub>1</sub> is smaller than <i>p</i><sub>2</sub> if <i>p</i><sub>1</sub> ≠ <i>p</i><sub>2</sub> and
<i>i</i><sup><i>p</i><sub>1</sub></sup> < <i>i</i><sup><i>p</i><sub>2</sub></sup> where <i>i</i> is the smallest point with
<i>i</i><sup><i>p</i><sub>1</sub></sup> ≠ <i>i</i><sup><i>p</i><sub>2</sub></sup>.
Therefore the identity permutation is the smallest permutation.
(see also <a href="CHAP030.htm#SECT011">Comparison Operations for Elements</a>)
<p>
Permutations can be compared with certain other <font face="Gill Sans,Helvetica,Arial">GAP</font> objects,
see <a href="CHAP004.htm#SECT011">Comparisons</a> for the details.
<p>
<pre>
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
</pre>
<p>
<a name = "SSEC001.2"></a>
<li><code>SmallestGeneratorPerm( </code><var>perm</var><code> ) F</code>
<p>
is the smallest permutation that generates the same cyclic group
as the permutation <var>perm</var>.
This is very efficient, even when <var>perm</var> has large order.
<p>
<pre>
gap> SmallestGeneratorPerm( (1,4,3,2) );
(1,2,3,4)
</pre>
<p>
<p>
<h2><a name="SECT002">40.2 Moved Points of Permutations</a></h2>
<p><p>
<a name = "SSEC002.1"></a>
<li><code>SmallestMovedPoint( </code><var>perm</var><code> ) A</code>
<li><code>SmallestMovedPoint( </code><var>C</var><code> ) A</code>
<p>
is the smallest positive integer that is moved by <var>perm</var>
if such an integer exists, and <code>infinity</code> if <code></code><var>perm</var><code> = ()</code>.
For <var>C</var> a collection or list of permutations, the smallest value of
<code>SmallestMovedPoint</code> for the elements of <var>C</var> is returned (and <code>infinity</code>
if <var>C</var> is empty).
<p>
<a name = "SSEC002.2"></a>
<li><code>LargestMovedPoint( </code><var>perm</var><code> ) A</code>
<li><code>LargestMovedPoint( </code><var>C</var><code> ) A</code>
<p>
For a permutation <var>perm</var>, this attribute contains
the largest positive integer which is moved by <var>perm</var>
if such an integer exists, and 0 if <code></code><var>perm</var><code> = ()</code>.
For <var>C</var> a collection or list of permutations, the largest value of
<code>LargestMovedPoint</code> for the elements of <var>C</var> is returned (and 0 if <var>C</var> is
empty).
<p>
<a name = "SSEC002.3"></a>
<li><code>MovedPoints( </code><var>perm</var><code> ) A</code>
<li><code>MovedPoints( </code><var>C</var><code> ) A</code>
<p>
is the proper set of the positive integers moved by at least one
permutation in the collection <var>C</var>, respectively by the permutation
<var>perm</var>.
<p>
<a name = "SSEC002.4"></a>
<li><code>NrMovedPoints( </code><var>perm</var><code> ) A</code>
<li><code>NrMovedPoints( </code><var>C</var><code> ) A</code>
<p>
is the number of positive integers that are moved by <var>perm</var>,
respectively by at least one element in the collection <var>C</var>.
(The actual moved points are returned by <code>MovedPoints</code>,
see <a href="CHAP040.htm#SSEC002.3">MovedPoints</a>)
<p>
<pre>
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
</pre>
<p>
<p>
<h2><a name="SECT003">40.3 Sign and Cycle Structure</a></h2>
<p><p>
<a name = "SSEC003.1"></a>
<li><code>SignPerm( </code><var>perm</var><code> ) A</code>
<p>
The <strong>sign</strong> of a permutation <var>perm</var> is defined as (−1)<sup><i>k</i></sup>
where <i>k</i> is the number of cycles of <var>perm</var> of even length.
<p>
The sign is a homomorphism from the symmetric group onto the
multiplicative group { +1, −1 },
the kernel of which is the alternating group.
<p>
<a name = "SSEC003.2"></a>
<li><code>CycleStructurePerm( </code><var>perm</var><code> ) A</code>
<p>
is the cycle structure (i.e. the numbers of cycles of different
lengths) of <var>perm</var>. This is encoded in a list <var>l</var> in the following form:
The <var>i</var>-th entry of <var>l</var> contains the number of cycles of <var>perm</var> of
length <var>i+1</var>. If <var>perm</var> contains no cycles of length <var>i+1</var> it is not
bound.
Cycles of length 1 are ignored.
<p>
<pre>
gap> SignPerm((1,2,3)(4,5));
-1
gap> CycleStructurePerm((1,2,3)(4,5,9,7,8));
[ , 1,, 1 ]
</pre>
<p>
<p>
<h2><a name="SECT004">40.4 Creating Permutations</a></h2>
<p><p>
<a name = "SSEC004.1"></a>
<li><code>ListPerm( </code><var>perm</var><code> ) F</code>
<p>
is a list <var>list</var> that contains the images of the positive integers
under the permutation <var>perm</var>.
That means that <code></code><var>list</var><code>[</code><var>i</var><code>] = </code><var>i</var><code>^</code><var>perm</var><code></code>, where <var>i</var> lies between 1
and the largest point moved by <var>perm</var> (see <a href="CHAP040.htm#SSEC002.2">LargestMovedPoint</a>).
<p>
<a name = "SSEC004.2"></a>
<li><code>PermList( </code><var>list</var><code> ) F</code>
<p>
is the permutation <var>perm</var> that moves points as described by the
list <var>list</var>. That means that <code></code><var>i</var><code>^</code><var>perm</var><code> = </code><var>list</var><code>[</code><var>i</var><code>]</code> if <var>i</var> lies
between 1 and the length of <var>list</var>, and <code></code><var>i</var><code>^</code><var>perm</var><code> = </code><var>i</var><code></code> if <var>i</var> is
larger than the length of the list <var>list</var>. It will return <code>fail</code>
if <var>list</var> does not define a permutation, i.e., if <var>list</var> is not dense,
or if <var>list</var> contains a positive integer twice, or if <var>list</var> contains an
integer not in the range <code>[ 1 .. Length( </code><var>list</var><code> ) ]</code>.
If <var>list</var> contains non-integer entries an error is raised.
<p>
<a name = "SSEC004.3"></a>
<li><code>MappingPermListList( </code><var>src</var><code>, </code><var>dst</var><code> ) F</code>
<p>
Let <var>src</var> and <var>dst</var> be lists of positive integers of the same length,
such that neither may contain an element twice.
<code>MappingPermListList</code> returns a permutation <var>perm</var> such that
<code></code><var>src</var><code>[</code><var>i</var><code>]^</code><var>perm</var><code> = </code><var>dst</var><code>[</code><var>i</var><code>]</code>.
<var>perm</var> fixes all points larger than the maximum of the entries in <var>src</var>
and <var>dst</var>.
If there are several such permutations, it is not specified which of them
<code>MappingPermListList</code> returns.
<p>
<a name = "SSEC004.4"></a>
<li><code>RestrictedPerm( </code><var>perm</var><code>, </code><var>list</var><code> ) O</code>
<a name = "SSEC004.4"></a>
<li><code>RestrictedPermNC( </code><var>perm</var><code>, </code><var>list</var><code> ) O</code>
<p>
<code>RestrictedPerm</code> returns the new permutation <var>new</var> that acts on the
points in the list <var>list</var> in the same way as the permutation <var>perm</var>,
and that fixes those points that are not in <var>list</var>.
<var>list</var> must be a list of positive integers such that for each <var>i</var> in
<var>list</var> the image <code></code><var>i</var><code>^</code><var>perm</var><code></code> is also in <var>list</var>,
i.e., <var>list</var> must be the union of cycles of <var>perm</var>.
<p>
<code>RestrictedPermNC</code> does not check whether <var>list</var> is a union of cycles.
<p>
<pre>
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)
</pre>
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP039.htm">Previous</a>] [<a href ="CHAP041.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
182
