====== 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'':
.center() center of group.
.centralizerOf(perm) centralizer of permutation perm.
.centralizerOf(group). centralizer of subgroup group.
.commutator(oth) commutator with oth group.
.conjugate(perm) conjugation of group with specified permutation perm( i.e. $p^{-1} G p$, where $p$ is perm and $G$ is a group).
.containsSubgroup(oth) returns whether group contains subgroup oth.
.degree() natural degree of group, i.e. largest moved point plus one.
.derivedSubgroup() derived subgroup, i.e. commutator subgroup of group with itself.
. directProduct(oth) direct product of group 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 oth.
. equals(oth) returns whether group is equal to oth in mathematical sense.
.generators() a list of group generators.
. base base of group.
. getBSGS() low level representation of base and strong generating set.
. intersection(oth) intersection of group with oth.
. isAbelian() returns whether group is abelian.
. isAlternating() returns whether group is alternating.
. isRegular() returns whether group is regular (i.e. transitive and its order equals to degree).
. isSymmetric() returns whether group is symmetric.
. isTransitive() returns whether group is transitive.
. isTransitive(from, to) returns whether group acts transitively on the the range from (inclusive) to to (exclusive).
. isTrivial() returns whether group is trivial (contains only identity element).
. leftCosetRepresentatives(subgroup) array of left coset representatives of a subgroup.
. leftTransversalOf(subgroup, perm) a unique left coset representative of perm.
. mapping(from, to) iterator over permutations that maps from points on to.
. membershipTest(perm) returns whether perm belongs to group.
. normalClosureOf(subgroup) normal closure of specified subgroup.
. orbit(points) orbit of points.
.order() group order (i.e. number of all elements).
. pointwiseStabilizer(set) pointwise stabilizer of specified set of points.
. randomElement() uniformly distributed random element from group.
. rightCosetRepresentatives(subgroup) array of right coset representatives of a subgroup.
. setwiseStabilizer(set) pointwise stabilizer of specified set of points.
. 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 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]]