====== Permutations and permutation groups ======
Next topic: [[documentation:guide:programming_with_redberry]]
----
====Permutations====
Permutations play a very important role in tensor algebra. For example, [[Symmetries of tensors|symmetries of tensors]] are specified in terms of permutations of indices. Besides, permutations and permutation groups are used in many routines and algorithms with tensors (e.g. [[documentation:ref:Symmetrize]] transformation or [[mappings of indices]] are uses algorithms with permutation groups).
A single [[documentation:ref:Permutation]] in Redberry can be inputted using ''.p'' property both in cycle and one-line 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
[[documentation:ref:Permutation]] can represent both permutational symmetry and antisymmetry. In order to convert symmetry to antisymmetry and vice versa, one can use minus:
//symmetry
def sym = [[0, 2, 5], [6, 7]].p
//antisymmetry
def asym = -sym
One can use [[documentation:ref:Permutation]] to permute a list of objects via ''%%>>%%'' 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]
In order to make a composition of permutations one can simply use multiplication:
def perm1 = [[0, 5, 4], [1, 3]].p
def perm2 = [[0, 1], [2, 3]].p
println perm1*perm2
> +[[0, 5, 4, 1, 2, 3]]
println perm2*perm1
> +[[0, 3, 2, 1, 5, 4]]
The result of applying composition ''perm1*perm2'' is equivalent to applying ''perm2'' then ''perm1'':
def list = ['a', 'b', 'c', 'd', 'e', 'f']
assert (perm1 * perm2) >> list == perm1 >> (perm2 >> list)
assert (perm2 * perm1) >> list == perm2 >> (perm1 >> list)
See [[documentation:ref:Permutation]] for further details.
====Permutation groups====
In order to [[Symmetries of tensors|specify symmetries of tensors]] one should specify a generating set of permutations. Redberry uses generating set to create a [[documentation:ref:PermutationGroup]] which is used in all further routines. Redberry can handle permutation groups with degree in the range of a few thousand, hence working with groups with more than $10^{1000}$ elements.
In order to create [[documentation:ref:PermutationGroup]] directly, one can do:
def gen1 = [[1, 4, 5], [3, 6]].p
def gen2 = -[[2, 3], [1, 5]].p
def group = Group(gen1, gen2)
Giving a [[documentation:ref:PermutationGroup]], one can e.g. check its order (i.e. number of all elements in group) or enumerate all its element:
//print number of all group elements
println group.order()
> 36
//enumerate all elements
def all = []
for (def perm in group)
all << perm
//find all antisymmetries
def assyms = group.findAll { perm -> perm.antisymmetry() }
println assyms
> [-[[4,5]], -[[3,6],[4,5]], -[[2,3],[4,5]], -[[2,6,3],[4,5]], -[[2,6],[4,5]],
-[[2,3,6],[4,5]], -[[1,4],[3,6]], -[[1,4]], -[[1,4],[2,3,6]], -[[1,4],[2,6]],
-[[1,4],[2,6,3]], -[[1,4],[2,3]], -[[1,5],[2,3]], -[[1,5],[2,6,3]], -[[1,5]],
-[[1,5],[3,6]], -[[1,5],[2,3,6]], -[[1,5],[2,6]]]
[[documentation:ref:PermutationGroup]] provides a wide range of specialized methods including membership testing, coset enumeration, searching for centralizers, stabilizers, etc. For example, to check whether some permutation belongs to a group one can do
def perm1 = [[1, 2, 5]].p
println group.membershipTest(perm1)
> false
def perm2 = [[1, 4, 5]].p
println group.membershipTest(perm2)
> true
To find a subgroup that stabilizes a set of points (i.e. map set on itself "as a whole") one can do:
println group.setwiseStabilizer(1, 3, 5)
> Group( +[[2, 6]], -[[1, 5]] )
See [[documentation:ref:PermutationGroup]] for further details.
====See also====
* Related guides: [[documentation:guide:symmetries_of_tensors]]
* Related reference material: [[documentation:ref:permutation]], [[documentation:ref:permutationgroup]]