Package org.openscience.cdk.group

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