permlib  0.2.9
Library for permutation computations
schreier_sims_construction.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef SCHREIERSIMSCONSTRUCTION_H_
34 #define SCHREIERSIMSCONSTRUCTION_H_
35 
36 #include <permlib/construct/base_construction.h>
37 #include <permlib/bsgs.h>
38 #include <permlib/generator/schreier_generator.h>
39 
40 #include <boost/foreach.hpp>
41 
42 namespace permlib {
43 
45 template <class PERM, class TRANS>
46 class SchreierSimsConstruction : public BaseConstruction<PERM, TRANS> {
47 public:
49 
52  explicit SchreierSimsConstruction(unsigned int n);
53 
55 
57  template <class ForwardIterator>
58  BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const;
59 
61 
67  template <class ForwardIterator, class InputIterator>
68  BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const;
69 
71  mutable unsigned int m_statScheierGeneratorsConsidered;
72 };
73 
74 //
75 // ---- IMPLEMENTATION
76 //
77 
78 template <class PERM, class TRANS>
80  : BaseConstruction<PERM, TRANS>(n), m_statScheierGeneratorsConsidered(0)
81 { }
82 
83 template <class PERM, class TRANS>
84 template <class ForwardIterator>
85 inline BSGS<PERM, TRANS> SchreierSimsConstruction<PERM,TRANS>::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const {
86  return construct(generatorsBegin, generatorsEnd, BaseConstruction<PERM,TRANS>::empty, BaseConstruction<PERM,TRANS>::empty);
87 }
88 
89 template <class PERM, class TRANS>
90 template <class ForwardIterator, class InputIterator>
92  ::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const
93 {
94  const dom_int &n = this->m_n;
95  BSGS<PERM, TRANS> ret(n);
96  std::vector<dom_int> &B = ret.B;
97  std::vector<TRANS> &U = ret.U;
98  std::vector<std::list<typename PERM::ptr> > S;
99  this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S);
100 
101  std::vector<boost::shared_ptr<SchreierGenerator<PERM, TRANS> > > SchreierGens;
102  for (unsigned int i = 0; i < B.size(); ++i) {
103  BOOST_ASSERT( i < U.size() );
104  BOOST_ASSERT( i < S.size() );
105  SchreierGens.push_back(boost::shared_ptr<SchreierGenerator<PERM, TRANS> >(new SchreierGenerator<PERM, TRANS>(&U[i], S[i].begin(), S[i].end())));
106  }
107 
108  unsigned int j = B.size();
109  bool breakUp = false;
110  while (j >= 1) {
111  breakUp = false;
112  SchreierGenerator<PERM, TRANS> &sg = *SchreierGens[j-1];
113  sg.update(&U[j-1], S[j-1].begin(), S[j-1].end());
114 
115  while (sg.hasNext()) {
116  ++m_statScheierGeneratorsConsidered;
117  PERMLIB_DEBUG(for(unsigned int jjj=0; jjj<j; ++jjj) std::cout << " ";)
118  PERMLIB_DEBUG(std::cout << "schreier j = " << (j-1) << " [" << S[j-1].size() << "," << U[j-1].size() << "]: ";)
119  PERM g = sg.next();
120  PERM h(n);
121  // sift for S_{j+1}, so use index j here
122  unsigned int k = ret.sift(g, h, j);
123  if (k < B.size() - j || !h.isIdentity()) {
124  // flush it, because we add it as a generator
125  h.flush();
126 
127  if (j == B.size()) {
128  dom_int gamma = n+1;
129  if (ret.chooseBaseElement(h, gamma)) {
130  B.push_back(gamma);
131  }
132  BOOST_ASSERT(j < B.size());
133  S.push_back(std::list<typename PERM::ptr>());
134  U.push_back(TRANS(n));
135  }
136  boost::shared_ptr<PERM> hPtr(new PERM(h));
137  S[j].insert(S[j].end(), hPtr);
138 
139  ret.orbitUpdate(j, S[j], hPtr);
140  if (j >= SchreierGens.size()) {
141  boost::shared_ptr<SchreierGenerator<PERM, TRANS> > localVar(new SchreierGenerator<PERM, TRANS>(&U[j], S[j].begin(), S[j].end()));
142  SchreierGens.push_back(localVar);
143  } else {
144  SchreierGens[j]->update(S[j].size() - 1);
145  }
146 
147  breakUp = true;
148  ++j;
149  break;
150  }
151  }
152  if (!breakUp)
153  --j;
154  }
155 
156  this->mergeGenerators(S, ret);
157 
158  return ret;
159 }
160 
161 }
162 
163 #endif // -- SCHREIERSIMSCONSTRUCTION_H_
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
bool chooseBaseElement(const PERM &h, dom_int &beta) const
tries to find a new base element
Definition: bsgs.h:289
stateful generator of Schreier generators
Definition: schreier_generator.h:54
BSGS< PERM, TRANS > construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const
constructs a BSGS for group given by generators with no base prescribed
Definition: schreier_sims_construction.h:85
SchreierSimsConstruction(unsigned int n)
constructor
Definition: schreier_sims_construction.h:79
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
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
std::vector< dom_int > B
base
Definition: bsgs_core.h:55
base class for BSGS construction algorithms
Definition: base_construction.h:46
unsigned int m_statScheierGeneratorsConsidered
number of Schreier generators examined during the last construct call
Definition: schreier_sims_construction.h:71
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
std::vector< TRANS > U
transversals along the stabilizer chain
Definition: bsgs_core.h:59
PERM next()
generates an element
Definition: schreier_generator.h:184
BSGS construction with classic Schreier-Sims algorithm.
Definition: schreier_sims_construction.h:46
Definition: abstract_bsgs.h:49
bool hasNext()
true, iff more elements can be generated
Definition: schreier_generator.h:141