permlib  0.2.9
Library for permutation computations
schreier_generator.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 SCHREIERGENERATOR_H_
34 #define SCHREIERGENERATOR_H_
35 
36 #include <permlib/common.h>
37 #include <permlib/generator/generator.h>
38 
39 #include <stack>
40 #include <boost/scoped_ptr.hpp>
41 #include <boost/tuple/tuple.hpp>
42 
43 namespace permlib {
44 
46 
53 template <class PERM, class TRANS>
54 class SchreierGenerator : public Generator<PERM> {
55 public:
57  typedef typename std::list<typename PERM::ptr>::const_iterator PERMlistIt;
59  typedef typename std::list<unsigned long>::const_iterator TRANSlistIt;
60 
62 
67  SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end);
68  virtual ~SchreierGenerator();
69 
70  PERM next();
71  bool hasNext();
72 
74 
79  void update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end);
80 
82 
87  void update(unsigned int j);
88 private:
89  PERMlistIt m_Sbegin;
90  PERMlistIt m_Scurrent;
91  PERMlistIt m_Send;
92  const TRANS *m_U;
93  TRANSlistIt m_Ubegin;
94  TRANSlistIt m_Ucurrent;
95  TRANSlistIt m_Uend;
96  unsigned int m_posS;
97  unsigned int m_posSlimit;
98  unsigned int m_posU;
99  unsigned int m_posUlimit;
100 
101  PERM* m_u_beta;
102  unsigned long m_beta;
103 
104  std::stack<boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> > m_stackTodo;
105 
107  bool advance();
109  void init();
111  void reset();
112 };
113 
114 //
115 // ---- IMPLEMENTATION
116 //
117 
118 template <class PERM, class TRANS>
120  : m_Sbegin(S_begin), m_Scurrent(S_begin), m_Send(S_end),
121  m_U(U), m_Ubegin(m_U->begin()), m_Ucurrent(m_U->begin()), m_Uend(m_U->end()),
122  m_posS(0), m_posSlimit(0), m_posU(0), m_posUlimit(0), m_u_beta(0)
123 {
124  init();
125 }
126 
127 template <class PERM, class TRANS>
129  delete m_u_beta;
130 }
131 
132 template <class PERM, class TRANS>
133 void SchreierGenerator<PERM, TRANS>::init() {
134  m_beta = *m_Ucurrent;
135  delete m_u_beta;
136  m_u_beta = m_U->at(m_beta);
137 }
138 
139 
140 template <class PERM, class TRANS>
142  if (m_Send != m_Scurrent && m_Uend != m_Ucurrent && (!m_posUlimit || m_posU < m_posUlimit)) {
143  const PERM &x = **m_Scurrent;
144  if (m_U->trivialByDefinition(x, x / m_beta)) {
145  advance();
146  return hasNext();
147  }
148  return true;
149  }
150 
151  if (!m_stackTodo.empty()) {
152  boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> lastTuple = m_stackTodo.top();
153  m_stackTodo.pop();
154 
155  m_posS = boost::get<0>(lastTuple);
156  m_posSlimit = boost::get<1>(lastTuple);
157  m_posU = boost::get<2>(lastTuple);
158  m_posUlimit = boost::get<3>(lastTuple);
159  reset();
160 
161  return hasNext();
162  }
163  return false;
164 }
165 
166 template <class PERM, class TRANS>
168  ++m_Scurrent;
169  ++m_posS;
170  if (m_Scurrent == m_Send) {
171  m_Scurrent = boost::next(m_Sbegin, m_posSlimit);
172  m_posS = m_posSlimit;
173  ++m_Ucurrent;
174  ++m_posU;
175  if (m_Ucurrent != m_Uend)
176  init();
177  else
178  return false;
179  }
180  return true;
181 }
182 
183 template <class PERM, class TRANS>
185  BOOST_ASSERT(m_Scurrent != m_Send);
186  BOOST_ASSERT(m_Ucurrent != m_Uend);
187 
188  PERMLIB_DEBUG(std::cout << "s = " << m_posS << "; u = " << m_posU << std::endl;)
189  const PERM &x = **m_Scurrent;
190 
191  PERM g = *m_u_beta * x;
192  boost::scoped_ptr<PERM> u_beta_ptr2(m_U->at(x / m_beta));
193  u_beta_ptr2->invertInplace();
194  g *= *u_beta_ptr2;
195 
196  advance();
197 
198  return g;
199 }
200 
201 template <class PERM, class TRANS>
203  m_Scurrent = m_Sbegin;
204  m_Ucurrent = m_Ubegin;
205  int i = m_posS;
206  while (--i>=0) ++m_Scurrent;
207  i = m_posU;
208  while (--i>=0) ++m_Ucurrent;
209 
210  if (m_Ucurrent != m_Uend)
211  init();
212 }
213 
214 template <class PERM, class TRANS>
216  if (U == m_U && S_begin == m_Sbegin && S_end == m_Send)
217  return;
218  m_U = U;
219  m_Sbegin = S_begin;
220  m_Send = S_end;
221  m_Ubegin = U->begin();
222  m_Uend = U->end();
223  reset();
224 }
225 
226 template <class PERM, class TRANS>
228  m_stackTodo.push(boost::make_tuple(m_posS, m_posSlimit, m_posU, m_posUlimit));
229  m_posUlimit = m_posU;
230  m_posS = j;
231  m_posSlimit = j;
232  m_posU = 0;
233  reset();
234 }
235 
236 }
237 
238 #endif // -- SCHREIERGENERATOR_H_
SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end)
constructor
Definition: schreier_generator.h:119
interface for group element generators
Definition: generator.h:40
stateful generator of Schreier generators
Definition: schreier_generator.h:54
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
std::list< unsigned long >::const_iterator TRANSlistIt
const iterator to a list of points (unsigned long)
Definition: schreier_generator.h:59
PERM next()
generates an element
Definition: schreier_generator.h:184
Definition: abstract_bsgs.h:49
bool hasNext()
true, iff more elements can be generated
Definition: schreier_generator.h:141
std::list< typename PERM::ptr >::const_iterator PERMlistIt
const iterator to a list of PERMutations
Definition: schreier_generator.h:57