public class PermutationGroup extends Object
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).
Modifier and Type | Class and Description |
---|---|
static interface |
PermutationGroup.Backtracker
An interface for use with the apply method, which runs through all the
permutations in this group.
|
Constructor and Description |
---|
PermutationGroup(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 base
base . |
Modifier and Type | Method and Description |
---|---|
List<Permutation> |
all()
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 base
newBase . |
void |
enter(Permutation g)
Enter the permutation g into this group.
|
Permutation |
get(int uIndex,
int uSubIndex)
Get one of the permutations that make up the compact representation.
|
List<Permutation> |
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.
|
String |
toString() |
List<Permutation> |
transversal(PermutationGroup subgroup)
Generate a transversal of a subgroup in this group.
|
public PermutationGroup(int size)
size
- the number of elements in the base permutationpublic PermutationGroup(Permutation base)
base
.base
- the permutation that the group is based onpublic PermutationGroup(int size, List<Permutation> generators)
size
- the size of the groupgenerators
- the generators to use to make the grouppublic static PermutationGroup makeSymN(int size)
size
- the size of the permutationpublic int getSize()
public long order()
public Permutation get(int uIndex, int uSubIndex)
uIndex
- the index of the set U.uSubIndex
- the index of the permutation within Ui.public List<Permutation> getLeftTransversal(int index)
index
- the index of the transversalpublic List<Permutation> transversal(PermutationGroup subgroup)
subgroup
- the subgroup to use for the transversalpublic void apply(PermutationGroup.Backtracker backtracker)
backtracker
- a hook for acting on the permutationspublic List<Permutation> all()
public void changeBase(Permutation newBase)
newBase
.newBase
- the new base for the grouppublic void enter(Permutation g)
g
- a permutation to add to the grouppublic int test(Permutation permutation)
permutation
- the one to testCopyright © 2017. All Rights Reserved.