Package 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:

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

      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 Details

    • 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

    • toString

      public String toString()
      Overrides:
      toString in class Object