40 #include <boost/cstdint.hpp>
41 #include <boost/foreach.hpp>
42 #include <boost/next_prior.hpp>
43 #include <boost/scoped_ptr.hpp>
44 #include <boost/shared_ptr.hpp>
45 #include <boost/utility.hpp>
47 #include <permlib/bsgs_core.h>
49 #include <permlib/transversal/orbit_set.h>
50 #include <permlib/transversal/transversal.h>
51 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
52 #include <permlib/predicate/stabilizes_point_predicate.h>
54 #include <permlib/redundant_base_point_insertion_strategy.h>
58 template <
class PERM,
class TRANS>
61 template <
class PERM,
class TRANS>
63 out <<
"BASE[" << bsgs.B.size() <<
"]" << std::endl;
64 BOOST_FOREACH(
unsigned long beta, bsgs.B) {
65 out << static_cast<unsigned int>(beta+1) <<
",";
68 out <<
"SGS[" << bsgs.S.size() <<
"]" << std::endl;
69 BOOST_FOREACH(
const typename PERM::ptr &g, bsgs.S) {
73 out <<
"U" << std::endl;
74 BOOST_FOREACH(
const TRANS &U, bsgs.U) {
75 for (
unsigned int i=0; i<bsgs.n; ++i)
77 boost::scoped_ptr<PERM> dummy(U.at(i));
78 out << U.size() <<
"{" << U.m_statMaxDepth <<
"}" <<
",";
80 out <<
" = " << bsgs.
order() << std::endl;
81 BOOST_FOREACH(
const TRANS &U, bsgs.U) {
82 out << U << std::endl;
88 template <
class PERM,
class TRANS>
90 typedef typename BSGSCore<PERM,TRANS>::PERMlist PERMlist;
93 explicit BSGS(dom_int n);
112 template<
typename Integer>
113 Integer
order()
const;
119 boost::uint64_t
order()
const;
127 unsigned int sift(
const PERM& g, PERM& siftee,
unsigned int j = 0)
const;
135 unsigned int sift(
const PERM& g, PERM& siftee,
unsigned int j,
unsigned int k)
const;
137 bool sifts(
const PERM& g)
const;
171 void orbit(
unsigned int j,
const PERMlist &generators);
176 void orbitUpdate(
unsigned int j,
const PERMlist &generators,
const typename PERM::ptr &g);
196 PERM
random(
const int i = 0)
const;
206 friend std::ostream &operator<< <> (std::ostream &out,
const BSGS<PERM,TRANS> &bsgs);
209 template <
class BaseIterator,
class TransversalIterator>
210 unsigned int sift(
const PERM& g, PERM& siftee, BaseIterator begin, BaseIterator end, TransversalIterator beginT, TransversalIterator endT)
const;
213 static int ms_bsgsId;
223 template <
class PERM,
class TRANS>
224 int BSGS<PERM,TRANS>::ms_bsgsId = 0;
226 template <
class PERM,
class TRANS>
228 :
BSGSCore<PERM,TRANS>(++ms_bsgsId, n_, 0)
231 template <
class PERM,
class TRANS>
233 :
BSGSCore<PERM,TRANS>(bsgs.m_id, bsgs.B, bsgs.U, bsgs.n)
235 copyTransversals(bsgs);
238 template <
class PERM,
class TRANS>
245 this->m_id = bsgs.m_id;
247 copyTransversals(bsgs);
251 template <
class PERM,
class TRANS>
252 template <
class BaseIterator,
class TransversalIterator>
253 unsigned int BSGS<PERM, TRANS>::sift(
const PERM& g, PERM& siftee, BaseIterator begin, BaseIterator end, TransversalIterator beginT, TransversalIterator endT)
const{
257 TransversalIterator transIt;
258 for (baseIt = begin, transIt = beginT; baseIt != end && transIt != endT; ++baseIt, ++transIt) {
259 unsigned long b = *baseIt;
260 const TRANS& U_i = *transIt;
262 boost::scoped_ptr<PERM> u_b(U_i.at(siftee / b));
265 u_b->invertInplace();
272 template <
class PERM,
class TRANS>
274 return sift(g, siftee, this->B.begin() + j, this->B.end(), this->U.begin() + j, this->U.end());
277 template <
class PERM,
class TRANS>
279 return sift(g, siftee, this->B.begin() + j, this->B.begin() + k, this->U.begin() + j, this->U.begin() + k);
282 template <
class PERM,
class TRANS>
284 PERM siftee(this->n);
285 unsigned int m = sift(g, siftee);
286 return this->B.size() == m && siftee.isIdentity();
289 template <
class PERM,
class TRANS>
291 for (beta = 0; beta < this->n; ++beta) {
292 if (std::find(this->B.begin(), this->B.end(), beta) != this->B.end())
294 if (h / beta != beta)
300 template <
class PERM,
class TRANS>
302 this->U[j].orbit(this->B[j], generators);
305 template <
class PERM,
class TRANS>
307 this->U[j].orbitUpdate(this->B[j], generators, g);
310 template <
class PERM,
class TRANS>
312 BOOST_ASSERT( i >= 0 );
314 for (
int l = this->U.size()-1; l>=i ; --l) {
316 unsigned long beta = *(boost::next(this->U[l].begin(), randomInt(this->U[l].size())));
317 boost::scoped_ptr<PERM> u_beta(this->U[l].at(beta));
323 template <
class PERM,
class TRANS>
326 gInv.invertInplace();
333 BOOST_FOREACH(
typename PERM::ptr& p, this->S) {
338 std::vector<dom_int> oldB(this->B);
339 for (
unsigned int i = 0; i < this->U.size(); ++i) {
341 this->B[i] = g / oldB[i];
343 this->U[i].permute(g, gInv);
347 template <
class PERM,
class TRANS>
350 for (;
static_cast<unsigned int>(pos) < this->B.size(); ++pos) {
351 if (*g / this->B[pos] != this->B[pos])
355 if (
static_cast<unsigned int>(pos) == this->B.size()) {
357 bool newBaseElement __attribute__((unused)) = chooseBaseElement(*g, beta);
358 BOOST_ASSERT( newBaseElement );
359 this->B.push_back(beta);
360 this->U.push_back(TRANS(this->n));
363 const int insertionPosition = pos;
364 this->S.push_back(g);
367 bool groupOrderChanged =
false;
368 for (; pos >= 0; --pos) {
369 PERMlist orbitGenerators;
370 const unsigned int oldTransversalSize = this->U[pos].size();
372 std::copy_if(this->S.begin(), this->S.end(), std::back_inserter(orbitGenerators),
374 if (orbitGenerators.size() > 0) {
375 orbitUpdate(pos, orbitGenerators, g);
378 if (this->U[pos].size() > oldTransversalSize)
379 groupOrderChanged =
true;
383 if (!groupOrderChanged) {
389 return insertionPosition;
392 template <
class PERM,
class TRANS>
396 for (; pos >= 0; --pos) {
397 PERMlist orbitGenerators;
398 std::copy_if(this->S.begin(), this->S.end(), std::back_inserter(orbitGenerators),
400 if (orbitGenerators.size() > 0)
401 orbit(pos, orbitGenerators);
405 template <
class PERM,
class TRANS>
406 template <
typename Integer>
408 Integer orderValue(1);
409 BOOST_FOREACH(
const TRANS &Ui, this->U) {
410 orderValue *= Ui.size();
415 template <
class PERM,
class TRANS>
417 return order<boost::uint64_t>();
421 template <
class PERM,
class TRANS>
428 pos = std::max(
static_cast<unsigned int>(pos), minPos);
430 this->B.insert(this->B.begin() + pos, beta);
431 this->U.insert(this->U.begin() + pos, TRANS(this->n));
432 this->U[pos].orbit(beta, S_i);
436 template <
class PERM,
class TRANS>
438 for (
int i = this->B.size()-1; i >= minPos; --i) {
439 if (this->U[i].size() <= 1) {
440 if (i ==
static_cast<int>(this->B.size()-1)) {
444 this->B.erase(this->B.begin() + i);
445 this->U.erase(this->U.begin() + i);
457 template <
class PERM>
464 template<
class InputIterator>
468 bool operator()(
const typename PERM::ptr& p1,
const typename PERM::ptr& p2)
const {
469 BOOST_FOREACH(
const dom_int b, m_base) {
470 if ( p1->at(b) == b && p2->at(b) != b )
472 if ( p1->at(b) != b )
478 std::vector<dom_int> m_base;
481 template <
class PERM,
class TRANS>
483 PERMlist sortedSGS(this->S);
486 PERMlist filteredSGS;
488 dom_int oldBaseElement =
static_cast<dom_int
>(-1);
489 BOOST_FOREACH(
const typename PERM::ptr& gen, sortedSGS) {
490 if (gen->isIdentity())
492 filteredSGS.push_back(gen);
498 dom_int baseElement = this->B.front();
499 BOOST_FOREACH(
const dom_int b, this->B) {
504 PERMLIB_DEBUG(std::cout <<
"gen " << *gen <<
" @ " << baseElement << std::endl;)
508 if (oldBaseElement == baseElement && newOrbit->size() == oldOrbit->
size()) {
510 PERMLIB_DEBUG(std::cout <<
" removed\n";)
511 filteredSGS.pop_back();
516 oldBaseElement = baseElement;
520 this->S = filteredSGS;
523 template <
class PERM,
class TRANS>
525 std::map<PERM*,typename PERM::ptr> genMap;
526 BOOST_FOREACH(
const typename PERM::ptr& p, bsgs.S) {
527 typename PERM::ptr deepcopy(
new PERM(*p));
529 genMap.insert(std::make_pair(p.get(), deepcopy));
530 this->S.push_back(deepcopy);
533 BOOST_ASSERT(this->B.size() == bsgs.B.size());
534 BOOST_ASSERT(bsgs.B.size() == bsgs.U.size());
536 this->U.resize(bsgs.U.size(), TRANS(bsgs.n));
537 BOOST_ASSERT(this->U.size() == bsgs.U.size());
539 for (
unsigned int i=0; i<this->U.size(); ++i) {
540 this->U[i] = bsgs.U[i].clone(genMap);