Class PermutationGroup
A permutation group with a Schreier-Sims representation. For a number n, a list of permutation sets is stored (U0,...,Un-1). All n! permutations of [0...n-1] can be reconstructed from this list by backtracking - see, for example, the generateAll method.
So if G is a group on X = {0, 1, 2, 3, ..., n-1}, then:
G0 = {g ∈ G : g(0) = 0}and G0, G1, G2, ..., Gn-1 are subgroups of G.
G1 = {g ∈ G0 : g(1) = 1}
G2 = {g ∈ G1 : g(2) = 2}
...
Gn-1 = {g in Gn-2 : g(n - 1) = n - 1} = {I}
Now let orb(0) = {g(0) : g ∈ G} be the orbit of 0 under G. Then |orb(0)| (the size of the orbit) is n0 for some integer 0 < n0 ≤ n and write orb(0) = {x0,1, x0,2, ..., x0,n₀} and for each i, 1 ≤ i ≤ n0 choose some h0,1 in G such that h0,i(0) = x0,1. Set U0 = {h0,1, ..., h0,n₀}.
Given the above, the list of permutation sets in this class is [U0,..,Un]. Also, for all i = 1, ..., n-1 the set Ui is a left transversal of Gi in Gi-1.
This is port of the code from the C.A.G.E.S. book [Kreher, Donald and Stinson, Douglas, Combinatorial Algorithms Generation Enumeration and Search, 1998, CRC Press]. The mathematics in the description above is also from that book (pp. 203).
- Author:
- maclean
- Belongs to CDK module:
- group
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic interface
An interface for use with the apply method, which runs through all the permutations in this group. -
Constructor Summary
ConstructorsConstructorDescriptionPermutationGroup
(int size) Make a group with just a single identity permutation of size n.PermutationGroup
(int size, List<Permutation> generators) Creates a group from a set of generators.PermutationGroup
(Permutation base) Creates the initial group, with the basebase
. -
Method Summary
Modifier and TypeMethodDescriptionall()
Generate the whole group from the compact list of permutations.void
apply
(PermutationGroup.Backtracker backtracker) Apply the backtracker to all permutations in the larger group.void
changeBase
(Permutation newBase) Change the base of the group to the new basenewBase
.void
enter
(Permutation g) Enter the permutation g into this group.get
(int uIndex, int uSubIndex) Get one of the permutations that make up the compact representation.getLeftTransversal
(int index) Get the traversal Ui from the list of transversals.int
getSize()
Get the number of elements in each permutation in the group.static PermutationGroup
makeSymN
(int size) Make the symmetric group Sym(N) for N.long
order()
Calculates the size of the group.int
test
(Permutation permutation) Test a permutation to see if it is in the group.toString()
transversal
(PermutationGroup subgroup) Generate a transversal of a subgroup in this group.
-
Constructor Details
-
PermutationGroup
public PermutationGroup(int size) Make a group with just a single identity permutation of size n.- Parameters:
size
- the number of elements in the base permutation
-
PermutationGroup
Creates the initial group, with the basebase
.- Parameters:
base
- the permutation that the group is based on
-
PermutationGroup
Creates a group from a set of generators. See the makeSymN method for where this is used to make the symmetric group on N using the two generators (0, 1) and (1, 2, ..., n - 1, 0)- Parameters:
size
- the size of the groupgenerators
- the generators to use to make the group
-
-
Method Details
-
makeSymN
Make the symmetric group Sym(N) for N. That is, a group of permutations that represents _all_ permutations of size N.- Parameters:
size
- the size of the permutation- Returns:
- a group for all permutations of N
-
getSize
public int getSize()Get the number of elements in each permutation in the group.- Returns:
- the size of the permutations
-
order
public long order()Calculates the size of the group.- Returns:
- the (total) number of permutations in the group
-
get
Get one of the permutations that make up the compact representation.- Parameters:
uIndex
- the index of the set U.uSubIndex
- the index of the permutation within Ui.- Returns:
- a permutation
-
getLeftTransversal
Get the traversal Ui from the list of transversals.- Parameters:
index
- the index of the transversal- Returns:
- a list of permutations
-
transversal
Generate a transversal of a subgroup in this group.- Parameters:
subgroup
- the subgroup to use for the transversal- Returns:
- a list of permutations
-
apply
Apply the backtracker to all permutations in the larger group.- Parameters:
backtracker
- a hook for acting on the permutations
-
all
Generate the whole group from the compact list of permutations.- Returns:
- a list of permutations
-
changeBase
Change the base of the group to the new basenewBase
.- Parameters:
newBase
- the new base for the group
-
enter
Enter the permutation g into this group.- Parameters:
g
- a permutation to add to the group
-
test
Test a permutation to see if it is in the group. Note that this also alters the permutation passed in.- Parameters:
permutation
- the one to test- Returns:
- the position it should be in the group, if any
-
toString
-