33 #ifndef SCHREIERGENERATOR_H_ 34 #define SCHREIERGENERATOR_H_ 36 #include <permlib/common.h> 37 #include <permlib/generator/generator.h> 40 #include <boost/scoped_ptr.hpp> 41 #include <boost/tuple/tuple.hpp> 53 template <
class PERM,
class TRANS>
57 typedef typename std::list<typename PERM::ptr>::const_iterator
PERMlistIt;
59 typedef typename std::list<unsigned long>::const_iterator
TRANSlistIt;
87 void update(
unsigned int j);
97 unsigned int m_posSlimit;
99 unsigned int m_posUlimit;
102 unsigned long m_beta;
104 std::stack<boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> > m_stackTodo;
118 template <
class PERM,
class TRANS>
120 : m_Sbegin(S_begin), m_Scurrent(S_begin), m_Send(S_end),
121 m_U(U), m_Ubegin(m_U->begin()), m_Ucurrent(m_U->begin()), m_Uend(m_U->end()),
122 m_posS(0), m_posSlimit(0), m_posU(0), m_posUlimit(0), m_u_beta(0)
127 template <
class PERM,
class TRANS>
132 template <
class PERM,
class TRANS>
133 void SchreierGenerator<PERM, TRANS>::init() {
134 m_beta = *m_Ucurrent;
136 m_u_beta = m_U->at(m_beta);
140 template <
class PERM,
class TRANS>
142 if (m_Send != m_Scurrent && m_Uend != m_Ucurrent && (!m_posUlimit || m_posU < m_posUlimit)) {
143 const PERM &x = **m_Scurrent;
144 if (m_U->trivialByDefinition(x, x / m_beta)) {
151 if (!m_stackTodo.empty()) {
152 boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> lastTuple = m_stackTodo.top();
155 m_posS = boost::get<0>(lastTuple);
156 m_posSlimit = boost::get<1>(lastTuple);
157 m_posU = boost::get<2>(lastTuple);
158 m_posUlimit = boost::get<3>(lastTuple);
166 template <
class PERM,
class TRANS>
170 if (m_Scurrent == m_Send) {
171 m_Scurrent = boost::next(m_Sbegin, m_posSlimit);
172 m_posS = m_posSlimit;
175 if (m_Ucurrent != m_Uend)
183 template <
class PERM,
class TRANS>
185 BOOST_ASSERT(m_Scurrent != m_Send);
186 BOOST_ASSERT(m_Ucurrent != m_Uend);
188 PERMLIB_DEBUG(std::cout <<
"s = " << m_posS <<
"; u = " << m_posU << std::endl;)
189 const PERM &x = **m_Scurrent;
191 PERM g = *m_u_beta * x;
192 boost::scoped_ptr<PERM> u_beta_ptr2(m_U->at(x / m_beta));
193 u_beta_ptr2->invertInplace();
201 template <
class PERM,
class TRANS>
203 m_Scurrent = m_Sbegin;
204 m_Ucurrent = m_Ubegin;
206 while (--i>=0) ++m_Scurrent;
208 while (--i>=0) ++m_Ucurrent;
210 if (m_Ucurrent != m_Uend)
214 template <
class PERM,
class TRANS>
216 if (U == m_U && S_begin == m_Sbegin && S_end == m_Send)
221 m_Ubegin = U->begin();
226 template <
class PERM,
class TRANS>
228 m_stackTodo.push(boost::make_tuple(m_posS, m_posSlimit, m_posU, m_posUlimit));
229 m_posUlimit = m_posU;
238 #endif // -- SCHREIERGENERATOR_H_ SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end)
constructor
Definition: schreier_generator.h:119
interface for group element generators
Definition: generator.h:40
stateful generator of Schreier generators
Definition: schreier_generator.h:54
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:215
std::list< unsigned long >::const_iterator TRANSlistIt
const iterator to a list of points (unsigned long)
Definition: schreier_generator.h:59
PERM next()
generates an element
Definition: schreier_generator.h:184
Definition: abstract_bsgs.h:49
bool hasNext()
true, iff more elements can be generated
Definition: schreier_generator.h:141
std::list< typename PERM::ptr >::const_iterator PERMlistIt
const iterator to a list of PERMutations
Definition: schreier_generator.h:57