33#ifndef BASECONSTRUCTION_H
34#define BASECONSTRUCTION_H
39#include <permlib/predicate/pointwise_stabilizer_predicate.h>
40#include <permlib/predicate/identity_predicate.h>
45template <
class PERM,
class TRANS>
66 template <
class ForwardIterator,
class InputIterator>
67 void setup(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd,
BSGS<PERM, TRANS> &bsgs, std::vector<std::list<typename PERM::ptr> > &S)
const;
73 static const unsigned long *
empty;
80template <
class PERM,
class TRANS>
84template <
class PERM,
class TRANS>
89template <
class PERM,
class TRANS>
90template <
class ForwardIterator,
class InputIterator>
93 std::vector<dom_int> &B = bsgs.
B;
94 std::vector<TRANS> &U = bsgs.
U;
96 std::list<typename PERM::ptr> nonIdentityGenerators;
97 std::remove_copy_if(generatorsBegin, generatorsEnd, std::back_inserter(nonIdentityGenerators),
IdentityPredicate<PERM>());
99 B.insert(B.begin(), prescribedBaseBegin, prescribedBaseEnd);
101 dom_int beta =
m_n + 1;
103 BOOST_FOREACH(
const typename PERM::ptr &gen, nonIdentityGenerators) {
116 std::list<typename PERM::ptr> S_0;
118 U[0].orbit(B[0], S_0);
125 std::vector<dom_int>::iterator Bit;
126 for (Bit = B.begin(); Bit != B.end(); ++Bit) {
127 std::list<typename PERM::ptr> S_i;
128 std::copy_if(nonIdentityGenerators.begin(), nonIdentityGenerators.end(),
140template <
class PERM,
class TRANS>
142 std::map<PERM*,typename PERM::ptr> generatorMap;
144 BOOST_FOREACH(std::list<typename PERM::ptr> &S_j, S) {
145 BOOST_FOREACH(
typename PERM::ptr &gen, S_j) {
147 BOOST_FOREACH(
const typename PERM::ptr& genS, ret.
S) {
150 generatorMap.insert(std::make_pair(gen.get(), genS));
155 ret.
S.push_back(gen);
156 generatorMap.insert(std::make_pair(gen.get(), gen));
161 BOOST_FOREACH(
TRANS& U_i, ret.
U) {
162 U_i.updateGenerators(generatorMap);
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
predicate matching a permutation if it stabilizes a given list of points pointwise
Definition identity_predicate.h:42
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
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition bsgs.h:301
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition bsgs.h:290