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