33#ifndef SCHREIERSIMSCONSTRUCTION_H_
34#define SCHREIERSIMSCONSTRUCTION_H_
36#include <permlib/construct/base_construction.h>
37#include <permlib/bsgs.h>
38#include <permlib/generator/schreier_generator.h>
40#include <boost/foreach.hpp>
45template <
class PERM,
class TRANS>
57 template <
class ForwardIterator>
67 template <
class ForwardIterator,
class InputIterator>
68 BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd)
const;
78template <
class PERM,
class TRANS>
83template <
class PERM,
class TRANS>
84template <
class ForwardIterator>
89template <
class PERM,
class TRANS>
90template <
class ForwardIterator,
class InputIterator>
92 ::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd)
const
94 const dom_int &n = this->
m_n;
96 std::vector<dom_int> &B = ret.
B;
97 std::vector<TRANS> &U = ret.
U;
98 std::vector<std::list<typename PERM::ptr> > S;
99 this->
setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
101 std::vector<boost::shared_ptr<SchreierGenerator<PERM, TRANS> > > SchreierGens;
102 for (
unsigned int i = 0; i < B.size(); ++i) {
103 BOOST_ASSERT( i < U.size() );
104 BOOST_ASSERT( i < S.size() );
108 unsigned int j = B.size();
109 bool breakUp =
false;
113 sg.
update(&U[j-1], S[j-1].begin(), S[j-1].end());
117 PERMLIB_DEBUG(
for(
unsigned int jjj=0; jjj<j; ++jjj) std::cout <<
" ";)
118 PERMLIB_DEBUG(std::cout <<
"schreier j = " << (j-1) <<
" [" << S[j-1].size() <<
"," << U[j-1].size() <<
"]: ";)
122 unsigned int k = ret.
sift(g, h, j);
123 if (k < B.size() - j || !h.isIdentity()) {
132 BOOST_ASSERT(j < B.size());
133 S.push_back(std::list<typename PERM::ptr>());
134 U.push_back(
TRANS(n));
136 boost::shared_ptr<PERM> hPtr(
new PERM(h));
137 S[j].insert(S[j].end(), hPtr);
140 if (j >= SchreierGens.size()) {
142 SchreierGens.push_back(localVar);
144 SchreierGens[j]->update(S[j].size() - 1);
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
stateful generator of Schreier generators
Definition schreier_generator.h:55
PERM next()
generates an element
Definition schreier_generator.h:185
bool hasNext()
true, iff more elements can be generated
Definition schreier_generator.h:142
void update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end)
updates transversal and group generators that the Schreier generators are constructed from
Definition schreier_generator.h:216
BSGS construction with classic Schreier-Sims algorithm.
Definition schreier_sims_construction.h:46
unsigned int m_statScheierGeneratorsConsidered
number of Schreier generators examined during the last construct call
Definition schreier_sims_construction.h:71
BSGS< PERM, TRANS > construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const
constructs a BSGS for group given by generators with no base prescribed
Definition schreier_sims_construction.h:85
SchreierSimsConstruction(unsigned int n)
constructor
Definition schreier_sims_construction.h:79
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