Package cc.redberry.core.groups.permutations

This package provides implementation of permutations and permutation groups.

See: Description

Interface Summary

Interface	Description
BacktrackSearchTestFunction	Test function which can be applied at each level of search tree; if it is not applicable at some level then it must return true.
Permutation	Interface describing a single permutation.

Class Summary

Class	Description
AlgorithmsBacktrack	Algorithms which uses backtrack search in permutation groups including searching for subgroups, setwise stabilizers, coset representatives, intersections of subgroups, centralizers etc.
AlgorithmsBase	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.
AlgorithmsBase.StripContainer	The result of AlgorithmsBase.strip(java.util.List, Permutation)
BacktrackSearch	An iterator (organized as output port OutputPort) over group elements, that scans group in increasing order permutations according to the ordering induced by a base (in increasing order of base images).
BacktrackSearchPayload
BSGSCandidateElement	A mutable version of BSGSElement.
BSGSElement	This class holds i-th base point (βi), generators of G(i) = Gβ1β2...βi-1 - stabilizer of all base points from 0-th to (i-1)-th as described in Sec.
InducedOrdering	An ordering of points Ω(n) induced by a base B: if bi, bj ∈ B then bi < bj if and only if i < j, and b < a for any b ∈ B and a ∉ B .
InducedOrderingOfPermutations	An ordering of permutations induced by an ordering on Ω(n) (see InducedOrdering).
PermutationGroup	Implementation of permutation group; this class provides a number of methods for work wih permutation groups, including membership testing, coset enumeration, searching for centralizers, stabilizers, etc (for details see method summary).
PermutationOneLineByte	The implementation of Permutation based on the one-line notation.
PermutationOneLineInt	The implementation of Permutation based on the one-line notation.
PermutationOneLineShort	The implementation of Permutation based on the one-line notation.
Permutations	Static methods to operate with permutations.
RandomPermutation	Algorithms for generating uniform distributed random elements of permutation group.

Exception Summary

Exception	Description
InconsistentGeneratorsException

Package cc.redberry.core.groups.permutations Description

This package provides implementation of permutations and permutation groups.

Permutations

The interface Permutation describes a wide functionality of a single permutation; it has several implementations (PermutationOneLineByte, PermutationOneLineInt etc.) and in order to create permutation in the appropriate implementation (from the stand point of memory consumption) one should use static methods createPermutation(...) in Permutations class.

Symmetries and antisymmetries In many physical applications, permutations arise as symmetries of some mathematical structures. For example, consider a function of 3 variables with the following property: f(x,y,z) == f(z,x,y). This symmetry can be put in one-to-one correspondence with a permutation [2,0,1] acting on a set [x,y,z]. Generally, it is accepted to consider a more general properties --- antisymmetries, which can additionally change the sigh of the function from the above example, e.g. f(x,y,z) == -f(z,y,x). In order to take into account antisymmetries, each Permutation may have additional property --- antisymmetry, which can have two values: +1 or -1. According to the sense of antisymmetry, this property simply multiplies under the composition of permutations.

Permutation groups

Permutation groups are described in the PermutationGroup class. This class provides a wide range of standard methods including membership testing, coset enumeration, searching for centralizers, stabilizers, etc. The implementation is based on a base and strong generating set (BSGS) (see [Holt05]). The description of BSGS data structure as well as algorithms for constructing, modifying and manipulating with BSGS are placed in AlgorithmsBase class. Algorithms for searching subgroups in permutation groups using backtracking are placed in AlgorithmsBacktrack class.

Literature:


[Holt05] Derek F. Holt, Bettina Eick, Eamonn A. O'Brien, Handbook Of Computational Group Theory, Chapman and Hall/CRC, 2005

See Also:

Permutation, PermutationOneLineInt, PermutationGroup, AlgorithmsBase, AlgorithmsBacktrack