org.openscience.cdk.group

Class PermutationGroup

java.lang.Object

org.openscience.cdk.group.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:

G₀ = {g ∈ G : g(0) = 0}
G₁ = {g ∈ G₀ : g(1) = 1}
G₂ = {g ∈ G₁ : g(2) = 2}
...
G_n-1 = {g in G_n-2 : g(n - 1) = n - 1} = {I}

and G₀, G₁, G₂, ..., G_n-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 n₀ for some integer 0 < n₀ ≤ n and write orb(0) = {x_0,1, x_0,2, ..., x_0,n₀} and for each i, 1 ≤ i ≤ n₀ choose some h_0,1 in G such that h_0,i(0) = x_0,1. Set U₀ = {h_0,1, ..., h_0,n₀}.

Given the above, the list of permutation sets in this class is [U₀,..,U_n]. Also, for all i = 1, ..., n-1 the set U_i is a left transversal of G_i in G_i-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 Classes

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 Summary

Constructors

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.

Method Summary

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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

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 U_i 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

toString

public String toString()

Overrides:

toString in class Object