<h3>8 <span class="Heading">Properties of Permutations </span></h3>
<p>It has been of interest to the authors to compute different properties of permutations. Inspections include plus- and minus-decomposable permutations, block-decompositions of permutations, as well as the computation of the direct and skew sum of permutations. First a couple of definitions on which some of the properties are based on:</p>
<p>An interval of a permutation <span class="SimpleMath">σ</span> is a set of contiguous values which in <span class="SimpleMath">σ</span> have consecutive indices.</p>
<p>A permutation of length <span class="SimpleMath">n</span> is called simple if it only contains the intervals of length 0, 1 and <span class="SimpleMath">n</span>.</p>
<h4>8.1 <span class="Heading"> Intervals in Permutations </span></h4>
<p>As mentioned above, an interval of a permutation <span class="SimpleMath">σ</span> is a set of contiguous numbers which in <span class="SimpleMath">σ</span> have consecutive indices. For example in <span class="SimpleMath">σ = 4 6 8 7 1 5 2 3</span> the following is an interval <span class="SimpleMath">σ(2)σ(3)σ(4)=6 8 7</span> whereas <span class="SimpleMath">σ(4)σ(5)σ(6)=7 1 5</span> is not.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsSimplePerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <code class="code">perm</code> is simple.</p>
<p>To check whether <code class="code">perm</code> (length of <code class="code">perm</code> = <span class="SimpleMath">n</span>) is a simple permutation <code class="code">IsSimplePerm</code> uses the basic algorithm proposed by Uno and Yagiura in <a href="chapBib.html#biBFAlgsEnumAllCommIntsof2Perms">[UY00]</a> to compare the <code class="code">perm</code> against the identity permutation of the same length.</p>
<h4>8.3 <span class="Heading"> Point Deletion in Simple Permutations </span></h4>
<p>In <a href="chapBib.html#biBSimpPermsPoset">[PR12]</a> it is shown how one can get chains of permutations by starting with a simple permutation and then removing either a single point or two points and the resulting permutation would still be simple. We have applied this theory to create functions such that the set of simple permutations of shorter length, by one deletion, can be found.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnePointDelete</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list of simple permutations with one point less than <code class="code">perm</code>.</p>
<p><code class="code">OnePointDelete</code> removes single points in the simple permutation and returns a list of the resulting simple permutations, in their rank encoding.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TwoPointDelete</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The exceptional permutation with two point less than <code class="code">perm</code>.</p>
<p><code class="code">TwoPointDelete</code> removes two points of the input exceptional permutation and returns the list of the unique resulting permutation, in its rank encoding.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PointDeletion</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list of simple permutations with of shorter length than <code class="code">perm</code>.</p>
<p><code class="code">PointDeletion</code> takes any simple permutation does not matter whether exceptional or not and removes the right number of points.</p>
<p>Given a permutation <span class="SimpleMath">π</span> of length <span class="SimpleMath">m</span> and nonempty permutations <span class="SimpleMath">α_1,...,α_m</span> the inflation of <span class="SimpleMath">π</span> by <span class="SimpleMath">α_1,...,α_m</span>, written as <span class="SimpleMath">π[α_1,...,α_m]</span>, is the permutation obtained by replacing each entry <span class="SimpleMath">π(i)</span> by an interval that is order isomorphic to <span class="SimpleMath">α_i</span> <a href="chapBib.html#biBSimpSurv">[Bri08]</a>. Conversely a block-decomposition of <span class="SimpleMath">σ</span> is any expression of <span class="SimpleMath">σ</span> as an inflation <span class="SimpleMath">σ=π[α_1,...,α_m]</span>. The block decomposition of a permutation is unique if and only if <span class="SimpleMath">σ,π,α_1,...,α_n</span> all are in the same pattern class and <span class="SimpleMath">π</span> is simple and <span class="SimpleMath">π≠ 1 2, 2 1</span> <a href="chapBib.html#biBSimpAndPRestrPerms">[AA05]</a>.</p>
<p>For example the inflation of <span class="SimpleMath">25413[21,1,1,1,2413]=3 2 8 9 1 5 7 4 6</span>, written in <strong class="pkg">GAP</strong> this is <code class="code">[[2,5,4,1,3],[2,1],[1],[1],[1],[2,4,1,3]]</code>. This decomposition of <span class="SimpleMath">3 2 8 9 1 5 7 4 6</span> is not unique. The unique block-decomposition, as described above, for <span class="SimpleMath">3 2 8 9 1 5 7 4 6=2413[21,12,1,2413]</span> or in <strong class="pkg">GAP</strong> notation <code class="code">[3,2,8,9,1,5,7,4,6]=[[2,4,1,3],[2,1],[1,2],[1],[2,4,1,3]]</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Inflation</code>( <var class="Arg">list_of_perms</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A permutation that represents the inflation of the list of permutations, taking the first permutation to be <span class="SimpleMath">π</span>, as described in the definition of inflation.</p>
<p>Inflation takes the list of permutations that stand for a box decomposition of a permutation, and calculates that permutation by replacing each entry <span class="SimpleMath">i</span> in the first permutation by an interval order isomorphic to the permutation in index <span class="SimpleMath">i+1</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BlockDecomposition</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list of permutations, representing the block-decomposition of <code class="code">perm</code>. In the list the first permutation is <span class="SimpleMath">π</span>, as described in the definiton of block-decomposition above.</p>
<p><code class="code">BlockDecomposition</code> takes a plus- and minus-indecomposable permutation and decomposes it into its maximal maximal intervals, which are preceded by the simple permutation that represents the positions of the intervals. If a plus- or minus-decomposable permutation is input, then the decomposition will not be the unique decomposition, by the definition of plus- or minus- decomposable permutations, see below.</p>
<p>A permutation <span class="SimpleMath">σ</span> is said to be plus-decomposable if it can be written uniquely in the following form,</p>
<p class="pcenter">σ = 12 [α_1,α_2]</p>
<p>where <span class="SimpleMath">α_1</span> is not plus-decomposable.</p>
<p>The subset of a rational class, containing all permutations that are plus-decomposable and in the class, has been found to be also rational under the rank encoding.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsPlusDecomposable</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <code class="code">perm</code> is plus-decomposable.</p>
<p>To check whether <code class="code">perm</code> is a plus-decomposable permutation <code class="code">IsPlusDecomposable</code> uses the fact that there has to be an interval <span class="SimpleMath">1..x</span> where <span class="SimpleMath">x <n</span> (<span class="SimpleMath">n</span> = length of the <code class="code">perm</code>) in the rank encoded permutation that is a valid rank encoding.</p>
<p>Minus-decomposability is essentially the same as plus-decomposability, the difference is that if a permutation <span class="SimpleMath">σ</span> is minus-decomposable, it can be written uniquely in the following form,</p>
<p class="pcenter">σ = 21 [α_1,α_2]</p>
<p>where <span class="SimpleMath">α_1</span> is not minus-decomposable.</p>
<p>Here also, the subset of a rational class, containing all permutations that are minus-decomposable and in the class, has been found to be rational under the rank encoding.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsMinusDecomposable</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">true</code> if <code class="code">perm</code> is minus-decomposable.</p>
<p>To check whether <code class="code">perm</code> (length of <code class="code">perm</code> = <span class="SimpleMath">n</span>) is a minus-decomposable permutation <code class="code">IsMinusDecomposable</code> uses the fact that the first <span class="SimpleMath">n-x</span>, where <span class="SimpleMath">x<n</span>, letters in the rank encoding of <code class="code">perm</code> have to be <span class="SimpleMath">>x</span> and that the letters from position <span class="SimpleMath">x+1</span> until the last one have to be <span class="SimpleMath">≤ x</span>.</p>
<p>The calculation of the direct and skew sums of permutations using the rank encoding is also straight forward and is used in the functions described below. The direct sum of two permutations <span class="SimpleMath">σ,τ</span> represented as their rank encoded sequences is the permutation which has the rank encoding that is the concatention of the rank encoding of <span class="SimpleMath">σ</span> and <span class="SimpleMath">τ</span>. The skew sum of two permutations <span class="SimpleMath">σ,τ</span> encoded by the rank encoding is the concatenation of the rank encodings of <span class="SimpleMath">σ</span> and <span class="SimpleMath">τ</span> where in the sequence corresponding to <span class="SimpleMath">σ</span> under the rank encoding each element has been increased by <span class="SimpleMath">l</span>, with <span class="SimpleMath">l</span> being the length of <span class="SimpleMath">τ</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermDirectSum</code>( <var class="Arg">perm1</var>, <var class="Arg">perm2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A permutation resulting from <code class="code">perm1</code> <span class="SimpleMath">⊕</span> <code class="code">perm2</code>.</p>
<p><code class="code">PermDirectSum</code> returns the permutation corresponding to <code class="code">perm1</code> <span class="SimpleMath">⊕</span> <code class="code">perm2</code> if <code class="code">perm1</code> and <code class="code">perm2</code> are both not rank encoded. If both <code class="code">perm1</code> and <code class="code">perm2</code> are rank encoded, then <code class="code">PermDirectSum</code> returns a rank encoded sequence.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PermSkewSum</code>( <var class="Arg">perm1</var>, <var class="Arg">perm2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A permutation resulting from <code class="code">perm1</code> <span class="SimpleMath">⊖</span> <code class="code">perm2</code>.</p>
<p><code class="code">PermSkewSum</code> returns the permutation corresponding to <code class="code">perm1</code> <span class="SimpleMath">⊖</span> <code class="code">perm2</code> if <code class="code">perm1</code> and <code class="code">perm2</code> are both not rank encoded. If both <code class="code">perm1</code> and <code class="code">perm2</code> are rank encoded, then <code class="code">PermSkewSum</code> returns a rank encoded sequence.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
