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> 50 template <
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;
101 template <
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)
108 template <
class PERM,
class TRANS,
typename Integer>
109 template <
class ForwardIterator>
114 template <
class PERM,
class TRANS,
typename Integer>
115 template <
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;
175 #endif // -- RANDOMSCHREIERSIMSCONSTRUCTION_H_ abstract base class for random group element generators
Definition: random_generator.h:42
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:305
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
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
BSGS construction with Random Schreier-Sims algorithm.
Definition: random_schreier_sims_construction.h:51
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
Integer order() const
order of the group
Definition: bsgs.h:406
unsigned int sift(const PERM &g, PERM &siftee, unsigned int j=0) const
sifts an element through the specified transversal range
Definition: bsgs.h:272
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
base class for BSGS construction algorithms
Definition: base_construction.h:46
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
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
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
unsigned int m_statRandomElementsConsidered
number of Schreier generators examined during the last construct call
Definition: random_schreier_sims_construction.h:85
Definition: abstract_bsgs.h:49