This shows you the differences between two versions of the page.
documentation:ref:permutation [2015/11/21 12:33] |
documentation:ref:permutation [2015/11/21 12:33] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Permutation ====== | ||
+ | |||
+ | ---- | ||
+ | ====Basics==== | ||
+ | |||
+ | * ''Permutation'' represents a mathematical permutation. | ||
+ | |||
+ | * ''Permutation'' can be inputted in both //one-line// and //cycle// notation using ''.p'' property. | ||
+ | |||
+ | * ''Permutation'' can can represent both permutational symmetry or antisymmetry. | ||
+ | |||
+ | * ''[].p'' represents identity permutation. | ||
+ | |||
+ | * Internally, Redberry stores ''Permutation'' in ''byte[]'', ''short[]'' or ''int[]'' array dynamically choosing the representation according to the degree of permutation. | ||
+ | ====Examples==== | ||
+ | Input ''Permutation'' in one-line or cycle notation: | ||
+ | <sxh groovy; gutter: false> | ||
+ | //permutation in one-line notation | ||
+ | def p1 = [0, 2, 5, 6, 7, 1, 3, 4].p | ||
+ | //same permutation in cycle notation | ||
+ | def p2 = [[1, 2, 5], [4, 7], [3, 6]].p | ||
+ | assert p1 == p2 | ||
+ | </sxh> | ||
+ | |||
+ | ---- | ||
+ | ''Permutation'' may represent permutational symmetry or antisymmetry; in order to convert symmetry to antisymmetry and vice versa one can use minus: | ||
+ | <sxh groovy; gutter: false> | ||
+ | //antisymmetry | ||
+ | def asym = -[[0, 4, 2], [1, 3]].p | ||
+ | //symmetry | ||
+ | def sym = -asym | ||
+ | </sxh> | ||
+ | |||
+ | One should be careful when inputting antisymmetries, since if a permutation order is odd (i.e. $p^r = 1$, where $p$ is a permutation and $r$ its order which is odd), then, obviously, such antisymmetry is inconsistent and Redberry will throw exception: | ||
+ | <sxh groovy; gutter: true> | ||
+ | def perm = [[0, 2, 5], [6, 7, 4]].p | ||
+ | println perm.order() | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > 3 | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 3> | ||
+ | //this will throw exception | ||
+ | println -perm | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > InconsistentGeneratorsException | ||
+ | </sxh> | ||
+ | |||
+ | ---- | ||
+ | One can apply permutation to some list using right shift operator: | ||
+ | <sxh groovy; gutter: true> | ||
+ | def p = [[0, 1], [2, 3]].p | ||
+ | println p >> [10, 9, 8, 7] | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [9, 10, 7, 8] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 3> | ||
+ | println p >> ['a', 'b', 'c', 'd', 'e'] | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [b, a, d, c, e] | ||
+ | </sxh> | ||
+ | |||
+ | ---- | ||
+ | The algebraic operations on permutations (composition, pow, inverse) can be performed in the following way: | ||
+ | <sxh groovy; gutter: true> | ||
+ | def p = [[0, 5, 4], [1, 3]].p | ||
+ | //inverse | ||
+ | println p**(-1) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | >[[0, 4, 5], [1, 3]] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 4> | ||
+ | //p1 * p1 * p1 | ||
+ | println p**(3) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [[1, 3]] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 6> | ||
+ | //inverse of (p1 * p1) | ||
+ | println p**(-2) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [[0, 5, 4]] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 8> | ||
+ | def oth = [[0, 1], [2, 3]].p | ||
+ | //apply oth after p | ||
+ | println p * oth | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [[0, 5, 4, 1, 2, 3]] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 11> | ||
+ | //apply p after oth | ||
+ | println oth * p | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [[0, 3, 2, 1, 5, 4]] | ||
+ | </sxh> | ||
+ | |||
+ | The convention on composition of permutations is the following: if ''a'' and ''b'' two permutations, then the result of applying composition ''a*b'' is equivalent to applying ''b'' after ''a''. | ||
+ | |||
+ | ---- | ||
+ | In order to obtain a new position of //i//-th element under permutation one can use ''[]'' operator: | ||
+ | <sxh groovy; gutter: false> | ||
+ | def p = [[0, 5, 4], [1, 3]].p | ||
+ | assert p[0] == 5 | ||
+ | assert p[4] == 0 | ||
+ | </sxh> | ||
+ | ====Additional features==== | ||
+ | The following table summarises some additional features of ''Permutation'': | ||
+ | <html> | ||
+ | <center> | ||
+ | <table style="width:600px;" cellpadding="10"> | ||
+ | <tr> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;"><code>.degree()</code></td> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;">returns <i>degree</i> of permutation, i.e. largest moved point plus one.</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;"><code>.order()</code></td> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;">calculates and returns the order of permutation.</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;"><code>.parity()</code></td> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;">returns parity of permutation (<code>0</code> for even and <code>1</code> for odd).</td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;"><code>.antisymmetry()</code></td> | ||
+ | <td valign="top" style="padding: 15px; border: 1px solid gray;">returns whether <code>Permutation</code> is antisymmetry.</td> | ||
+ | </tr> | ||
+ | </table> | ||
+ | </center> | ||
+ | </html> | ||
+ | |||
+ | More specialised features of ''Permutation'' can be found in API (see [[#See also| JavaDocs]]). | ||
+ | |||
+ | =====See also===== | ||
+ | * Related guides: [[documentation:guide:Permutations and permutation groups]] | ||
+ | * Related reference material: [[documentation:ref:permutationgroup]] | ||
+ | * JavaDocs: [[http://api.redberry.cc/redberry/1.1.9/java-api/cc/redberry/core/groups/permutations/Permutation.html| Permutation]] | ||
+ | * Source code: [[https://bitbucket.org/redberry/redberry/src/tip/core/src/main/java/cc/redberry/core/groups/permutations/Permutation.java|Permutation.java]] | ||