permlib
0.2.9
Library for permutation computations
|
BSGS construction with Random Schreier-Sims algorithm. More...
#include <random_schreier_sims_construction.h>
Public Member Functions | |
RandomSchreierSimsConstruction (unsigned int n, RandomGenerator< PERM > *rng, Integer knownOrder=0, unsigned int minimalConsecutiveSiftingElementCount=20, unsigned int maxIterationFactor=10000) | |
constructor More... | |
template<class ForwardIterator > | |
BSGS< PERM, TRANS > | construct (ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool &guaranteedBSGS) const |
constructs a probable BSGS for group given by generators with no base prescribed More... | |
template<class ForwardIterator , class InputIterator > | |
BSGS< PERM, TRANS > | construct (ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, bool &guaranteedBSGS) const |
constructs a probable BSGS for group given by generators respecting prescribed base elements More... | |
![]() | |
BaseConstruction (dom_int n) | |
constructor More... | |
Public Attributes | |
unsigned int | m_statRandomElementsConsidered |
number of Schreier generators examined during the last construct call | |
const unsigned int | m_minimalConsecutiveSiftingElementCount |
number of elements that have to sift through constructed BSGS consecutively that it is returned as a probable BSGS | |
const unsigned int | m_maxIterationFactor |
factor limiting the number of maximal iterations depeding on the initial base size | |
Additional Inherited Members | |
![]() | |
template<class ForwardIterator , class InputIterator > | |
void | setup (ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd, BSGS< PERM, TRANS > &bsgs, std::vector< std::list< typename PERM::ptr > > &S) const |
initializes BSGS object More... | |
void | mergeGenerators (std::vector< std::list< typename PERM::ptr > > &S, BSGS< PERM, TRANS > &ret) const |
merges all strong generators in S into a single strong generating set ret.S | |
![]() | |
dom_int | m_n |
cardinality of the set the group is acting on | |
![]() | |
static const unsigned long * | empty = static_cast<unsigned long*>(0) |
auxilliary element marking an empty iterator | |
BSGS construction with Random Schreier-Sims algorithm.
Randomized algorithm for BSGS construction. If order is known it is Las Vegas type, otherwise Monte Carlo (it may return an incomplete BSGS).
permlib::RandomSchreierSimsConstruction< PERM, TRANS, Integer >::RandomSchreierSimsConstruction | ( | unsigned int | n, |
RandomGenerator< PERM > * | rng, | ||
Integer | knownOrder = 0 , |
||
unsigned int | minimalConsecutiveSiftingElementCount = 20 , |
||
unsigned int | maxIterationFactor = 10000 |
||
) |
constructor
n | cardinality of the set the group is acting on |
rng | a RandomGenerator generating uniformly distributed random group elements of the group that the BSGS is constructed of |
knownOrder | order of the group that the BSGS is constructed of. If non-zero upgrades algorithm to Las Vegas type and the output is guaranteed to be a BSGS. |
minimalConsecutiveSiftingElementCount | number of elements that have to sift through constructed BSGS consecutively that it is returned as a probable BSGS |
maxIterationFactor | factor limiting the number of maximal iterations depeding on the initial base size |
|
inline |
constructs a probable BSGS for group given by generators with no base prescribed
BSGS< PERM, TRANS > permlib::RandomSchreierSimsConstruction< PERM, TRANS, Integer >::construct | ( | ForwardIterator | generatorsBegin, |
ForwardIterator | generatorsEnd, | ||
InputIterator | prescribedBaseBegin, | ||
InputIterator | prescribedBaseEnd, | ||
bool & | guaranteedBSGS | ||
) | const |
constructs a probable BSGS for group given by generators respecting prescribed base elements
runs (#{size of initial base} * maxIterationFactor) iterations or until constructed BSGS has knownOrder or #minimalConsecutiveSiftingElementCount sift through the constructed BSGS consecutively
generatorsBegin | begin iterator of group generators of type PERM |
generatorsEnd | end iterator of group generators of type PERM |
prescribedBaseBegin | begin iterator of prescribed base of type unsigned long |
prescribedBaseEnd | end iterator of prescribed base of type unsigned long |
guaranteedBSGS | iff true, return object is guaranteed to be a BSGS |