This file is indexed.

/usr/share/gap/doc/ref/chap42.html is in gap-doc 4r8p6-2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
         "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (ref) - Chapter 42: Permutations</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap42"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap41.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap43.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap42_mj.html">[MathJax on]</a></p>
<p><a id="X80F808307A2D5AB8" name="X80F808307A2D5AB8"></a></p>
<div class="ChapSects"><a href="chap42.html#X80F808307A2D5AB8">42 <span class="Heading">Permutations</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap42.html#X80F07BE2811D4BAC">42.1 <span class="Heading">IsPerm (Filter)</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7AA69C6686FC49EA">42.1-1 IsPerm</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X82069E437D2DF9AA">42.1-2 IsPermCollection</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X819628B083B3939B">42.1-3 PermutationsFamily</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap42.html#X7A21DE5779D21A6D">42.2 <span class="Heading">Comparison of Permutations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7CEC03A9808E2E7C">42.2-1 \=</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7BC944F57A04AFF2">42.2-2 DistancePerms</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X83A917F67D45C7EA">42.2-3 SmallestGeneratorPerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap42.html#X82C255E2821C0721">42.3 <span class="Heading">Moved Points of Permutations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X84EF0A697F7A87DC">42.3-1 SmallestMovedPoint</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X84AA603987C94AC0">42.3-2 LargestMovedPoint</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X85E61B9C7A6B0CCA">42.3-3 MovedPoints</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X85E7B1E28430F49E">42.3-4 NrMovedPoints</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap42.html#X79BE80267F4AA2B0">42.4 <span class="Heading">Sign and Cycle Structure</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7BE5011B7C0DB704">42.4-1 SignPerm</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7944D1447804A69A">42.4-2 CycleStructurePerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap42.html#X7B3194EC869D936D">42.5 <span class="Heading">Creating Permutations</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7A9DCFD986958C1E">42.5-1 ListPerm</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X78D611D17EA6E3BC">42.5-2 PermList</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X8087DCC780B9656A">42.5-3 MappingPermListList</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X7EF8388E7DA8E600">42.5-4 RestrictedPerm</a></span>
<span class="ContSS"><br /><span class="nocss">&nbsp;&nbsp;</span><a href="chap42.html#X8353AB8987E35DF3">42.5-5 AsPermutation</a></span>
</div></div>
</div>

<h3>42 <span class="Heading">Permutations</span></h3>

<p><strong class="pkg">GAP</strong> offers a data type <em>permutation</em> to describe the elements of permutation groups.</p>

<p>The points on which permutations in <strong class="pkg">GAP</strong> act are the positive integers up to a certain architecture dependent limit, and the image of a point <span class="SimpleMath">i</span> under a permutation <span class="SimpleMath">p</span> is written <span class="SimpleMath">i^p</span>, which is expressed as <span class="SimpleMath">i</span><code class="code">^</code><span class="SimpleMath">p</span> in <strong class="pkg">GAP</strong>. (This action is also implemented by the function <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>).) If <span class="SimpleMath">i</span><code class="code">^</code><span class="SimpleMath">p</span> is different from <span class="SimpleMath">i</span>, we say that <span class="SimpleMath">i</span> is <em>moved</em> by <span class="SimpleMath">p</span>, otherwise it is <em>fixed</em>. Permutations in <strong class="pkg">GAP</strong> are entered and displayed in cycle notation, such as <code class="code">(1,2,3)(4,5)</code>.</p>

<p>The preimage of the point <span class="SimpleMath">i</span> under the permutation <span class="SimpleMath">p</span> can be computed as <span class="SimpleMath">i</span><code class="code">/</code><span class="SimpleMath">p</span>, without constructing the inverse of <span class="SimpleMath">p</span>.</p>

<p>For arithmetic operations for permutations and their precedence, see <a href="chap31.html#X7A2914307963E370"><span class="RefLink">31.12</span></a>.</p>

<p>In the names of the <strong class="pkg">GAP</strong> 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 <code class="func">IsPerm</code> (<a href="chap42.html#X7AA69C6686FC49EA"><span class="RefLink">42.1-1</span></a>).</p>

<p><a id="X80F07BE2811D4BAC" name="X80F07BE2811D4BAC"></a></p>

<h4>42.1 <span class="Heading">IsPerm (Filter)</span></h4>

<p>Internally, <strong class="pkg">GAP</strong> stores a permutation as a list of the <span class="SimpleMath">d</span> images of the integers <span class="SimpleMath">1, ..., d</span>, where the "internal degree" <span class="SimpleMath">d</span> is the largest integer moved by the permutation or bigger. When a permutation is read in in cycle notation, <span class="SimpleMath">d</span> is always set to the largest moved integer, but a bigger <span class="SimpleMath">d</span> can result from a multiplication of two permutations, because the product is not shortened if it fixes <span class="SimpleMath">d</span>. The images are stored all as <span class="SimpleMath">16</span>-bit integers or all as <span class="SimpleMath">32</span>-bit integers, depending on whether <span class="SimpleMath">d ≤ 65536</span> or not. For example, if <span class="SimpleMath">m≥ 65536</span>, the permutation <span class="SimpleMath">(1, 2, ..., m)</span> has internal degree <span class="SimpleMath">d=m</span> and takes <span class="SimpleMath">4m</span> bytes of memory for storage. But --- since the internal degree is not reduced --- this means that the identity permutation <code class="code">()</code> calculated as <span class="SimpleMath">(1, 2, ..., m) * (1, 2, ..., m)^{-1}</span> also takes <span class="SimpleMath">4m</span> bytes of storage. It can take even more because the internal list has sometimes room for more than <span class="SimpleMath">d</span> images.</p>

<p>The operation <code class="func">RestrictedPerm</code> (<a href="chap42.html#X7EF8388E7DA8E600"><span class="RefLink">42.5-4</span></a>) reduces the storage degree of its result and therefore can be used to save memory if intermediate calculations in large degree result in a small degree result.</p>

<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>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,2,3);</span>
(1,2,3)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,2,3) * (2,3,4);</span>
(1,3)(2,4)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">17^(2,5,17,9,8);</span>
9
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">OnPoints(17,(2,5,17,9,8));</span>
9
</pre></div>

<p>The operation <code class="func">Permuted</code> (<a href="chap21.html#X7B5A19098406347A"><span class="RefLink">21.20-18</span></a>) can be used to permute the entries of a list according to a permutation.</p>

<p><a id="X7AA69C6686FC49EA" name="X7AA69C6686FC49EA"></a></p>

<h5>42.1-1 IsPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsPerm</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Each <em>permutation</em> in <strong class="pkg">GAP</strong> lies in the category <code class="func">IsPerm</code>. Basic operations for permutations are <code class="func">LargestMovedPoint</code> (<a href="chap42.html#X84AA603987C94AC0"><span class="RefLink">42.3-2</span></a>), multiplication of two permutations via <code class="code">*</code>, and exponentiation <code class="code">^</code> with first argument a positive integer <span class="SimpleMath">i</span> and second argument a permutation <span class="SimpleMath">π</span>, the result being the image <span class="SimpleMath">i^π</span> of the point <span class="SimpleMath">i</span> under <span class="SimpleMath">π</span>.</p>

<p><a id="X82069E437D2DF9AA" name="X82069E437D2DF9AA"></a></p>

<h5>42.1-2 IsPermCollection</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsPermCollection</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; IsPermCollColl</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>are the categories for collections of permutations and collections of collections of permutations, respectively.</p>

<p><a id="X819628B083B3939B" name="X819628B083B3939B"></a></p>

<h5>42.1-3 PermutationsFamily</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PermutationsFamily</code></td><td class="tdright">( family )</td></tr></table></div>
<p>is the family of all permutations.</p>

<p><a id="X7A21DE5779D21A6D" name="X7A21DE5779D21A6D"></a></p>

<h4>42.2 <span class="Heading">Comparison of Permutations</span></h4>

<p><a id="X7CEC03A9808E2E7C" name="X7CEC03A9808E2E7C"></a></p>

<h5>42.2-1 \=</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; \=</code>( <var class="Arg">p1</var>, <var class="Arg">p2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; \&lt;</code>( <var class="Arg">p1</var>, <var class="Arg">p2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>Two permutations are equal if they move the same points and all these points have the same images under both permutations.</p>

<p>The permutation <var class="Arg">p1</var> is smaller than <var class="Arg">p2</var> if <var class="Arg">p1</var> <span class="SimpleMath"></span> <var class="Arg">p2</var> and <span class="SimpleMath">i^{<var class="Arg">p1</var>} &lt; i^{<var class="Arg">p2</var>}</span>, where <span class="SimpleMath">i</span> is the smallest point with <span class="SimpleMath">i^{<var class="Arg">p1</var>} ≠ i^{<var class="Arg">p2</var>}</span>. Therefore the identity permutation is the smallest permutation, see also Section <a href="chap31.html#X7B3BC7BA7BB2646D"><span class="RefLink">31.11</span></a>.</p>

<p>Permutations can be compared with certain other <strong class="pkg">GAP</strong> objects, see <a href="chap4.html#X7A274A1F8553B7E6"><span class="RefLink">4.12</span></a> for the details.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,2,3) = (2,3,1);</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,2,3) * (2,3,4) = (1,3)(2,4);</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,2,3) &lt; (1,3,2);      # 1^(1,2,3) = 2 &lt; 3 = 1^(1,3,2)</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">(1,3,2,4) &lt; (1,3,4,2);  # 2^(1,3,2,4) = 4 &gt; 1 = 2^(1,3,4,2)</span>
false
</pre></div>

<p><a id="X7BC944F57A04AFF2" name="X7BC944F57A04AFF2"></a></p>

<h5>42.2-2 DistancePerms</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; DistancePerms</code>( <var class="Arg">perm1</var>, <var class="Arg">perm2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>returns the number of points for which <var class="Arg">perm1</var> and <var class="Arg">perm2</var> have different images. This should always produce the same result as <code class="code">NrMovePoints(<var class="Arg">perm1</var>/<var class="Arg">perm2</var>)</code> but some methods may be much faster than this form, since no new permutation needs to be created.</p>

<p><a id="X83A917F67D45C7EA" name="X83A917F67D45C7EA"></a></p>

<h5>42.2-3 SmallestGeneratorPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SmallestGeneratorPerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is the smallest permutation that generates the same cyclic group as the permutation <var class="Arg">perm</var>. This is very efficient, even when <var class="Arg">perm</var> has large order.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SmallestGeneratorPerm( (1,4,3,2) );</span>
(1,2,3,4)
</pre></div>

<p><a id="X82C255E2821C0721" name="X82C255E2821C0721"></a></p>

<h4>42.3 <span class="Heading">Moved Points of Permutations</span></h4>

<p><a id="X84EF0A697F7A87DC" name="X84EF0A697F7A87DC"></a></p>

<h5>42.3-1 SmallestMovedPoint</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SmallestMovedPoint</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SmallestMovedPoint</code>( <var class="Arg">C</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is the smallest positive integer that is moved by <var class="Arg">perm</var> if such an integer exists, and <code class="func">infinity</code> (<a href="chap18.html#X8511B8DF83324C27"><span class="RefLink">18.2-1</span></a>) if <var class="Arg">perm</var> is the identity. For <var class="Arg">C</var> a collection or list of permutations, the smallest value of <code class="func">SmallestMovedPoint</code> for the elements of <var class="Arg">C</var> is returned (and <code class="func">infinity</code> (<a href="chap18.html#X8511B8DF83324C27"><span class="RefLink">18.2-1</span></a>) if <var class="Arg">C</var> is empty).</p>

<p><a id="X84AA603987C94AC0" name="X84AA603987C94AC0"></a></p>

<h5>42.3-2 LargestMovedPoint</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; LargestMovedPoint</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; LargestMovedPoint</code>( <var class="Arg">C</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>For a permutation <var class="Arg">perm</var>, this attribute contains the largest positive integer which is moved by <var class="Arg">perm</var> if such an integer exists, and <code class="code">0</code> if <var class="Arg">perm</var> is the identity. For <var class="Arg">C</var> a collection or list of permutations, the largest value of <code class="func">LargestMovedPoint</code> for the elements of <var class="Arg">C</var> is returned (and <code class="code">0</code> if <var class="Arg">C</var> is empty).</p>

<p><a id="X85E61B9C7A6B0CCA" name="X85E61B9C7A6B0CCA"></a></p>

<h5>42.3-3 MovedPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; MovedPoints</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; MovedPoints</code>( <var class="Arg">C</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is the proper set of the positive integers moved by at least one permutation in the collection <var class="Arg">C</var>, respectively by the permutation <var class="Arg">perm</var>.</p>

<p><a id="X85E7B1E28430F49E" name="X85E7B1E28430F49E"></a></p>

<h5>42.3-4 NrMovedPoints</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; NrMovedPoints</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; NrMovedPoints</code>( <var class="Arg">C</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is the number of positive integers that are moved by <var class="Arg">perm</var>, respectively by at least one element in the collection <var class="Arg">C</var>. (The actual moved points are returned by <code class="func">MovedPoints</code> (<a href="chap42.html#X85E61B9C7A6B0CCA"><span class="RefLink">42.3-3</span></a>).)</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SmallestMovedPointPerm((4,5,6)(7,2,8));</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LargestMovedPointPerm((4,5,6)(7,2,8));</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NrMovedPointsPerm((4,5,6)(7,2,8));</span>
6
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">MovedPoints([(2,3,4),(7,6,3),(5,47)]);</span>
[ 2, 3, 4, 5, 6, 7, 47 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NrMovedPoints([(2,3,4),(7,6,3),(5,47)]);</span>
7
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]);</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]);</span>
47
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">LargestMovedPoint([()]);</span>
0
</pre></div>

<p><a id="X79BE80267F4AA2B0" name="X79BE80267F4AA2B0"></a></p>

<h4>42.4 <span class="Heading">Sign and Cycle Structure</span></h4>

<p><a id="X7BE5011B7C0DB704" name="X7BE5011B7C0DB704"></a></p>

<h5>42.4-1 SignPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; SignPerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>The <em>sign</em> of a permutation <var class="Arg">perm</var> is defined as <span class="SimpleMath">(-1)^k</span> where <span class="SimpleMath">k</span> is the number of cycles of <var class="Arg">perm</var> of even length.</p>

<p>The sign is a homomorphism from the symmetric group onto the multiplicative group <span class="SimpleMath">{ +1, -1 }</span>, the kernel of which is the alternating group.</p>

<p><a id="X7944D1447804A69A" name="X7944D1447804A69A"></a></p>

<h5>42.4-2 CycleStructurePerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; CycleStructurePerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>is the cycle structure (i.e. the numbers of cycles of different lengths) of the permutation <var class="Arg">perm</var>. This is encoded in a list <span class="SimpleMath">l</span> in the following form: The <span class="SimpleMath">i</span>-th entry of <span class="SimpleMath">l</span> contains the number of cycles of <var class="Arg">perm</var> of length <span class="SimpleMath">i+1</span>. If <var class="Arg">perm</var> contains no cycles of length <span class="SimpleMath">i+1</span> it is not bound. Cycles of length 1 are ignored.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SignPerm((1,2,3)(4,5));</span>
-1
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">CycleStructurePerm((1,2,3)(4,5,9,7,8));</span>
[ , 1,, 1 ]
</pre></div>

<p><a id="X7B3194EC869D936D" name="X7B3194EC869D936D"></a></p>

<h4>42.5 <span class="Heading">Creating Permutations</span></h4>

<p><a id="X7A9DCFD986958C1E" name="X7A9DCFD986958C1E"></a></p>

<h5>42.5-1 ListPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; ListPerm</code>( <var class="Arg">perm</var>[, <var class="Arg">length</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>is a list <span class="SimpleMath">l</span> that contains the images of the positive integers under the permutation <var class="Arg">perm</var>. That means that <span class="SimpleMath">l</span><code class="code">[</code><span class="SimpleMath">i</span><code class="code">]</code> <span class="SimpleMath">= i</span><code class="code">^</code><var class="Arg">perm</var>, where <span class="SimpleMath">i</span> lies between 1 and the largest point moved by <var class="Arg">perm</var> (see <code class="func">LargestMovedPoint</code> (<a href="chap42.html#X84AA603987C94AC0"><span class="RefLink">42.3-2</span></a>)).</p>

<p>An optional second argument specifies the length of the desired list.</p>

<p><a id="X78D611D17EA6E3BC" name="X78D611D17EA6E3BC"></a></p>

<h5>42.5-2 PermList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; PermList</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>is the permutation <span class="SimpleMath">π</span> that moves points as described by the list <var class="Arg">list</var>. That means that <span class="SimpleMath">i^π =</span> <var class="Arg">list</var><code class="code">[</code><span class="SimpleMath">i</span><code class="code">]</code> if <span class="SimpleMath">i</span> lies between <span class="SimpleMath">1</span> and the length of <var class="Arg">list</var>, and <span class="SimpleMath">i^π = i</span> if <span class="SimpleMath">i</span> is larger than the length of the list <var class="Arg">list</var>. <code class="func">PermList</code> will return <code class="keyw">fail</code> if <var class="Arg">list</var> does not define a permutation, i.e., if <var class="Arg">list</var> is not dense, or if <var class="Arg">list</var> contains a positive integer twice, or if <var class="Arg">list</var> contains an integer not in the range <code class="code">[ 1 .. Length( <var class="Arg">list</var> ) ]</code>. If <var class="Arg">list</var> contains non-integer entries an error is raised.</p>

<p><a id="X8087DCC780B9656A" name="X8087DCC780B9656A"></a></p>

<h5>42.5-3 MappingPermListList</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; MappingPermListList</code>( <var class="Arg">src</var>, <var class="Arg">dst</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">src</var> and <var class="Arg">dst</var> be lists of positive integers of the same length, such that neither may contain an element twice. <code class="func">MappingPermListList</code> returns a permutation <span class="SimpleMath">π</span> such that <var class="Arg">src</var><code class="code">[</code><span class="SimpleMath">i</span><code class="code">]^</code><span class="SimpleMath">π =</span> <var class="Arg">dst</var><code class="code">[</code><span class="SimpleMath">i</span><code class="code">]</code>. The permutation <span class="SimpleMath">π</span> fixes all points larger than the maximum of the entries in <var class="Arg">src</var> and <var class="Arg">dst</var>. If there are several such permutations, it is not specified which of them <code class="func">MappingPermListList</code> returns.</p>

<p><a id="X7EF8388E7DA8E600" name="X7EF8388E7DA8E600"></a></p>

<h5>42.5-4 RestrictedPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; RestrictedPerm</code>( <var class="Arg">perm</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; RestrictedPermNC</code>( <var class="Arg">perm</var>, <var class="Arg">list</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><code class="func">RestrictedPerm</code> returns the new permutation that acts on the points in the list <var class="Arg">list</var> in the same way as the permutation <var class="Arg">perm</var>, and that fixes those points that are not in <var class="Arg">list</var>. The resulting permutation is stored internally of degree given by the maximal entry of <var class="Arg">list</var>. <var class="Arg">list</var> must be a list of positive integers such that for each <span class="SimpleMath">i</span> in <var class="Arg">list</var> the image <span class="SimpleMath">i</span><code class="code">^</code><var class="Arg">perm</var> is also in <var class="Arg">list</var>, i.e., <var class="Arg">list</var> must be the union of cycles of <var class="Arg">perm</var>.</p>

<p><code class="func">RestrictedPermNC</code> does not check whether <var class="Arg">list</var> is a union of cycles.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ListPerm((3,4,5));</span>
[ 1, 2, 4, 5, 3 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PermList([1,2,4,5,3]);</span>
(3,4,5)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">MappingPermListList([2,5,1,6],[7,12,8,2]);</span>
(1,8,5,12,11,10,9,6,2,7,4,3)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RestrictedPerm((1,2)(3,4),[3..5]);</span>
(3,4)
</pre></div>

<p><a id="X8353AB8987E35DF3" name="X8353AB8987E35DF3"></a></p>

<h5>42.5-5 AsPermutation</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#8227; AsPermutation</code>( <var class="Arg">f</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: A permutation or <code class="keyw">fail</code>.</p>

<p>Partial permutations and transformations which define permutations (mathematically) can be converted into <strong class="pkg">GAP</strong> permutations using <code class="code">AsPermutation</code>; see Chapters <a href="chap53.html#X860026B880BCB2A5"><span class="RefLink">53</span></a> and <a href="chap54.html#X7D6495F77B8A77BD"><span class="RefLink">54</span></a> for more details about transformations and partial permutations.</p>


<dl>
<dt><strong class="Mark">for partial permutations</strong></dt>
<dd><p>If the partial permutation <var class="Arg">f</var> is a permutation of its image, then <code class="code">AsPermutation</code> returns this permutation. If <var class="Arg">f</var> does not permute its image, then <code class="keyw">fail</code> is returned.</p>

</dd>
<dt><strong class="Mark">for transformations</strong></dt>
<dd><p>A transformation is a permutation if and only if its rank equals its degree. If a transformation in <strong class="pkg">GAP</strong> is a permutation, then <code class="code">AsPermutation</code> returns this permutation. If <var class="Arg">f</var> is not a permutation, then <code class="keyw">fail</code> is returned.</p>

</dd>
</dl>
<p>The function <code class="func">Permutation</code> (<a href="chap41.html#X7807A33381DCAB26"><span class="RefLink">41.9-1</span></a>) can also be used to convert partial permutations and transformations into permutations where appropriate.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:=PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ],</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">[ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] );</span>
(1,2,7,5)(3,9)(4)(6,10,8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AsPermutation(f);</span>
(1,2,7,5)(3,9)(6,10,8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:= PartialPerm( [ 1, 2, 3, 4, 5, 7, 8 ], [ 5, 3, 8, 1, 9, 4, 10 ] );</span>
[2,3,8,10][7,4,1,5,9]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AsPermutation(f);</span>
fail
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:=Transformation( [ 5, 8, 3, 5, 8, 6, 2, 2, 7, 8 ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AsPermutation(f);</span>
fail  
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:=Transformation( [ 1, 3, 6, 6, 2, 10, 2, 3, 10, 5 ] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AsPermutation(f);</span>
fail
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f:=Transformation( [ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] );</span>
Transformation( [ 2, 7, 9, 4, 1, 10, 5, 6, 3, 8 ] )
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">AsPermutation(f);</span>
(1,2,7,5)(3,9)(6,10,8)</pre></div>


<div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap41.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap43.html">[Next Chapter]</a>&nbsp;  </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chap11.html">11</a>  <a href="chap12.html">12</a>  <a href="chap13.html">13</a>  <a href="chap14.html">14</a>  <a href="chap15.html">15</a>  <a href="chap16.html">16</a>  <a href="chap17.html">17</a>  <a href="chap18.html">18</a>  <a href="chap19.html">19</a>  <a href="chap20.html">20</a>  <a href="chap21.html">21</a>  <a href="chap22.html">22</a>  <a href="chap23.html">23</a>  <a href="chap24.html">24</a>  <a href="chap25.html">25</a>  <a href="chap26.html">26</a>  <a href="chap27.html">27</a>  <a href="chap28.html">28</a>  <a href="chap29.html">29</a>  <a href="chap30.html">30</a>  <a href="chap31.html">31</a>  <a href="chap32.html">32</a>  <a href="chap33.html">33</a>  <a href="chap34.html">34</a>  <a href="chap35.html">35</a>  <a href="chap36.html">36</a>  <a href="chap37.html">37</a>  <a href="chap38.html">38</a>  <a href="chap39.html">39</a>  <a href="chap40.html">40</a>  <a href="chap41.html">41</a>  <a href="chap42.html">42</a>  <a href="chap43.html">43</a>  <a href="chap44.html">44</a>  <a href="chap45.html">45</a>  <a href="chap46.html">46</a>  <a href="chap47.html">47</a>  <a href="chap48.html">48</a>  <a href="chap49.html">49</a>  <a href="chap50.html">50</a>  <a href="chap51.html">51</a>  <a href="chap52.html">52</a>  <a href="chap53.html">53</a>  <a href="chap54.html">54</a>  <a href="chap55.html">55</a>  <a href="chap56.html">56</a>  <a href="chap57.html">57</a>  <a href="chap58.html">58</a>  <a href="chap59.html">59</a>  <a href="chap60.html">60</a>  <a href="chap61.html">61</a>  <a href="chap62.html">62</a>  <a href="chap63.html">63</a>  <a href="chap64.html">64</a>  <a href="chap65.html">65</a>  <a href="chap66.html">66</a>  <a href="chap67.html">67</a>  <a href="chap68.html">68</a>  <a href="chap69.html">69</a>  <a href="chap70.html">70</a>  <a href="chap71.html">71</a>  <a href="chap72.html">72</a>  <a href="chap73.html">73</a>  <a href="chap74.html">74</a>  <a href="chap75.html">75</a>  <a href="chap76.html">76</a>  <a href="chap77.html">77</a>  <a href="chap78.html">78</a>  <a href="chap79.html">79</a>  <a href="chap80.html">80</a>  <a href="chap81.html">81</a>  <a href="chap82.html">82</a>  <a href="chap83.html">83</a>  <a href="chap84.html">84</a>  <a href="chap85.html">85</a>  <a href="chap86.html">86</a>  <a href="chap87.html">87</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>