cc.redberry.core.groups.permutations

Class AlgorithmsBacktrack

java.lang.Object

cc.redberry.core.groups.permutations.AlgorithmsBacktrack

public final class AlgorithmsBacktrack
extends java.lang.Object

Algorithms which uses backtrack search in permutation groups including searching for subgroups, setwise stabilizers, coset representatives, intersections of subgroups, centralizers etc.

Since:

1.1.6

See Also:

AlgorithmsBase

Method Summary

Modifier and Type	Method and Description
static void	intersection(java.util.List<? extends BSGSElement> group1, java.util.List<? extends BSGSElement> group2, java.util.ArrayList<BSGSCandidateElement> intersection) Calculates intersection of given subgroups using subgroupSearch(java.util.List, java.util.ArrayList, BacktrackSearchTestFunction, cc.redberry.core.utils.Indicator).
static Permutation[]	leftCosetRepresentatives(java.util.List<? extends BSGSElement> group, java.util.List<? extends BSGSElement> subgroup) Calculates left coset (gK) representatives of specified subgroup in specified group; each transversal is <-least in its coset.
static Permutation[]	leftCosetRepresentatives(java.util.List<? extends BSGSElement> group, java.util.List<? extends BSGSElement> subgroup, int[] base, InducedOrdering ordering) Calculates left coset (gK) representatives of specified subgroup in specified group; each returned transversal is <-least in its coset.
static Permutation	leftTransversalOf(Permutation element, java.util.List<? extends BSGSElement> group, java.util.List<? extends BSGSElement> subgroup) Returns coset representative of specified element; the returned representative will be minimal in its coset.
static Permutation	leftTransversalOf(Permutation element, java.util.List<? extends BSGSElement> group, java.util.List<? extends BSGSElement> subgroup, int[] base, InducedOrdering ordering) Returns coset representative of specified element; the returned representative will be minimal in its coset.
static void	subgroupSearch(java.util.List<? extends BSGSElement> group, java.util.ArrayList<BSGSCandidateElement> subgroup, BacktrackSearchTestFunction testFunction, Indicator<Permutation> property) The algorithm performs subgroup search in specified group.
static void	subgroupSearch(java.util.List<? extends BSGSElement> group, java.util.ArrayList<BSGSCandidateElement> subgroup, BacktrackSearchTestFunction testFunction, Indicator<Permutation> property, int[] base, InducedOrdering ordering) The algorithm performs subgroup search in specified group.
static void	subgroupSearchWithPayload(java.util.List<? extends BSGSElement> group, java.util.ArrayList<BSGSCandidateElement> subgroup, BacktrackSearchPayload payload, Indicator<Permutation> property) The algorithm performs subgroup search in specified group.
static void	subgroupSearchWithPayload(java.util.List<? extends BSGSElement> group, java.util.ArrayList<BSGSCandidateElement> subgroup, BacktrackSearchPayload payload, Indicator<Permutation> property, int[] base, InducedOrdering ordering) The algorithm performs subgroup search in specified group.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

subgroupSearch

public static void subgroupSearch(java.util.List<? extends BSGSElement> group,
                                  java.util.ArrayList<BSGSCandidateElement> subgroup,
                                  BacktrackSearchTestFunction testFunction,
                                  Indicator<Permutation> property)

The algorithm performs subgroup search in specified group. If a nonempty initial subgroup was provided, then it will be extended to the subgroup which we search for. Implementation issues can be found in Sec. 4.6.3 in [Holt05].

Parameters:

group - base and strong generating set of group

subgroup - initial base and strong generating set of subgroup for which we perform search

testFunction - test function that applies at each level of search tree

property - property of subgroup elements

See Also:

BacktrackSearch

subgroupSearchWithPayload

public static void subgroupSearchWithPayload(java.util.List<? extends BSGSElement> group,
                                             java.util.ArrayList<BSGSCandidateElement> subgroup,
                                             BacktrackSearchPayload payload,
                                             Indicator<Permutation> property)

The algorithm performs subgroup search in specified group. If a nonempty initial subgroup was provided, then it will be extended to the subgroup which we search for. Implementation issues can be found in Sec. 4.6.3 in [Holt05].

Parameters:

group - base and strong generating set of group

subgroup - initial base and strong generating set of subgroup for which we perform search

payload - payload test function that applies at each level of search tree and listen events on entering and leaving each tree level

property - property of subgroup elements

See Also:

BacktrackSearch

subgroupSearch

public static void subgroupSearch(java.util.List<? extends BSGSElement> group,
                                  java.util.ArrayList<BSGSCandidateElement> subgroup,
                                  BacktrackSearchTestFunction testFunction,
                                  Indicator<Permutation> property,
                                  int[] base,
                                  InducedOrdering ordering)

The algorithm performs subgroup search in specified group. If a nonempty initial subgroup was provided, then it will be extended to the subgroup which we search for. Implementation issues can be found in Sec. 4.6.3 in [Holt05].

Parameters:

group - base and strong generating set of group

subgroup - initial base and strong generating set of subgroup for which we perform search

testFunction - test function that applies at each level of search tree

property - property of subgroup elements

base - precomputed base

ordering - precomputed induced ordering

See Also:

BacktrackSearch

subgroupSearchWithPayload

public static void subgroupSearchWithPayload(java.util.List<? extends BSGSElement> group,
                                             java.util.ArrayList<BSGSCandidateElement> subgroup,
                                             BacktrackSearchPayload payload,
                                             Indicator<Permutation> property,
                                             int[] base,
                                             InducedOrdering ordering)

The algorithm performs subgroup search in specified group. If a nonempty initial subgroup was provided, then it will be extended to the subgroup which we search for. Implementation issues can be found in Sec. 4.6.3 in [Holt05].

Parameters:

group - base and strong generating set of group

subgroup - initial base and strong generating set of subgroup for which we perform search

payload - test function that applies at each level of search tree

property - property of subgroup elements

base - precomputed base

ordering - precomputed induced ordering

leftCosetRepresentatives

public static Permutation[] leftCosetRepresentatives(java.util.List<? extends BSGSElement> group,
                                                     java.util.List<? extends BSGSElement> subgroup)

Calculates left coset (gK) representatives of specified subgroup in specified group; each transversal is <-least in its coset. The implementation is based on a general backtrack search and prunes tree using minimality test. For details see the first method described in 4.6.7 in [Holt05].

Parameters:

group - group

subgroup - subgroup of specified group

Returns:

left coset representatives

leftCosetRepresentatives

public static Permutation[] leftCosetRepresentatives(java.util.List<? extends BSGSElement> group,
                                                     java.util.List<? extends BSGSElement> subgroup,
                                                     int[] base,
                                                     InducedOrdering ordering)

Calculates left coset (gK) representatives of specified subgroup in specified group; each returned transversal is <-least in its coset. The implementation is based on a general backtrack search and prunes tree using minimality test. For details see the first method described in 4.6.7 in [Holt05].

Parameters:

group - group

subgroup - subgroup of specified group

base - precomputed base

ordering - precomputed ordering

Returns:

left coset representatives

leftTransversalOf

public static Permutation leftTransversalOf(Permutation element,
                                            java.util.List<? extends BSGSElement> group,
                                            java.util.List<? extends BSGSElement> subgroup)

Returns coset representative of specified element; the returned representative will be minimal in its coset.

Parameters:

element - group element

group - group

subgroup - subgroup

Returns:

coset representative of specified group element

leftTransversalOf

public static Permutation leftTransversalOf(Permutation element,
                                            java.util.List<? extends BSGSElement> group,
                                            java.util.List<? extends BSGSElement> subgroup,
                                            int[] base,
                                            InducedOrdering ordering)

Returns coset representative of specified element; the returned representative will be minimal in its coset.

Parameters:

element - group element

group - group

subgroup - subgroup

base - precomputed base

ordering - precomputed ordering

Returns:

coset representative of specified group element

intersection

public static void intersection(java.util.List<? extends BSGSElement> group1,
                                java.util.List<? extends BSGSElement> group2,
                                java.util.ArrayList<BSGSCandidateElement> intersection)

Calculates intersection of given subgroups using subgroupSearch(java.util.List, java.util.ArrayList, BacktrackSearchTestFunction, cc.redberry.core.utils.Indicator).

Parameters:

group1 - permutation group

group2 - permutation group

intersection - initial intersection of given groups