40 #include <boost/cstdint.hpp> 41 #include <boost/foreach.hpp> 42 #include <boost/scoped_ptr.hpp> 43 #include <boost/shared_ptr.hpp> 44 #include <boost/utility.hpp> 46 #include <permlib/bsgs_core.h> 48 #include <permlib/transversal/orbit_set.h> 49 #include <permlib/transversal/transversal.h> 50 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 51 #include <permlib/predicate/stabilizes_point_predicate.h> 53 #include <permlib/redundant_base_point_insertion_strategy.h> 57 template <
class PERM,
class TRANS>
60 template <
class PERM,
class TRANS>
61 std::ostream &operator<< (std::ostream &out, const BSGS<PERM,TRANS> &bsgs) {
62 out <<
"BASE[" << bsgs.
B.size() <<
"]" << std::endl;
63 BOOST_FOREACH(
unsigned long beta, bsgs.B) {
64 out << static_cast<unsigned int>(beta+1) <<
",";
67 out <<
"SGS[" << bsgs.S.size() <<
"]" << std::endl;
68 BOOST_FOREACH(
const typename PERM::ptr &g, bsgs.S) {
72 out <<
"U" << std::endl;
73 BOOST_FOREACH(
const TRANS &U, bsgs.U) {
74 for (
unsigned int i=0; i<bsgs.n; ++i)
76 boost::scoped_ptr<PERM> dummy(U.at(i));
77 out << U.size() <<
"{" << U.m_statMaxDepth <<
"}" <<
",";
79 out <<
" = " << bsgs.order() << std::endl;
80 BOOST_FOREACH(
const TRANS &U, bsgs.U) {
81 out << U << std::endl;
87 template <
class PERM,
class TRANS>
89 typedef typename BSGSCore<PERM,TRANS>::PERMlist PERMlist;
92 explicit BSGS(dom_int
n);
111 template<
typename Integer>
112 Integer
order()
const;
118 boost::uint64_t
order()
const;
126 unsigned int sift(
const PERM& g, PERM& siftee,
unsigned int j = 0)
const;
134 unsigned int sift(
const PERM& g, PERM& siftee,
unsigned int j,
unsigned int k)
const;
136 bool sifts(
const PERM& g)
const;
170 void orbit(
unsigned int j,
const PERMlist &generators);
175 void orbitUpdate(
unsigned int j,
const PERMlist &generators,
const typename PERM::ptr &g);
195 PERM
random(
const int i = 0)
const;
205 friend std::ostream &operator<< <> (std::ostream &out,
const BSGS<PERM,TRANS> &bsgs);
208 template <
class BaseIterator,
class TransversalIterator>
209 unsigned int sift(
const PERM& g, PERM& siftee, BaseIterator begin, BaseIterator end, TransversalIterator beginT, TransversalIterator endT)
const;
212 static int ms_bsgsId;
222 template <
class PERM,
class TRANS>
223 int BSGS<PERM,TRANS>::ms_bsgsId = 0;
225 template <
class PERM,
class TRANS>
227 :
BSGSCore<PERM,TRANS>(++ms_bsgsId, n_, 0)
230 template <
class PERM,
class TRANS>
232 :
BSGSCore<PERM,TRANS>(bsgs.m_id, bsgs.B, bsgs.U, bsgs.n)
234 copyTransversals(bsgs);
237 template <
class PERM,
class TRANS>
244 this->m_id = bsgs.
m_id;
246 copyTransversals(bsgs);
250 template <
class PERM,
class TRANS>
251 template <
class BaseIterator,
class TransversalIterator>
252 unsigned int BSGS<PERM, TRANS>::sift(
const PERM& g, PERM& siftee, BaseIterator begin, BaseIterator end, TransversalIterator beginT, TransversalIterator endT)
const{
256 TransversalIterator transIt;
257 for (baseIt = begin, transIt = beginT; baseIt != end && transIt != endT; ++baseIt, ++transIt) {
258 unsigned long b = *baseIt;
259 const TRANS& U_i = *transIt;
261 boost::scoped_ptr<PERM> u_b(U_i.at(siftee / b));
264 u_b->invertInplace();
271 template <
class PERM,
class TRANS>
273 return sift(g, siftee, this->B.begin() + j, this->B.end(), this->U.begin() + j, this->U.end());
276 template <
class PERM,
class TRANS>
278 return sift(g, siftee, this->B.begin() + j, this->B.begin() + k, this->U.begin() + j, this->U.begin() + k);
281 template <
class PERM,
class TRANS>
283 PERM siftee(this->n);
284 unsigned int m = sift(g, siftee);
285 return this->B.size() == m && siftee.isIdentity();
288 template <
class PERM,
class TRANS>
290 for (beta = 0; beta < this->n; ++beta) {
291 if (std::find(this->B.begin(), this->B.end(), beta) != this->B.end())
293 if (h / beta != beta)
299 template <
class PERM,
class TRANS>
301 this->U[j].orbit(this->B[j], generators);
304 template <
class PERM,
class TRANS>
306 this->U[j].orbitUpdate(this->B[j], generators, g);
309 template <
class PERM,
class TRANS>
311 BOOST_ASSERT( i >= 0 );
313 for (
int l = this->U.size()-1; l>=i ; --l) {
315 unsigned long beta = *(boost::next(this->U[l].begin(), randomInt(this->U[l].size())));
316 boost::scoped_ptr<PERM> u_beta(this->U[l].at(beta));
322 template <
class PERM,
class TRANS>
325 gInv.invertInplace();
332 BOOST_FOREACH(
typename PERM::ptr& p, this->S) {
337 std::vector<dom_int> oldB(this->B);
338 for (
unsigned int i = 0; i < this->U.size(); ++i) {
340 this->B[i] = g / oldB[i];
342 this->U[i].permute(g, gInv);
346 template <
class PERM,
class TRANS>
349 for (;
static_cast<unsigned int>(pos) < this->B.size(); ++pos) {
350 if (*g / this->B[pos] != this->B[pos])
354 if (static_cast<unsigned int>(pos) == this->B.size()) {
356 bool newBaseElement __attribute__((unused)) = chooseBaseElement(*g, beta);
357 BOOST_ASSERT( newBaseElement );
358 this->B.push_back(beta);
359 this->U.push_back(TRANS(this->n));
362 const int insertionPosition = pos;
363 this->S.push_back(g);
366 bool groupOrderChanged =
false;
367 for (; pos >= 0; --pos) {
368 PERMlist orbitGenerators;
369 const unsigned int oldTransversalSize = this->U[pos].size();
371 std::copy_if(this->S.begin(), this->S.end(), std::back_inserter(orbitGenerators),
373 if (orbitGenerators.size() > 0) {
374 orbitUpdate(pos, orbitGenerators, g);
377 if (this->U[pos].size() > oldTransversalSize)
378 groupOrderChanged =
true;
382 if (!groupOrderChanged) {
388 return insertionPosition;
391 template <
class PERM,
class TRANS>
395 for (; pos >= 0; --pos) {
396 PERMlist orbitGenerators;
397 std::copy_if(this->S.begin(), this->S.end(), std::back_inserter(orbitGenerators),
399 if (orbitGenerators.size() > 0)
400 orbit(pos, orbitGenerators);
404 template <
class PERM,
class TRANS>
405 template <
typename Integer>
407 Integer orderValue(1);
408 BOOST_FOREACH(
const TRANS &Ui, this->U) {
409 orderValue *= Ui.size();
414 template <
class PERM,
class TRANS>
416 return order<boost::uint64_t>();
420 template <
class PERM,
class TRANS>
427 pos = std::max(static_cast<unsigned int>(pos), minPos);
429 this->B.insert(this->B.begin() + pos, beta);
430 this->U.insert(this->U.begin() + pos, TRANS(this->n));
431 this->U[pos].orbit(beta, S_i);
435 template <
class PERM,
class TRANS>
437 for (
int i = this->B.size()-1; i >= minPos; --i) {
438 if (this->U[i].size() <= 1) {
439 if (i == static_cast<int>(this->B.size()-1)) {
443 this->B.erase(this->B.begin() + i);
444 this->U.erase(this->U.begin() + i);
456 template <
class PERM>
463 template<
class InputIterator>
467 bool operator()(
const typename PERM::ptr& p1,
const typename PERM::ptr& p2)
const {
468 BOOST_FOREACH(
const dom_int b, m_base) {
469 if ( p1->at(b) == b && p2->at(b) != b )
471 if ( p1->at(b) != b )
477 std::vector<dom_int> m_base;
480 template <
class PERM,
class TRANS>
482 PERMlist sortedSGS(this->S);
485 PERMlist filteredSGS;
487 dom_int oldBaseElement =
static_cast<dom_int
>(-1);
488 BOOST_FOREACH(
const typename PERM::ptr& gen, sortedSGS) {
489 if (gen->isIdentity())
491 filteredSGS.push_back(gen);
497 dom_int baseElement = this->B.front();
498 BOOST_FOREACH(
const dom_int b, this->B) {
503 PERMLIB_DEBUG(std::cout <<
"gen " << *gen <<
" @ " << baseElement << std::endl;)
507 if (oldBaseElement == baseElement && newOrbit->
size() == oldOrbit->
size()) {
509 PERMLIB_DEBUG(std::cout <<
" removed\n";)
510 filteredSGS.pop_back();
515 oldBaseElement = baseElement;
519 this->S = filteredSGS;
522 template <
class PERM,
class TRANS>
524 std::map<PERM*,typename PERM::ptr> genMap;
525 BOOST_FOREACH(
const typename PERM::ptr& p, bsgs.
S) {
526 typename PERM::ptr deepcopy(
new PERM(*p));
528 genMap.insert(std::make_pair(p.get(), deepcopy));
529 this->S.push_back(deepcopy);
532 BOOST_ASSERT(this->B.size() == bsgs.
B.size());
533 BOOST_ASSERT(bsgs.
B.size() == bsgs.
U.size());
535 this->U.resize(bsgs.
U.size(), TRANS(bsgs.
n));
536 BOOST_ASSERT(this->U.size() == bsgs.
U.size());
538 for (
unsigned int i=0; i<this->U.size(); ++i) {
539 this->U[i] = bsgs.
U[i].clone(genMap);
dom_int n
degree of group
Definition: bsgs_core.h:61
action of a PERM on unsigned long element
Definition: transversal.h:112
unsigned int insertRedundantBasePoint(unsigned int beta, unsigned int minPos=0)
inserts a redundant base beta
Definition: bsgs.h:421
BSGS< PERM, TRANS > & operator=(const BSGS< PERM, TRANS > &)
assignment operator
Definition: bsgs.h:238
insertion position after first non-trivial transversal
Definition: redundant_base_point_insertion_strategy.h:68
Class that can be used to sort a strong generating set.
Definition: bsgs.h:457
bool sifts(const PERM &g) const
true iff g sifts through transversal system
Definition: bsgs.h:282
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:305
stores an orbit in a set for fast contains() operation
Definition: orbit_set.h:42
BSGS(dom_int n)
constructs an empty group of degree n
Definition: bsgs.h:226
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
core data of a base and strong generating set (BSGS)
Definition: bsgs_core.h:42
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
Integer order() const
order of the group
Definition: bsgs.h:406
StrongGeneratingSetSorter(InputIterator baseBegin, InputIterator baseEnd)
Definition: bsgs.h:464
unsigned int sift(const PERM &g, PERM &siftee, unsigned int j=0) const
sifts an element through the specified transversal range
Definition: bsgs.h:272
int m_id
id of this BSGS instance
Definition: bsgs_core.h:81
void conjugate(const PERM &g)
conjugate group with a permutation
Definition: bsgs.h:323
void stripRedundantBasePoints(int minPos=0)
strips redundant base points from the end to the minPos-th base element
Definition: bsgs.h:436
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
size_t size() const
number of orbit elements
Definition: orbit_set.h:60
PERM random(const int i=0) const
generates a uniformly distributed random element of
Definition: bsgs.h:310
int insertGenerator(const typename PERM::ptr &g, bool updateOrbit)
adds a new group generator
Definition: bsgs.h:347
bool operator()(const typename PERM::ptr &p1, const typename PERM::ptr &p2) const
true iff p1 stabilizes more base points (in increasing order) than p2
Definition: bsgs.h:467
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
virtual int findInsertionPoint(dom_int beta, std::list< typename PERM::ptr > &S_i) const
finds possible insertion point for base point
Definition: redundant_base_point_insertion_strategy.h:73
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
void orbit(unsigned int j, const PERMlist &generators)
re-computes the j-th fundamental orbit with the given orbit generators
Definition: bsgs.h:300
void stripRedundantStrongGenerators()
removes redundant generators
Definition: bsgs.h:481
void updateOrbits(int pos)
updates transversals/orbits
Definition: bsgs.h:392
PERMlist S
strong generating set
Definition: bsgs_core.h:57
Definition: abstract_bsgs.h:49