PermutationGroup represents a group of permutations. 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]]
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.
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)
println group.order()
> 28810681675776000
println group.orbit(20)
> [9, 16, 22, 30, 18, 15, 20, 19, 14]
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
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
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
def dSubgroup = group.derivedSubgroup() println dSubgroup.order()
> 3201186852864000
def oth = Group([[1, 17, 12, 19], [23, 25]].p, [[4, 14, 26]].p) println group.containsSubgroup(oth)
> false
def union = group.union(oth) assert union.containsSubgroup(group) assert union.containsSubgroup(oth) println union.order()
> 4420880996869850977271808000000
def intersection = union.intersection(group) assert intersection == group
println sStabilizer.leftCosetRepresentatives(pStabilizer)
> [+[],
+[[1, 4], [25, 27]],
+[[1, 4], [3, 25]],
+[[3, 25, 27]],
+[[3, 27, 25]],
+[[1, 4], [3, 27]]]
println group.centralizerOf(sStabilizer)
> Group( +[[9, 14, 19, 20, 15, 18, 30, 22, 16]] )
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 |
. 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. |
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]]
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()
> 43252003274489856000Get 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:
The details on the internal implementation can be found in API.
PermutationGroup: PermutationGroupPermutationGroup: PermutationGroup.java