Class PermutationGroup

• 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}
G1 = {g ∈ G0 : g(1) = 1}
G2 = {g ∈ G1 : g(2) = 2}
...
Gn-1 = {g in Gn-2 : g(n - 1) = n - 1} = {I}
and G0, G1, G2, ..., Gn-1 are subgroups of G.

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
• Constructor Detail

• 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

public PermutationGroup​(Permutation base)
Creates the initial group, with the base base.
Parameters:
base - the permutation that the group is based on
• PermutationGroup

public PermutationGroup​(int size,
List<Permutation> generators)
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 group
generators - the generators to use to make the group
• Method Detail

• makeSymN

public static PermutationGroup makeSymN​(int size)
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

public Permutation get​(int uIndex,
int uSubIndex)
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

public List<Permutation> getLeftTransversal​(int index)
Get the traversal Ui from the list of transversals.
Parameters:
index - the index of the transversal
Returns:
a list of permutations
• transversal

public List<Permutation> transversal​(PermutationGroup subgroup)
Generate a transversal of a subgroup in this group.
Parameters:
subgroup - the subgroup to use for the transversal
Returns:
a list of permutations
• apply

public void apply​(PermutationGroup.Backtracker backtracker)
Apply the backtracker to all permutations in the larger group.
Parameters:
backtracker - a hook for acting on the permutations
• all

public List<Permutation> all()
Generate the whole group from the compact list of permutations.
Returns:
a list of permutations
• changeBase

public void changeBase​(Permutation newBase)
Change the base of the group to the new base newBase.
Parameters:
newBase - the new base for the group
• enter

public void enter​(Permutation g)
Enter the permutation g into this group.
Parameters:
g - a permutation to add to the group
• test

public int test​(Permutation permutation)
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