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:

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


Permutation may represent permutational symmetry or antisymmetry; in order to convert symmetry to antisymmetry and vice versa one can use minus:

//antisymmetry
def asym = -[[0, 4, 2], [1, 3]].p
//symmetry
def sym = -asym

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:

def perm = [[0, 2, 5], [6, 7, 4]].p
println perm.order()
   > 3
//this will throw exception
println -perm
   > InconsistentGeneratorsException


One can apply permutation to some list using right shift operator:

def p = [[0, 1], [2, 3]].p
println p >> [10, 9, 8, 7]
   > [9, 10, 7, 8]
println p >> ['a', 'b', 'c', 'd', 'e']
   > [b, a, d, c, e]


The algebraic operations on permutations (composition, pow, inverse) can be performed in the following way:

def p = [[0, 5, 4], [1, 3]].p
//inverse
println p**(-1)
   >[[0, 4, 5], [1, 3]]
//p1 * p1 * p1
println p**(3)
   > [[1, 3]]
//inverse of (p1 * p1)
println p**(-2)
   > [[0, 5, 4]]
def oth = [[0, 1], [2, 3]].p
//apply oth after p
println p * oth
   > [[0, 5, 4, 1, 2, 3]]
//apply p after oth
println oth * p
   > [[0, 3, 2, 1, 5, 4]]

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:

def p = [[0, 5, 4], [1, 3]].p
assert p[0] == 5
assert p[4] == 0

Additional features

The following table summarises some additional features of Permutation:

.degree() returns degree of permutation, i.e. largest moved point plus one.
.order() calculates and returns the order of permutation.
.parity() returns parity of permutation (0 for even and 1 for odd).
.antisymmetry() returns whether Permutation is antisymmetry.

More specialised features of Permutation can be found in API (see JavaDocs).

See also