33#ifndef BASETRANSPOSE_H_
34#define BASETRANSPOSE_H_
36#include <permlib/predicate/pointwise_stabilizer_predicate.h>
37#include <permlib/generator/generator.h>
39#include <boost/scoped_ptr.hpp>
40#include <boost/iterator/indirect_iterator.hpp>
41#include <boost/next_prior.hpp>
49template<
class PERM,
class TRANS>
69 typedef std::list<typename PERM::ptr> PERMlist;
85template<
class PERM,
class TRANS>
90template<
class PERM,
class TRANS>
92 std::vector<dom_int> &B = bsgs.
B;
93 std::vector<TRANS> &U = bsgs.
U;
102 std::swap(B[i], B[i+1]);
107 unsigned int targetTransversalSize = U[i+1].size() * U[i].size();
111 U_i.orbit(B[i], S_i);
112 targetTransversalSize /= U_i.size();
116 TRANS U_i1(U[i+1].n());
117 U_i1.orbit(B[i+1], S_i1);
118 boost::scoped_ptr<Generator<PERM> > generator(
setupGenerator(bsgs, i, S_i, U_i));
119 BOOST_ASSERT(generator != 0);
121 while (U_i1.size() < targetTransversalSize) {
122 bool newGeneratorFound =
false;
123 while (generator->hasNext()) {
124 PERM g = generator->next();
126 boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end());
127 if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) {
129 boost::shared_ptr<PERM> gen(
new PERM(g));
130 S_i1.push_front(gen);
132 U_i1.orbitUpdate(B[i+1], S_i1, gen);
133 newGeneratorFound =
true;
137 if (!newGeneratorFound)
141 BOOST_ASSERT(U_i1.size() >= targetTransversalSize);
unsigned int m_statScheierGeneratorsConsidered
Definition base_transpose.h:65
unsigned int m_statNewGenerators
Definition base_transpose.h:67
void transpose(BSGS< PERM, TRANS > &bsgs, unsigned int i) const
performs a base transposition on bsgs between bsgs.B[i] and bsgs.B[i+1]
Definition base_transpose.h:91
BaseTranspose()
constructor
Definition base_transpose.h:86
virtual Generator< PERM > * setupGenerator(BSGS< PERM, TRANS > &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const =0
initializes the specific Schreier Generator that is used for the BaseTranpose implementation
virtual ~BaseTranspose()
virtual destructor
Definition base_transpose.h:55
interface for group element generators
Definition generator.h:40
predicate matching a permutation if it stabilizes a given list of points pointwise
Definition pointwise_stabilizer_predicate.h:42
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
copies elements of (begin to end) to destBegin if they match the given predicate
Definition common.h:49
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
PERMlist S
strong generating set
Definition bsgs_core.h:57
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89