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 © 2021. All rights reserved.