Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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