<?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 (PatternClass) - Chapter 3: Permutation Encoding</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="chap3"  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="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="chap2.html">[Previous Chapter]</a>    <a href="chap4.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap3_mj.html">[MathJax on]</a></p>
<p><a id="X8696E21E80C1AEC1" name="X8696E21E80C1AEC1"></a></p>
<div class="ChapSects"><a href="chap3.html#X8696E21E80C1AEC1">3 <span class="Heading">Permutation Encoding</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap3.html#X793F8BF48048365F">3.1 <span class="Heading"> Encoding and Decoding </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X8143AF3D79F4CC1D">3.1-1 RankEncoding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X7DA97A7B7C8EB18A">3.1-2 RankDecoding</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap3.html#X832A1FEC7E5491EA">3.1-3 SequencesToRatExp</a></span>
</div></div>
</div>

<h3>3 <span class="Heading">Permutation Encoding</span></h3>

<p>A permutation <span class="SimpleMath">π=π_1 ... π_n</span> has rank encoding <span class="SimpleMath">p_1 ... p_n</span> where <span class="SimpleMath">p_i= |{j : j ≥ i, π_j ≤ π_i } |</span>. In other words the rank encoded permutation is a sequence of <span class="SimpleMath">p_i</span> with <span class="SimpleMath">1≤ i≤ n</span>, where <span class="SimpleMath">p_i</span> is the rank of <span class="SimpleMath">π_i</span> in <span class="SimpleMath">{π_i,π_i+1,... ,π_n}</span>. <a href="chapBib.html#biBRegCloSetPerms">[AAR03]</a></p>

<p>The encoding of the permutation 3 2 5 1 6 7 4 8 9 is done as follows:</p>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Permutation</td>
<td class="tdcenter">Encoding</td>
<td class="tdcenter">Assisting list</td>
</tr>
<tr>
<td class="tdcenter">325167489</td>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
<td class="tdcenter">123456789</td>
</tr>
<tr>
<td class="tdcenter">25167489</td>
<td class="tdcenter">3</td>
<td class="tdcenter">12456789</td>
</tr>
<tr>
<td class="tdcenter">5167489</td>
<td class="tdcenter">32</td>
<td class="tdcenter">1456789</td>
</tr>
<tr>
<td class="tdcenter">167489</td>
<td class="tdcenter">323</td>
<td class="tdcenter">146789</td>
</tr>
<tr>
<td class="tdcenter">67489</td>
<td class="tdcenter">3231</td>
<td class="tdcenter">46789</td>
</tr>
<tr>
<td class="tdcenter">7489</td>
<td class="tdcenter">32312</td>
<td class="tdcenter">4789</td>
</tr>
<tr>
<td class="tdcenter">489</td>
<td class="tdcenter">323122</td>
<td class="tdcenter">489</td>
</tr>
<tr>
<td class="tdcenter">89</td>
<td class="tdcenter">3231221</td>
<td class="tdcenter">89</td>
</tr>
<tr>
<td class="tdcenter">9</td>
<td class="tdcenter">32312211</td>
<td class="tdcenter">9</td>
</tr>
<tr>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
<td class="tdcenter">323122111</td>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
</tr>
</table><br />
</div>

<p>Decoding a permutation is done in a similar fashion, taking the sequence <span class="SimpleMath">p_1 ... p_n</span> and using the reverse process will lead to the permutation <span class="SimpleMath">π=π_1 ... π_n</span>, where <span class="SimpleMath">π_i</span> is determined by finding the number that has rank <span class="SimpleMath">p_i</span> in <span class="SimpleMath">{π_i, π_i+1, ... , π_n}</span>.</p>

<p>The sequence 3 2 3 1 2 2 1 1 1 is decoded as:</p>

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">Encoding</td>
<td class="tdcenter">Permutation</td>
<td class="tdcenter">Assisting list</td>
</tr>
<tr>
<td class="tdcenter">323122111</td>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
<td class="tdcenter">123456789</td>
</tr>
<tr>
<td class="tdcenter">23122111</td>
<td class="tdcenter">3</td>
<td class="tdcenter">12456789</td>
</tr>
<tr>
<td class="tdcenter">3122111</td>
<td class="tdcenter">32</td>
<td class="tdcenter">1456789</td>
</tr>
<tr>
<td class="tdcenter">122111</td>
<td class="tdcenter">325</td>
<td class="tdcenter">146789</td>
</tr>
<tr>
<td class="tdcenter">22111</td>
<td class="tdcenter">3251</td>
<td class="tdcenter">46789</td>
</tr>
<tr>
<td class="tdcenter">2111</td>
<td class="tdcenter">32516</td>
<td class="tdcenter">4789</td>
</tr>
<tr>
<td class="tdcenter">111</td>
<td class="tdcenter">325167</td>
<td class="tdcenter">489</td>
</tr>
<tr>
<td class="tdcenter">11</td>
<td class="tdcenter">3251674</td>
<td class="tdcenter">89</td>
</tr>
<tr>
<td class="tdcenter">1</td>
<td class="tdcenter">32516748</td>
<td class="tdcenter">9</td>
</tr>
<tr>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
<td class="tdcenter">325167489</td>
<td class="tdcenter"><span class="SimpleMath">∅</span></td>
</tr>
</table><br />
</div>

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

<h4>3.1 <span class="Heading"> Encoding and Decoding </span></h4>

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

<h5>3.1-1 RankEncoding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RankEncoding</code>( <var class="Arg">p</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list that represents the rank encoding of the permutation <code class="code">p</code>.</p>

<p>Using the algorithm above <code class="code">RankEncoding</code> turns the permutation <code class="code">p</code> into a list of integers.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RankEncoding([3, 2, 5, 1, 6, 7, 4, 8, 9]);</span>
[ 3, 2, 3, 1, 2, 2, 1, 1, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RankEncoding([ 4, 2, 3, 5, 1 ]);                 </span>
[ 4, 2, 2, 2, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>3.1-2 RankDecoding</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RankDecoding</code>( <var class="Arg">e</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A permutation in list form.</p>

<p>A rank encoded permutation is decoded by using the reversed process from encoding, which is also explained above.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RankDecoding([ 3, 2, 3, 1, 2, 2, 1, 1, 1 ]);</span>
[ 3, 2, 5, 1, 6, 7, 4, 8, 9 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RankDecoding([ 4, 2, 2, 2, 1 ]);</span>
[ 4, 2, 3, 5, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>3.1-3 SequencesToRatExp</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SequencesToRatExp</code>( <var class="Arg">list</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A rational expression that describes all the words in <code class="code">list</code>.</p>

<p>A list of sequences is turned into a rational expression by concatenating each sequence and unifying all of them.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SequencesToRatExp([[ 1, 1, 1, 1, 1 ],[ 2, 1, 2, 2, 1 ],[ 3, 2, 1, 2, 1 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ 4, 2, 3, 2, 1 ]]);</span>
11111U21221U32121U42321
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap2.html">[Previous Chapter]</a>    <a href="chap4.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="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

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