Documentation of 'cc.redberry.core.groups.permutations.AlgorithmsBase' Java class
AlgorithmsBase
Skip navigation links
cc.redberry.core.groups.permutations

Class AlgorithmsBase


  • public final class AlgorithmsBase
extends java.lang.Object
    Algorithms for constructing, modifying and manipulating base and strong generating set (BSGS) of permutation group including Schreier-Sims algorithm and its randomized versions, algorithms for changing base of BSGS, algorithms for creating BSGS of symmetric and alternating groups and other utility methods.

    BSGS data structure The data structure used for representing BSGS is an array list of BSGS elements (see BSGSElement); i-th item in this list contains i-th base point and i-th basic stabilizer in stabilizers chain (pointwise stabilizer of all points before i-th point, exclusive), represented by its generators.

    The BSGS structure appears in two forms: mutable --- ArrayList<BSGSCandidateElement> (see BSGSCandidateElement) and immutable --- List<BSGSElement> (unmodifiable). The first form is used as a candidate BSGS of permutation group, while the second everywhere considered as a valid BSGS. For illustration, consider the following code: 

     1: Permutation perm1 = Permutations.createPermutation(1, 2, 3, 4, 0);
 2: Permutation perm2 = Permutations.createPermutation(1, 3, 0, 4, 2);
 3: //create a candidate BSGS
 4: ArrayList<BSGSCandidateElement> candidate = (ArrayList) AlgorithmsBase.createRawBSGSCandidate(perm1, perm2);
 5: //apply randomized Schreier-Sims algorithm to candidate BSGS (add missing base points and basic stabilizers)
 6: AlgorithmsBase.RandomSchreierSimsAlgorithm(candidate, 0.9999,  new Well1024a());
 7: //if our random Schreier-Sims was not enough
 8: if (!AlgorithmsBase.isBSGS(candidate))
 9:     AlgorithmsBase.SchreierSimsAlgorithm(candidate);
 10: List<BSGSElement> bsgs = AlgorithmsBase.asBSGSList(candidate);
    In this example we construct a very raw candidate BSGS in the line 4 and then apply randomized Schreier-Sims algorithm which modifies it. Still after, there is a very small ~0.01% probability that this candidate is not a real BSGS; we check this in the line 8 and apply deterministic algorithm if necessary. After all, we can convert candidate BSGS to a list with immutable elements in line 10.

    Since:
    1.1.6
    See Also:
    AlgorithmsBacktrack

    • Field Detail

      • TRIVIAL_BSGS

        public static final java.util.List<BSGSElement> TRIVIAL_BSGS

      • SMALL_DEGREE_THRESHOLD

        public static final int SMALL_DEGREE_THRESHOLD
        This value is an upper bound of degrees, which we consider as "small".
        See Also:
        Constant Field Values

    • Method Detail

      • strip

        public static AlgorithmsBase.StripContainer strip(java.util.List<? extends BSGSElement> BSGS,
                                                  Permutation permutation)
        Calculates representation of specified permutation in terms of specified BSGS. If specified permutation can be represented in terms of specified BSGS, then the produced remainder will be identity and terminationLevel equals to BSGS size. If produced remainder is not identity then it fixes all base points in specified BSGS (hence permutation does not belong to group). If terminationLevel is less then BSGS size, then specified permutation does not belong to group and produced remainder is a unique generator that should be placed at terminationLevel in specified BSGS in order to extend group such that it will contain specified permutation.

        The algorithm is a straightforward implementation of STRIP described in Sec. 4.4.1 of [Holt05].

        Parameters:
        BSGS -
        permutation -
        Returns:
        terminationLevel and remainder

      • membershipTest

        public static boolean membershipTest(java.util.List<? extends BSGSElement> BSGS,
                                     Permutation permutation)
        Returns whether specified permutation belongs to permutation group defined by specified base and strong generating set.
        Parameters:
        BSGS - base and strong generating set
        permutation - permutation
        Returns:
        true if specified permutation belongs to permutation group defined by specified base and strong generating set and false otherwise

      • createRawBSGSCandidate

        public static java.util.List<BSGSCandidateElement> createRawBSGSCandidate(Permutation... generators)
        Creates a raw BSGS candidate represented as list. This method simply takes all distinct points that can be mapped onto another points under any of generators and adjoins these points to a base. If generating set is empty or it fixes all points, then this method returns Collections.EMPTY_LIST, otherwise it returns an ArrayList which can be further used in Schreier-Sims algorithm.
        Parameters:
        generators - group generators
        Returns:
        raw BSGS candidate

      • createRawBSGSCandidate

        public static java.util.List<BSGSCandidateElement> createRawBSGSCandidate(java.util.List<Permutation> generators)
        Creates a raw BSGS candidate represented as list. This method simply takes all distinct points that can be mapped onto another points under any of generators and adjoins these points to a base. If generating set is empty or it fixes all points, then this method returns Collections.EMPTY_LIST, otherwise it returns an ArrayList which can be further used in Schreier-Sims algorithm.
        Parameters:
        generators - group generators
        Returns:
        raw BSGS candidate

      • createRawBSGSCandidate

        public static java.util.List<BSGSCandidateElement> createRawBSGSCandidate(java.util.List<Permutation> generators,
                                                                          int degree)
        Creates a raw BSGS candidate represented as list. This method simply takes all distinct points that can be mapped onto another points under any of generators and adjoins these points to a base. If generating set is empty or it fixes all points, then this method returns Collections.EMPTY_LIST, otherwise it returns an ArrayList which can be further used in Schreier-Sims algorithm.
        Parameters:
        generators - group generators
        degree - degree of group used to create Schreier vectors of proper length (see Permutations.internalDegree(java.util.List))
        Returns:
        raw BSGS candidate

      • createRawBSGSCandidate

        public static java.util.List<BSGSCandidateElement> createRawBSGSCandidate(int[] knownBase,
                                                                          java.util.List<Permutation> generators)
        Creates a raw BSGS candidate represented as list. This method simply adds to knownBase all distinct points that can be mapped onto another points under any of generators. Those points in knownBase that are fixed by all generators will not be taken into account. If generating set is empty, or it fixes all points, then this method returns Collections.EMPTY_LIST, otherwise it returns an ArrayList which can be further used in Schreier-Sims algorithm.
        Parameters:
        knownBase - some proposed base points
        generators - group generators
        Returns:
        raw BSGS candidate

      • createRawBSGSCandidate

        public static java.util.List<BSGSCandidateElement> createRawBSGSCandidate(int[] knownBase,
                                                                          java.util.List<Permutation> generators,
                                                                          int degree)
        Creates a raw BSGS candidate represented as list. This method simply adds to knownBase all distinct points that can be mapped onto another points under any of generators. Those points in knownBase that are fixed by all generators will not be taken into account. If generating set is empty, or it fixes all points, then this method returns Collections.EMPTY_LIST, otherwise it returns an ArrayList which can be further used in Schreier-Sims algorithm.
        Parameters:
        knownBase - some proposed base points
        generators - group generators
        degree - degree of group used to create Schreier vectors of proper length (see Permutations.internalDegree(java.util.List))
        Returns:
        raw BSGS candidate

      • createBSGSList

        public static java.util.List<BSGSElement> createBSGSList(java.util.List<Permutation> generators)
        Creates BSGS using Schreier-Sims algorithm.

        The underlying code schematically organized as follows: 

        
 List<BSGSCandidateElement> BSGSCandidate = createRawBSGSCandidate(generators);
 if (BSGSCandidate.isEmpty())
    return TRIVIAL_BSGS;
 SchreierSimsAlgorithm((ArrayList) BSGSCandidate);
 return asBSGSList(BSGSCandidate);

        Parameters:
        generators - a set of group generators
        Returns:
        BSGS represented as array of its element
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)
        See Also:
        createRawBSGSCandidate(java.util.List), SchreierSimsAlgorithm(java.util.ArrayList)

      • createBSGSList

        public static java.util.List<BSGSElement> createBSGSList(java.util.List<Permutation> generators,
                                                         int degree)
        Creates BSGS using Schreier-Sims algorithm.

        The underlying code schematically organized as follows: 

        
 List<BSGSCandidateElement> BSGSCandidate = createRawBSGSCandidate(generators, degree);
 if (BSGSCandidate.isEmpty())
    return TRIVIAL_BSGS;
 SchreierSimsAlgorithm((ArrayList) BSGSCandidate);
 return asBSGSList(BSGSCandidate);

        Parameters:
        generators - a set of group generators
        degree - degree of group used to create Schreier vectors of proper length (see Permutations.internalDegree(java.util.List))
        Returns:
        BSGS represented as array of its element
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)
        See Also:
        createRawBSGSCandidate(java.util.List), SchreierSimsAlgorithm(java.util.ArrayList)

      • createBSGSList

        public static java.util.List<BSGSElement> createBSGSList(int[] knownBase,
                                                         java.util.List<Permutation> generators)
        Creates BSGS using Schreier-Sims algorithm. Specified base will be extended if necessary.

        The underlying code schematically organized as follows: 

        
 List<BSGSCandidateElement> BSGSCandidate = createRawBSGSCandidate(knownBase, generators);
 if (BSGSCandidate.isEmpty())
    return Collections.EMPTY_LIST;
 SchreierSimsAlgorithm((ArrayList) BSGSCandidate);
 return asBSGSList(BSGSCandidate);

        Parameters:
        generators - a set of group generators
        knownBase - proposed base points
        Returns:
        BSGS represented as array of its element
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)
        See Also:
        createRawBSGSCandidate(int[], java.util.List), SchreierSimsAlgorithm(java.util.ArrayList)

      • createBSGSList

        public static java.util.List<BSGSElement> createBSGSList(int[] knownBase,
                                                         java.util.List<Permutation> generators,
                                                         int degree)
        Creates BSGS using Schreier-Sims algorithm. Specified base will be extended if necessary.

        The underlying code organized as follows: 

        
 List<BSGSCandidateElement> BSGSCandidate = createRawBSGSCandidate(knownBase, generators, degree);
 if (BSGSCandidate.isEmpty())
    return TRIVIAL_BSGS;
 SchreierSimsAlgorithm((ArrayList) BSGSCandidate);
 return asBSGSList(BSGSCandidate);

        Parameters:
        knownBase - proposed base points
        generators - a set of group generators
        degree - degree of group used to create Schreier vectors of proper length (see Permutations.internalDegree(java.util.List))
        Returns:
        BSGS represented as array of its element
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)
        See Also:
        createRawBSGSCandidate(int[], java.util.List), SchreierSimsAlgorithm(java.util.ArrayList)

      • makeUseOfAllGenerators

        public static void makeUseOfAllGenerators(java.util.List<BSGSCandidateElement> BSGSCandidate)
        If some of generators fixes all base points, then, this method will find a new point that is not fixed by this generator and add this point to specified BSGS candidate.
        Parameters:
        BSGSCandidate - BSGS candidate

      • SchreierSimsAlgorithm

        public static void SchreierSimsAlgorithm(java.util.ArrayList<BSGSCandidateElement> BSGSCandidate)
        Applies Schreier-Sims algorithm to specified BSGS candidate and complete it if necessary; as result, specified BSGS candidate will be guaranteed BSGS. The algorithm described as SCHREIERSIMS in Sec. 4.4.1 of [Holt05].
        Parameters:
        BSGSCandidate - BSGS candidate
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)

      • RandomSchreierSimsAlgorithm

        public static void RandomSchreierSimsAlgorithm(java.util.ArrayList<BSGSCandidateElement> BSGSCandidate,
                                               double confidenceLevel,
                                               org.apache.commons.math3.random.RandomGenerator randomGenerator)
        Applies randomized version of Schreier-Sims algorithm to specified BSGS candidate and complete it if necessary. The probability that after applying this algorithm the BSGS candidate will be guaranteed BSGS is equal to specified confidence level. The algorithm described as RANDOMSCHREIER in Sec. 4.4.5 of [Holt05].
        Parameters:
        BSGSCandidate - BSGS candidate
        confidenceLevel - confidence level (0 < confidence level < 1)
        randomGenerator - random generator
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)

      • RandomSchreierSimsAlgorithmForKnownOrder

        public static void RandomSchreierSimsAlgorithmForKnownOrder(java.util.ArrayList<BSGSCandidateElement> BSGSCandidate,
                                                            java.math.BigInteger groupOrder,
                                                            org.apache.commons.math3.random.RandomGenerator randomGenerator)
        Applies randomized version of Schreier-Sims algorithm to specified BSGS until the group order calculated using this candidate is not equals to order specified; as result, specified BSGS candidate will be guarantied BSGS. If specified order greater then the order of permutation group generated by specified BSGS candidate, then the algorithm will fall in infinite loop.
        Parameters:
        BSGSCandidate - BSGS candidate
        groupOrder - order of a group
        randomGenerator - random generator
        Throws:
        InconsistentGeneratorsException - if algorithm detects that specified generators are inconsistent (due to antisymmetries)
        See Also:
        RandomSchreierSimsAlgorithm(java.util.ArrayList, double, org.apache.commons.math3.random.RandomGenerator)

      • calculateOrder

        public static final java.math.BigInteger calculateOrder(java.util.List<? extends BSGSElement> BSGSList)
        Calculates order of permutation group represented by specified BSGS.
        Parameters:
        BSGSList - BSGS
        Returns:
        order of permutation group represented by specified BSGS

      • removeRedundantGenerators

        public static void removeRedundantGenerators(java.util.ArrayList<BSGSCandidateElement> BSGSCandidate)
        Removes redundant elements from BSGS candidate. The algorithm have O(degree^5) complexity in the worst case.
        Parameters:
        BSGSCandidate - BSGS candidate

      • removeRedundantBaseRemnant

        public static void removeRedundantBaseRemnant(java.util.ArrayList<BSGSCandidateElement> BSGS)
        Removes redundant base points from the ending of specified BSGS.
        Parameters:
        BSGS - BSGS

      • isBSGS

        public static boolean isBSGS(java.util.List<? extends BSGSElement> BSGSCandidate)
        Returns true if specified BSGS candidate is a real BSGS. Method uses a restricted version of Schreier-Sims algorithm.
        Parameters:
        BSGSCandidate - BSGS candidate
        Returns:
        true if specified BSGS candidate is a real BSGS and false otherwise

      • isBSGS

        public static boolean isBSGS(java.util.List<? extends BSGSElement> BSGSCandidate,
                             double confidenceLevel,
                             org.apache.commons.math3.random.RandomGenerator randomGenerator)
        Returns true if specified BSGS candidate is a real BSGS with specified confidence level. Method uses a restricted version of randomized Schreier-Sims algorithm.
        Parameters:
        BSGSCandidate - BSGS candidate
        confidenceLevel - confidence level (0 < confidence level < 1)
        randomGenerator - random generator
        Returns:
        true if specified BSGS candidate is a real BSGS and false otherwise

      • numberOfStrongGenerators

        public static long numberOfStrongGenerators(java.util.List<? extends BSGSElement> BSGS)
        Returns the number of elements in specified strong generating set.
        Parameters:
        BSGS - strong generating set
        Returns:
        number of elements in specified strong generating set

      • swapAdjacentBasePoints

        public static void swapAdjacentBasePoints(java.util.ArrayList<BSGSCandidateElement> BSGS,
                                          int i)
        Swaps i-th and (i+1)-th points of specified BSGS. The details of the implementation can be found in Sec. 4.4.7 of [Holt05] (see BASESWAP algorithm).
        Parameters:
        BSGS - BSGS
        i - position of base point to swap with next point

      • rebaseWithTranspositions

        public static void rebaseWithTranspositions(java.util.ArrayList<BSGSCandidateElement> BSGS,
                                            int[] newBase)
        Changes the base of specified BSGS to specified new base using an algorithm with transpositions. The algorithm guaranties that if initial base is [b1, b2, b3, ..., bk] and specified base is [a1, a2, a3, ..., al], then the resulting base will look like [a1, a2, a3, ...., al, b4, b7, ..., b19] with no any redundant base points at the end (redundant point is point which corresponding stabilizer generators are empty) - this achieves by invocation of removeRedundantBaseRemnant(java.util.ArrayList) at the end of procedure.
        Parameters:
        BSGS - BSGS
        newBase - new base

      • rebaseWithConjugationAndTranspositions

        public static void rebaseWithConjugationAndTranspositions(java.util.ArrayList<BSGSCandidateElement> BSGS,
                                                          int[] newBase)
        Changes base of specified BSGS to specified new base using an algorithm with conjugations and transpositions. The algorithm guaranties that if initial base is [b1, b2, b3, ..., bk] and specified base is [a1, a2, a3, ..., al], then the resulting base will look like [a1, a2, a3, ...., al, b4, b7, ..., b19] with no any redundant base points at the end (redundant point is point which corresponding stabilizer generators are empty) - this achieves by invocation of removeRedundantBaseRemnant(java.util.ArrayList) at the end of procedure.
        Parameters:
        BSGS - BSGS
        newBase - new base

      • rebaseFromScratch

        public static void rebaseFromScratch(java.util.ArrayList<BSGSCandidateElement> BSGS,
                                     int[] newBase)
        Changes base of specified BSGS to specified new base by construction of a new BSGS with known base using randomized Schreier-Sims algorithm RandomSchreierSimsAlgorithmForKnownOrder(java.util.ArrayList, java.math.BigInteger, org.apache.commons.math3.random.RandomGenerator). The algorithm guaranties that if initial base is [b1, b2, b3, ..., bk] and specified base is [a1, a2, a3, ..., al], then the resulting base will look like [a1, a2, a3, ...., al, x, y, ..., z] with no any redundant base points at the end (redundant point is point which corresponding stabilizer generators are empty) but with some additional points introduced if specified new base was not anought.
        Parameters:
        BSGS - BSGS
        newBase - new base

      • directProduct

        public static java.util.ArrayList<BSGSElement> directProduct(java.util.List<? extends BSGSElement> bsgs1,
                                                             java.util.List<? extends BSGSElement> bsgs2)
        Returns direct product of two groups given by their BSGS. This product is organized as follows: the initial segment of each permutation is equal to permutation taken from first group, while the rest is taken from the second.
        Parameters:
        bsgs1 - BSGS of first group
        bsgs2 - BSGS of second group
        Returns:
        direct product first group × second group

      • union

        public static java.util.ArrayList<? extends BSGSElement> union(java.util.ArrayList<? extends BSGSElement> bsgs1,
                                                               java.util.ArrayList<? extends BSGSElement> bsgs2)
        Calculates a union of specified groups.
        Parameters:
        bsgs1 - base and strong generating set of first group
        bsgs2 - base and strong generating set of second group
        Returns:
        base and strong generating set of the union

      • createAlternatingGroupBSGS

        public static java.util.List<BSGSElement> createAlternatingGroupBSGS(int degree)
        Creates base and strong generating set of alternating group of specified degree. Alternating group of degree smaller then SMALL_DEGREE_THRESHOLD will provide zero-time access to all transversals in each stabilizer; group with larger degree will provide log(size of orbit) access. Additionally, small degree group with fixed degree will be constructed once (at the first invocation of this method with specified degree) and then cached, so second invocation of this method with same degree will return same reference.
        Parameters:
        degree - group degree
        Returns:
        base and strong generating set of symmetric group

      • createSymmetricGroupBSGS

        public static java.util.ArrayList<BSGSElement> createSymmetricGroupBSGS(int degree)
        Creates base and strong generating set of symmetric group of specified degree. Symmetric group of degree smaller then SMALL_DEGREE_THRESHOLD will provide zero-time access to all transversals in each stabilizer; group with larger degree will provide log(size of orbit) access. Additionally, small degree group with fixed degree will be constructed once (at the first invocation of this method with specified degree) and then cached, so second invocation of this method with same degree will return same reference.
        Parameters:
        degree - group degree
        Returns:
        base and strong generating set of symmetric group

      • createAntisymmetricGroupBSGS

        public static java.util.List<BSGSElement> createAntisymmetricGroupBSGS(int degree)
        Creates base and strong generating set of symmetric group of specified degree, where all odd permutations are antisymmetries. Symmetric group of degree smaller then SMALL_DEGREE_THRESHOLD will provide zero-time access to all transversals in each stabilizer; group with larger degree will provide log(size of orbit) access. Additionally, small degree group with fixed degree will be constructed once (at the first invocation of this method with specified degree) and then cached, so second invocation of this method with same degree will return same reference.
        Parameters:
        degree - group degree
        Returns:
        base and strong generating set of symmetric group

      • asBSGSCandidatesList

        public static java.util.ArrayList<BSGSCandidateElement> asBSGSCandidatesList(java.util.List<? extends BSGSElement> BSGS)
        Makes a mutable copy of BSGS.
        Parameters:
        BSGS - BSGS
        Returns:
        mutable copy of BSGS

      • asBSGSList

        public static java.util.ArrayList<BSGSElement> asBSGSList(java.util.List<? extends BSGSElement> BSGSCandidate)
        Makes an immutable copy of BSGS.
        Parameters:
        BSGSCandidate - BSGS
        Returns:
        immutable copy of BSGS

      • getBaseAsArray

        public static int[] getBaseAsArray(java.util.List<? extends BSGSElement> BSGS)
        Returns base represented as array
        Parameters:
        BSGS - BSGS
        Returns:
        base represented as array

      • clone

        public static java.util.ArrayList<BSGSCandidateElement> clone(java.util.List<BSGSCandidateElement> BSGSCandidate)
        Returns a deep copy of specified list
        Parameters:
        BSGSCandidate - BSGS candidate
        Returns:
        deep copy of specified list
Skip navigation links

DataMelt 3.0 © DataMelt by jWork.ORG

Ads help maintain this website.