# Differences

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

 — documentation:ref:permutationgroup [2015/11/21 12:33] (current) Line 1: Line 1: + ====== PermutationGroup ====== + ---- + =====Basics===== + + * ''​PermutationGroup''​ represents a group of permutations. ​ + ​ + * Redberry can handle permutation groups ​ with degree in the range of a few thousand, hence working with groups with more than $10^{1000}$ ​ elements. + + * ''​PermutationGroup''​ can be specified by its generating set: + + def gen1 = [[1, 4, 5]].p + def gen2 = [[2, 3]].p + def group = Group(gen1, gen2) + //print all group elements + group.each { println it } + ​ + + > +[] + > +[[2, 3]] + > +[[1, 5, 4]] + > +[[1, 5, 4], [2, 3]] + > +[[1, 4, 5]] + > +[[1, 4, 5], [2, 3]] + ​ + + * One can construct a special kinds of ''​PermutationGroup'':​ symmetric or alternating by using ''​SymmetricGroup(degree)''​ and  ''​AlternatingGroup(degree)''​ respectively:​ + + def sym69 = SymmetricGroup(69) + println sym69.order() + ​ + + > 17112245242814131137246833888127283909227054489352036939364804092325 + 7279754140647424000000000000000 + ​ + + def alt54 = AlternatingGroup(54) + println alt54.order() + ​ + + > 115421848669620690236046371341513790541639282285903970566144000000000000 + ​ + + + + * ''​PermutationGroup''​ provides a number of common methods for working wih permutation groups: ​ membership testing, coset enumeration,​ searching for centralizers,​ stabilizers,​ etc. One can find many examples in below subsections. + =====Examples===== + Let us consider some common features of ''​PermutationGroup''​ by a particular examples. Consider the following permutation group: + + //first generator in cycle notation + def perm1 = [[1,​28,​5,​3,​13,​25,​8,​4,​17,​11,​29,​7,​2,​21,​23,​10,​6],​ + [9,​16,​22,​30,​18,​15,​20,​19,​14]].p + //second generator in cycle notation + def perm2 = [[1, 4, 27], [2, 5, 3]].p + //create group + def group = Group(perm1,​ perm2) + ​ + ---- + * Print group order (i.e. number of all elements): + + println group.order() + ​ + + > 28810681675776000 + ​ + ---- + * Get orbit of some point: + + println group.orbit(20) + ​ + + > [9, 16, 22, 30, 18, 15, 20, 19, 14] + ​ + ---- + * Get a pointwise stabilizer (i.e. subgroup that fixes specified points) + + def pStabilizer =  group.pointwiseStabilizer(3,​ 25, 27) + println pStabilizer + ​ + + > Group( +[[9, 16, 22, 30, 18, 15, 20, 19, 14]], + +[[1, 17, 11, 21, 23, 28, 5, 29, 7, 2, 13, 8, 4, 10, 6]], + +[[1, 29, 2, 17, 7, 6, 23, 8, 21, 13, 11], [4, 10, 28]]) + ​ + + println pStabilizer.order() + ​ + + > 5884534656000 + ​ + ---- + * Check membership (i.e. whether some permutation belongs to ''​PermutationGroup''​) + + def p = [[1, 28, 2, 8, 27, 10, 11], [21, 29, 23]].p + println group.membershipTest(p) + ​ + + > true + ​ + + def n = [[7, 19, 5, 17, 3, 4, 21, 25]].p + println group.membershipTest(n) + ​ + + > false + ​ + ---- + * Calculate a setwise stabiliser (i.e. a subgroup that fixes a set as a whole): + + def sStabilizer = group.setwiseStabilizer(3,​ 27, 25) + println sStabilizer ​ + ​ + + > Group( +[[9, 16, 22, 30, 18, 15, 20, 19, 14]], + +[[1, 17, 11, 21, 23, 28, 5, 29, 7, 2, 13, 8, 4, 10, 6]], + +[[1, 29, 2, 17, 7, 6, 23, 8, 21, 13, 11], [4, 10, 28]], + +[[1, 4], [25, 27]], +[[1, 4], [3, 25]] ) + ​ + + println sStabilizer.order() + ​ + + > 35307207936000 + ​ + ---- + * Calculate derived subgroup (i.e. a commutator subgroup of group with itself): + + def dSubgroup = group.derivedSubgroup() + println dSubgroup.order() + ​ + + > 3201186852864000 + ​ + ---- + * Define some other group and check whether it is a subgroup of group: + + def oth = Group([[1, 17, 12, 19], [23, 25]].p, [[4, 14, 26]].p) + println group.containsSubgroup(oth) + ​ + + > false + ​ + ---- + * Calculate union of groups: + + def union = group.union(oth) + assert union.containsSubgroup(group) + assert union.containsSubgroup(oth) + + println union.order() + ​ + + > 4420880996869850977271808000000 + ​ + ---- + * Calculate intersection of groups: + + def intersection = union.intersection(group) + assert intersection == group + ​ + ---- + * Calculate coset representatives:​ + + println sStabilizer.leftCosetRepresentatives(pStabilizer) + ​ + + > [+[], + +[[1, 4], [25, 27]], + +[[1, 4], [3, 25]], + +[[3, 25, 27]], + +[[3, 27, 25]], + +[[1, 4], [3, 27]]] + ​ + ---- + * Calculate centralizer of subgroup: + + println group.centralizerOf(sStabilizer) + ​ + + > Group( +[[9, 14, 19, 20, 15, 18, 30, 22, 16]] ) + ​ + + =====Features===== + ====General features==== + The following table lists relevant features of ''​PermutationGroup'':​ + <​html>​ + ​ +
<​code>​.center()​ + ​center of group. ​ +
<​code>​.centralizerOf(perm)​ + ​centralizer of permutation <​code>​perm​.  ​ +
<​code>​.centralizerOf(group)​.​ + ​centralizer of subgroup <​code>​group​.  ​ +
<​code>​.commutator(oth)​ + ​commutator with <​code>​oth​ group. ​ +
<​code>​.conjugate(perm)​ + ​conjugation of group with specified permutation <​code>​perm​( i.e.  $p^{-1} G p$, where $p$ is <​code>​perm​ and $G$ is a group). ​ +
<​code>​.containsSubgroup(oth)​ + ​returns whether group contains subgroup <​code>​oth​. ​ +
<​code>​.degree()​ + ​natural degree of group, i.e. largest moved point plus one. ​ +
<​code>​.derivedSubgroup()​ + ​derived subgroup, i.e. commutator subgroup of group with itself. ​ +
<​code>​. directProduct(oth)​ + ​direct product of group <​code>​oth​ group. This product is organized as follows: the initial segment of each permutation is equal to permutation taken from group, while the rest is taken from permutation of <​code>​oth​. ​ +
<​code>​. equals(oth)​ + ​returns whether group is equal to <​code>​oth​ in mathematical sense. ​ +
<​code>​.generators()​ + ​a list of group generators. ​ +
<​code>​. base​ + ​base of group. ​ +
<​code>​. getBSGS()​ + ​low level representation of base and strong generating set. ​ +
<​code>​. intersection(oth)​ + ​intersection of group with <​code>​oth​. ​ +
<​code>​. isAbelian()​ + ​returns whether group is abelian. ​ +
<​code>​. isAlternating()​ + ​returns whether group is alternating. ​ +
<​code>​. isRegular()​ + ​returns whether group is regular (i.e. transitive and its order equals to degree). ​ +
<​code>​. isSymmetric()​ + ​returns whether group is symmetric. ​ +
<​code>​. isTransitive()​ + ​returns whether group is transitive. ​ +
<​code>​. isTransitive(from,​ to)​ + ​returns whether group acts transitively on the the range <​code>​from​ (inclusive) to <​code>​to​ (exclusive). ​ +
<​code>​. isTrivial()​ + ​returns whether group is trivial (contains only identity element). ​ +
<​code>​. leftCosetRepresentatives(subgroup)​ + ​array of left coset representatives of a <​code>​subgroup​. ​ +
<​code>​. leftTransversalOf(subgroup,​ perm)​ + ​ a unique left coset representative of <​code>​perm​. ​ +
<​code>​. mapping(from,​ to)​ + ​ iterator over permutations that maps <​code>​from​ points on <​code>​to​. ​ +
<​code>​. membershipTest(perm)​ + ​ returns whether <​code>​perm<​code>​ belongs to group. ​ +
<​code>​. normalClosureOf(subgroup)​ + ​ normal closure of specified <​code>​subgroup​. ​ +
<​code>​. orbit(points)​ + ​ orbit of <​code>​points​. ​ +
<​code>​.order()​ + ​group order (i.e. number of all elements). ​ +
<​code>​. pointwiseStabilizer(set)​ + ​pointwise stabilizer of specified <​code>​set​ of points. ​ +
<​code>​. randomElement()​ + ​uniformly distributed random element from group. ​ +
<​code>​. rightCosetRepresentatives(subgroup)​ + ​array of right coset representatives of a <​code>​subgroup​. ​ +
<​code>​. setwiseStabilizer(set)​ + ​pointwise stabilizer of specified <​code>​set​ of points. ​ +
<​code>​. union(oth)​ + ​union of group and specified group (or set of generators),​ i.e. group which is generated by union of generators of group and <​code>​oth​. ​ +
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + ​ + ​ + + ====Orbits==== + One can take an orbit of some point using method ''​.orbit(point)'':​ + + def perm1 = [[0, 7, 4, 2, 10], [8, 5, 9]].p + def perm2 = [[0, 3, 6], [1, 4, 2]].p + def group = Group(perm1,​ perm2) + + println group.orbit(2) + ​ + + > [0, 7, 3, 4, 6, 2, 10, 1] + ​ + + println group.orbit(5) + ​ + + > [5, 9, 8] + ​ + In order to take a list of all orbits one can do + + def orbits = group.orbits() + println orbits + ​ + + > [[0, 7, 3, 4, 6, 2, 10, 1], [5, 9, 8]] + ​ + Given a list of all orbits, one can take an orbit of specified point by using array ''​positionsInOrbits'':​ an //i//-th element in this array is an index of orbit of //i//-th point in array of ''​orbits'':​ + + def poss = group.positionsInOrbits + println poss + ​ + + > [0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0] + ​ + + //orbit of 2 + println orbits[poss[2]] + ​ + + > [0, 7, 3, 4, 6, 2, 10, 1] + ​ + + //orbit of 5 + println orbits[poss[5]] + ​ + + > [5, 9, 8] + ​ + + //check + for (int i = 0; i < group.degree();​ ++i) + assert group.orbit(i) == orbits[poss[i]] + ​ + + + =====Details===== + The implementation of most ''​PermutationGroup''​ methods relies on base and strong generating set (BSGS). The algorithms such as used in calculation of groups intersections,​ centralizers ​ etc. uses backtracking techniques. + + + Consider for example the stabilizers chain of Rubik group: + + def rot1 = [[0, 2, 7, 5], [1, 4, 6, 3], + [8, 47, 14, 11], [9, 46, 15, 12], + [10, 45, 16, 13]].p + def rot2 = [[5, 14, 34, 25], [6, 21, 33, 18], + [7, 29, 32, 10], [11, 13, 28, 26], + [12, 20, 27, 19]].p + def rot3 = [[0, 11, 32, 40], [3, 19, 35, 43], + [5, 26, 37, 45], [8, 10, 25, 23], + [9, 18, 24, 17]].p + def rot4 = [[0, 23, 39, 16], [1, 17, 38, 22], + [2, 8, 37, 31], [40, 42, 47, 45], + [41, 44, 46, 43]].p + def rot5 = [[2, 42, 34, 13], [4, 44, 36, 20], + [7, 47, 39, 28], [14, 16, 31, 29], + [15, 22, 30, 21]].p + def rot6 = [[23, 26, 29, 42], [24, 27, 30, 41], + [25, 28, 31, 40], [32, 34, 39, 37], + [33, 36, 38, 35]].p + + def RubikGroup = Group(rot1, rot2, rot3, rot4, rot5, rot6) + //order of Rubik group + println RubikGroup.order() + ​ + + > 43252003274489856000 + ​ + Get base of group: + + //get base of group + def base = RubikGroup.base + println base + ​ + + > [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4,​ + 30,17,3,1] + ​ + Let's print order of each stabilizer in stabilizers chain: + + //print stabilizers chain + for (int i = 0; i < base.length;​ ++i) { + //partial base + def pBase = base[0..i] as int[] + print('​stab of ' + pBase + ' -> ') + print(RubikGroup.pointwiseStabilizer(pBase).order()) + println ''​ + } + ​ + + > stab of [0] -> 1802166803103744000 + > stab of [0,5] -> 85817466814464000 + > stab of [0,5,6] -> 3575727783936000 + > stab of [0,5,6,7] -> 198651543552000 + > stab of [0,​5,​6,​7,​10] -> 198651543552000 + > stab of [0,​5,​6,​7,​10,​11] -> 198651543552000 + > stab of [0,​5,​6,​7,​10,​11,​12] -> 198651543552000 + > stab of [0,​5,​6,​7,​10,​11,​12,​13] -> 198651543552000 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14] -> 198651543552000 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18] -> 9029615616000 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19] -> 9029615616000 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20] -> 451480780800 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21] -> 451480780800 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25] -> 30098718720 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26] -> 30098718720 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27] -> 1672151040 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28] -> 139345920 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29] -> 139345920 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32] -> 139345920 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33] ->  139345920 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34] -> 139345920 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2] -> 15482880 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23] -> 2580480 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22] -> 161280 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24] -> 11520 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4] -> 960 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4,​30] -> 96 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4,​30,​17] -> 12 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4,​30,​17,​3] -> 2 + > stab of [0,​5,​6,​7,​10,​11,​12,​13,​14,​18,​19,​20,​21,​25,​26,​27,​28,​29,​32,​33,​34,​2,​23,​22,​24,​4,​30,​17,​3,​1] -> 1 + ​ + + The algorithms used in Redberry are described in: + + * Derek F. Holt, Bettina Eick, Eamonn A. O'​Brien,​ //Handbook Of Computational Group Theory//, Chapman and Hall/CRC, 2005 + + The details on the internal implementation can be found in API. + + =====See also===== + * Related guides: [[documentation:​guide:​permutations_and_permutation_groups]] + * Related reference material: [[documentation:​ref:​permutation]] + * JavaDocs: + * Overview: [[http://​api.redberry.cc/​redberry/​1.1.9/​java-api/​cc/​redberry/​core/​groups/​permutations/​package-summary.html| Permutations package]] + * ''​PermutationGroup'':​ [[http://​api.redberry.cc/​redberry/​1.1.9/​java-api/​cc/​redberry/​core/​groups/​permutations/​PermutationGroup.html| PermutationGroup]] + * Schreier-Sims and related algorithms: [[http://​api.redberry.cc/​redberry/​1.1.9/​java-api/​cc/​redberry/​core/​groups/​permutations/​AlgorithmsBase.html| AlgorithmsBase]] + * Backtracking algorithms: [[http://​api.redberry.cc/​redberry/​1.1.9/​java-api/​cc/​redberry/​core/​groups/​permutations/​AlgorithmsBacktrack.html| AlgorithmsBacktrack]] + + * Source code: + * ''​PermutationGroup'':​ [[https://​bitbucket.org/​redberry/​redberry/​src/​tip/​core/​src/​main/​java/​cc/​redberry/​core/​groups/​permutations/​PermutationGroup.java| PermutationGroup.java]] + * Schreier-Sims and related algorithms: [[https://​bitbucket.org/​redberry/​redberry/​src/​tip/​core/​src/​main/​java/​cc/​redberry/​core/​groups/​permutations/​AlgorithmsBase.java| AlgorithmsBase.java]] + * Backtracking algorithms: [[https://​bitbucket.org/​redberry/​redberry/​src/​tip/​core/​src/​main/​java/​cc/​redberry/​core/​groups/​permutations/​AlgorithmsBacktrack.java| AlgorithmsBacktrack.java]]