This shows you the differences between two versions of the page.
— |
documentation:guide:permutations_and_permutation_groups [2015/11/21 12:33] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Permutations and permutation groups ====== | ||
+ | <html> | ||
+ | <div class="text-right" style="font-size: 15px; "> | ||
+ | </html> | ||
+ | Next topic: [[documentation:guide:programming_with_redberry]] | ||
+ | <html> | ||
+ | <span class="glyphicon glyphicon-arrow-right"></span> | ||
+ | </div> | ||
+ | </html> | ||
+ | |||
+ | ---- | ||
+ | |||
+ | ====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: | ||
+ | <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> | ||
+ | [[documentation:ref:Permutation]] can represent both permutational symmetry and antisymmetry. In order to convert symmetry to antisymmetry and vice versa, one can use minus: | ||
+ | <sxh groovy; gutter: false> | ||
+ | //symmetry | ||
+ | def sym = [[0, 2, 5], [6, 7]].p | ||
+ | //antisymmetry | ||
+ | def asym = -sym | ||
+ | </sxh> | ||
+ | |||
+ | One can use [[documentation:ref:Permutation]] to permute a list of objects via ''%%>>%%'' 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> | ||
+ | |||
+ | In order to make a composition of permutations one can simply use multiplication: | ||
+ | <sxh groovy; gutter: true> | ||
+ | def perm1 = [[0, 5, 4], [1, 3]].p | ||
+ | def perm2 = [[0, 1], [2, 3]].p | ||
+ | println perm1*perm2 | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > +[[0, 5, 4, 1, 2, 3]] | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 4> | ||
+ | println perm2*perm1 | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > +[[0, 3, 2, 1, 5, 4]] | ||
+ | </sxh> | ||
+ | The result of applying composition ''perm1*perm2'' is equivalent to applying ''perm2'' then ''perm1'': | ||
+ | <sxh groovy; gutter: true; first-line: 5> | ||
+ | def list = ['a', 'b', 'c', 'd', 'e', 'f'] | ||
+ | assert (perm1 * perm2) >> list == perm1 >> (perm2 >> list) | ||
+ | assert (perm2 * perm1) >> list == perm2 >> (perm1 >> list) | ||
+ | </sxh> | ||
+ | |||
+ | 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: | ||
+ | <sxh groovy; gutter: true> | ||
+ | def gen1 = [[1, 4, 5], [3, 6]].p | ||
+ | def gen2 = -[[2, 3], [1, 5]].p | ||
+ | def group = Group(gen1, gen2) | ||
+ | </sxh> | ||
+ | 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: | ||
+ | <sxh groovy; gutter: true; first-line: 4> | ||
+ | //print number of all group elements | ||
+ | println group.order() | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > 36 | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 6> | ||
+ | //enumerate all elements | ||
+ | def all = [] | ||
+ | for (def perm in group) | ||
+ | all << perm | ||
+ | //find all antisymmetries | ||
+ | def assyms = group.findAll { perm -> perm.antisymmetry() } | ||
+ | println assyms | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > [-[[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]]] | ||
+ | </sxh> | ||
+ | |||
+ | |||
+ | [[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 | ||
+ | <sxh groovy; gutter: true; first-line: 13> | ||
+ | def perm1 = [[1, 2, 5]].p | ||
+ | println group.membershipTest(perm1) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > false | ||
+ | </sxh> | ||
+ | <sxh groovy; gutter: true; first-line: 15> | ||
+ | def perm2 = [[1, 4, 5]].p | ||
+ | println group.membershipTest(perm2) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > true | ||
+ | </sxh> | ||
+ | To find a subgroup that stabilizes a set of points (i.e. map set on itself "as a whole") one can do: | ||
+ | <sxh groovy; gutter: true; first-line: 17> | ||
+ | println group.setwiseStabilizer(1, 3, 5) | ||
+ | </sxh> | ||
+ | <sxh plain; gutter: false> | ||
+ | > Group( +[[2, 6]], -[[1, 5]] ) | ||
+ | </sxh> | ||
+ | |||
+ | 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]] | ||