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)
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);
127 if (m_knownOrder > 0) {
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();
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;
168 guaranteedBSGS = ret.template order<Integer>() == m_knownOrder;
static const unsigned long * empty
auxilliary element marking an empty iterator
Definition base_construction.h:73
BaseConstruction(dom_int n)
constructor
Definition base_construction.h:85
dom_int m_n
cardinality of the set the group is acting on
Definition base_construction.h:55
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
Definition base_construction.h:141
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
Definition base_construction.h:91
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 bsgs.h:89
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