/usr/share/gap/doc/ref/chap42.html is in gap-doc 4r7p5-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"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap41.html">[Previous Chapter]</a> <a href="chap43.html">[Next Chapter]</a> </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"> </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"> </span><a href="chap42.html#X7AA69C6686FC49EA">42.1-1 IsPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X82069E437D2DF9AA">42.1-2 IsPermCollection</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X819628B083B3939B">42.1-3 PermutationsFamily</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap42.html#X7CEC03A9808E2E7C">42.2-1 \=</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X7BC944F57A04AFF2">42.2-2 DistancePerms</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X83A917F67D45C7EA">42.2-3 SmallestGeneratorPerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap42.html#X84EF0A697F7A87DC">42.3-1 SmallestMovedPoint</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X84AA603987C94AC0">42.3-2 LargestMovedPoint</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X85E61B9C7A6B0CCA">42.3-3 MovedPoints</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X85E7B1E28430F49E">42.3-4 NrMovedPoints</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap42.html#X7BE5011B7C0DB704">42.4-1 SignPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X7944D1447804A69A">42.4-2 CycleStructurePerm</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </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"> </span><a href="chap42.html#X7A9DCFD986958C1E">42.5-1 ListPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X78D611D17EA6E3BC">42.5-2 PermList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X8087DCC780B9656A">42.5-3 MappingPermListList</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap42.html#X7EF8388E7DA8E600">42.5-4 RestrictedPerm</a></span>
<span class="ContSS"><br /><span class="nocss"> </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></span> <span class="GAPinput">(1,2,3);</span>
(1,2,3)
<span class="GAPprompt">gap></span> <span class="GAPinput">(1,2,3) * (2,3,4);</span>
(1,3)(2,4)
<span class="GAPprompt">gap></span> <span class="GAPinput">17^(2,5,17,9,8);</span>
9
<span class="GAPprompt">gap></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">‣ 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">‣ 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">‣ 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">‣ PermutationsFamily</code></td><td class="tdright">( global variable )</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">‣ \=</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">‣ \<</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>} < 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></span> <span class="GAPinput">(1,2,3) = (2,3,1);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">(1,2,3) * (2,3,4) = (1,3)(2,4);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">(1,2,3) < (1,3,2); # 1^(1,2,3) = 2 < 3 = 1^(1,3,2)</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">(1,3,2,4) < (1,3,4,2); # 2^(1,3,2,4) = 4 > 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">‣ 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">‣ SmallestGeneratorPerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</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></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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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></span> <span class="GAPinput">SmallestMovedPointPerm((4,5,6)(7,2,8));</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">LargestMovedPointPerm((4,5,6)(7,2,8));</span>
8
<span class="GAPprompt">gap></span> <span class="GAPinput">NrMovedPointsPerm((4,5,6)(7,2,8));</span>
6
<span class="GAPprompt">gap></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></span> <span class="GAPinput">NrMovedPoints([(2,3,4),(7,6,3),(5,47)]);</span>
7
<span class="GAPprompt">gap></span> <span class="GAPinput">SmallestMovedPoint([(2,3,4),(7,6,3),(5,47)]);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">LargestMovedPoint([(2,3,4),(7,6,3),(5,47)]);</span>
47
<span class="GAPprompt">gap></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">‣ 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">‣ 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></span> <span class="GAPinput">SignPerm((1,2,3)(4,5));</span>
-1
<span class="GAPprompt">gap></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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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></span> <span class="GAPinput">ListPerm((3,4,5));</span>
[ 1, 2, 4, 5, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">PermList([1,2,4,5,3]);</span>
(3,4,5)
<span class="GAPprompt">gap></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></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">‣ AsPermutation</code>( <var class="Arg">f</var> )</td><td class="tdright">( operation )</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></span> <span class="GAPinput">f:=PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ],</span>
<span class="GAPprompt">></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></span> <span class="GAPinput">AsPermutation(f);</span>
(1,2,7,5)(3,9)(6,10,8)
<span class="GAPprompt">gap></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></span> <span class="GAPinput">AsPermutation(f);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=Transformation( [ 5, 8, 3, 5, 8, 6, 2, 2, 7, 8 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPermutation(f);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">f:=Transformation( [ 1, 3, 6, 6, 2, 10, 2, 3, 10, 5 ] );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsPermutation(f);</span>
fail
<span class="GAPprompt">gap></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></span> <span class="GAPinput">AsPermutation(f);</span>
(1,2,7,5)(3,9)(6,10,8)</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap41.html">[Previous Chapter]</a> <a href="chap43.html">[Next Chapter]</a> </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>
|