33#ifndef RANDOMSCHREIERSIMSCONSTRUCTION_H_
34#define RANDOMSCHREIERSIMSCONSTRUCTION_H_
36#include <permlib/construct/base_construction.h>
37#include <permlib/generator/random_generator.h>
38#include <permlib/bsgs.h>
40#include <boost/cstdint.hpp>
41#include <boost/foreach.hpp>
50template <
class PERM,
class TRANS,
typename Integer = boost::u
int64_t>
62 unsigned int minimalConsecutiveSiftingElementCount = 20,
unsigned int maxIterationFactor = 10000);
67 template <
class ForwardIterator>
81 template <
class ForwardIterator,
class InputIterator>
82 BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd,
bool& guaranteedBSGS)
const;
101template <
class PERM,
class TRANS,
typename Integer>
103 unsigned int minimalConsecutiveSiftingElementCount,
unsigned int maxIterationFactor)
104 :
BaseConstruction<PERM, TRANS>(n), m_statRandomElementsConsidered(0), m_minimalConsecutiveSiftingElementCount(minimalConsecutiveSiftingElementCount),
105 m_maxIterationFactor(maxIterationFactor), m_rng(rng), m_knownOrder(knownOrder)
108template <
class PERM,
class TRANS,
typename Integer>
109template <
class ForwardIterator>
114template <
class PERM,
class TRANS,
typename Integer>
115template <
class ForwardIterator,
class InputIterator>
117 ::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd,
bool& guaranteedBSGS)
const
119 const unsigned int &n = this->m_n;
121 std::vector<dom_int> &B = ret.
B;
122 std::vector<TRANS> &U = ret.
U;
123 std::vector<std::list<typename PERM::ptr> > S;
124 this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
126 unsigned int consecutiveSiftingElementCount = m_minimalConsecutiveSiftingElementCount;
127 if (m_knownOrder > 0) {
129 consecutiveSiftingElementCount = m_maxIterationFactor;
131 const unsigned int maxIterationCount = B.size() * m_maxIterationFactor;
132 for (
unsigned int it = 0; it < maxIterationCount; ++it) {
133 bool isProbableBSGS =
true;
134 for (
unsigned int i = 0; i < consecutiveSiftingElementCount && ret.
order() != m_knownOrder; ++i) {
135 PERM g = m_rng->next();
136 ++m_statRandomElementsConsidered;
138 unsigned int j = ret.
sift(g, h);
139 if (j < B.size() || !h.isIdentity()) {
148 BOOST_ASSERT(j < B.size());
149 S.push_back(std::list<typename PERM::ptr>());
150 U.push_back(TRANS(n));
153 boost::shared_ptr<PERM> hPtr(
new PERM(h));
154 S[j].insert(S[j].end(), hPtr);
157 isProbableBSGS =
false;
165 this->mergeGenerators(S, ret);
168 guaranteedBSGS = ret.template order<Integer>() == m_knownOrder;
base class for BSGS construction algorithms
Definition base_construction.h:46
abstract base class for random group element generators
Definition random_generator.h:42
BSGS construction with Random Schreier-Sims algorithm.
Definition random_schreier_sims_construction.h:51
const unsigned int m_minimalConsecutiveSiftingElementCount
number of elements that have to sift through constructed BSGS consecutively that it is returned as a ...
Definition random_schreier_sims_construction.h:88
const unsigned int m_maxIterationFactor
factor limiting the number of maximal iterations depeding on the initial base size
Definition random_schreier_sims_construction.h:91
unsigned int m_statRandomElementsConsidered
number of Schreier generators examined during the last construct call
Definition random_schreier_sims_construction.h:85
RandomSchreierSimsConstruction(unsigned int n, RandomGenerator< PERM > *rng, Integer knownOrder=0, unsigned int minimalConsecutiveSiftingElementCount=20, unsigned int maxIterationFactor=10000)
constructor
Definition random_schreier_sims_construction.h:102
BSGS< PERM, TRANS > construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, bool &guaranteedBSGS) const
constructs a probable BSGS for group given by generators with no base prescribed
Definition random_schreier_sims_construction.h:110
std::vector< TRANS > U
transversals along the stabilizer chain
Definition bsgs_core.h:59
std::vector< dom_int > B
base
Definition bsgs_core.h:55
Represents a base and strong generating set (BSGS)
Definition redundant_base_point_insertion_strategy.h:39
void orbitUpdate(unsigned int j, const PERMlist &generators, const typename PERM::ptr &g)
updates the j-th fundamental orbit with the given orbit generators and a new generator g
Definition bsgs.h:306
unsigned int sift(const PERM &g, PERM &siftee, unsigned int j=0) const
sifts an element through the specified transversal range
Definition bsgs.h:273
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition bsgs.h:290
Integer order() const
order of the group
Definition bsgs.h:407