permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef SCHREIERGENERATOR_H_ 00034 #define SCHREIERGENERATOR_H_ 00035 00036 #include <permlib/common.h> 00037 #include <permlib/generator/generator.h> 00038 00039 #include <stack> 00040 #include <boost/scoped_ptr.hpp> 00041 #include <boost/tuple/tuple.hpp> 00042 00043 namespace permlib { 00044 00046 00053 template <class PERM, class TRANS> 00054 class SchreierGenerator : public Generator<PERM> { 00055 public: 00057 typedef typename std::list<typename PERM::ptr>::const_iterator PERMlistIt; 00059 typedef typename std::list<unsigned long>::const_iterator TRANSlistIt; 00060 00062 00067 SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end); 00068 virtual ~SchreierGenerator(); 00069 00070 PERM next(); 00071 bool hasNext(); 00072 00074 00079 void update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end); 00080 00082 00087 void update(unsigned int j); 00088 private: 00089 PERMlistIt m_Sbegin; 00090 PERMlistIt m_Scurrent; 00091 PERMlistIt m_Send; 00092 const TRANS *m_U; 00093 TRANSlistIt m_Ubegin; 00094 TRANSlistIt m_Ucurrent; 00095 TRANSlistIt m_Uend; 00096 unsigned int m_posS; 00097 unsigned int m_posSlimit; 00098 unsigned int m_posU; 00099 unsigned int m_posUlimit; 00100 00101 PERM* m_u_beta; 00102 unsigned long m_beta; 00103 00104 std::stack<boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> > m_stackTodo; 00105 00107 bool advance(); 00109 void init(); 00111 void reset(); 00112 }; 00113 00114 // 00115 // ---- IMPLEMENTATION 00116 // 00117 00118 template <class PERM, class TRANS> 00119 SchreierGenerator<PERM, TRANS>::SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end) 00120 : m_Sbegin(S_begin), m_Scurrent(S_begin), m_Send(S_end), 00121 m_U(U), m_Ubegin(m_U->begin()), m_Ucurrent(m_U->begin()), m_Uend(m_U->end()), 00122 m_posS(0), m_posSlimit(0), m_posU(0), m_posUlimit(0), m_u_beta(0) 00123 { 00124 init(); 00125 } 00126 00127 template <class PERM, class TRANS> 00128 SchreierGenerator<PERM, TRANS>::~SchreierGenerator() { 00129 delete m_u_beta; 00130 } 00131 00132 template <class PERM, class TRANS> 00133 void SchreierGenerator<PERM, TRANS>::init() { 00134 m_beta = *m_Ucurrent; 00135 delete m_u_beta; 00136 m_u_beta = m_U->at(m_beta); 00137 } 00138 00139 00140 template <class PERM, class TRANS> 00141 bool SchreierGenerator<PERM, TRANS>::hasNext() { 00142 if (m_Send != m_Scurrent && m_Uend != m_Ucurrent && (!m_posUlimit || m_posU < m_posUlimit)) { 00143 const PERM &x = **m_Scurrent; 00144 if (m_U->trivialByDefinition(x, x / m_beta)) { 00145 advance(); 00146 return hasNext(); 00147 } 00148 return true; 00149 } 00150 00151 if (!m_stackTodo.empty()) { 00152 boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> lastTuple = m_stackTodo.top(); 00153 m_stackTodo.pop(); 00154 00155 m_posS = boost::get<0>(lastTuple); 00156 m_posSlimit = boost::get<1>(lastTuple); 00157 m_posU = boost::get<2>(lastTuple); 00158 m_posUlimit = boost::get<3>(lastTuple); 00159 reset(); 00160 00161 return hasNext(); 00162 } 00163 return false; 00164 } 00165 00166 template <class PERM, class TRANS> 00167 bool SchreierGenerator<PERM, TRANS>::advance() { 00168 ++m_Scurrent; 00169 ++m_posS; 00170 if (m_Scurrent == m_Send) { 00171 m_Scurrent = boost::next(m_Sbegin, m_posSlimit); 00172 m_posS = m_posSlimit; 00173 ++m_Ucurrent; 00174 ++m_posU; 00175 if (m_Ucurrent != m_Uend) 00176 init(); 00177 else 00178 return false; 00179 } 00180 return true; 00181 } 00182 00183 template <class PERM, class TRANS> 00184 PERM SchreierGenerator<PERM, TRANS>::next() { 00185 BOOST_ASSERT(m_Scurrent != m_Send); 00186 BOOST_ASSERT(m_Ucurrent != m_Uend); 00187 00188 PERMLIB_DEBUG(std::cout << "s = " << m_posS << "; u = " << m_posU << std::endl;) 00189 const PERM &x = **m_Scurrent; 00190 00191 PERM g = *m_u_beta * x; 00192 boost::scoped_ptr<PERM> u_beta_ptr2(m_U->at(x / m_beta)); 00193 u_beta_ptr2->invertInplace(); 00194 g *= *u_beta_ptr2; 00195 00196 advance(); 00197 00198 return g; 00199 } 00200 00201 template <class PERM, class TRANS> 00202 void SchreierGenerator<PERM, TRANS>::reset() { 00203 m_Scurrent = m_Sbegin; 00204 m_Ucurrent = m_Ubegin; 00205 int i = m_posS; 00206 while (--i>=0) ++m_Scurrent; 00207 i = m_posU; 00208 while (--i>=0) ++m_Ucurrent; 00209 00210 if (m_Ucurrent != m_Uend) 00211 init(); 00212 } 00213 00214 template <class PERM, class TRANS> 00215 void SchreierGenerator<PERM, TRANS>:: update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end) { 00216 if (U == m_U && S_begin == m_Sbegin && S_end == m_Send) 00217 return; 00218 m_U = U; 00219 m_Sbegin = S_begin; 00220 m_Send = S_end; 00221 m_Ubegin = U->begin(); 00222 m_Uend = U->end(); 00223 reset(); 00224 } 00225 00226 template <class PERM, class TRANS> 00227 void SchreierGenerator<PERM, TRANS>:: update(unsigned int j) { 00228 m_stackTodo.push(boost::make_tuple(m_posS, m_posSlimit, m_posU, m_posUlimit)); 00229 m_posUlimit = m_posU; 00230 m_posS = j; 00231 m_posSlimit = j; 00232 m_posU = 0; 00233 reset(); 00234 } 00235 00236 } 00237 00238 #endif // -- SCHREIERGENERATOR_H_