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 TRANSVERSAL_H_ 00034 #define TRANSVERSAL_H_ 00035 00036 #include <permlib/sorter/base_sorter.h> 00037 #include <permlib/transversal/orbit.h> 00038 00039 #include <map> 00040 #include <list> 00041 #include <vector> 00042 00043 #include <boost/foreach.hpp> 00044 #include <boost/shared_ptr.hpp> 00045 00046 namespace permlib { 00047 00048 template <class PERM> 00049 class Transversal; 00050 00051 template <class PERM> 00052 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) { 00053 out << "{"; 00054 BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) { 00055 if (p) 00056 out << *p << ", "; 00057 else 00058 out << "O, "; 00059 } 00060 out << "}"; 00061 return out; 00062 } 00063 00065 template <class PERM> 00066 class Transversal : public Orbit<PERM,unsigned long> { 00067 public: 00069 00072 Transversal(unsigned int n); 00074 virtual ~Transversal() {} 00075 00077 virtual PERM* at(unsigned long val) const = 0; 00078 00080 virtual bool trivialByDefinition(const PERM& x, unsigned long to) const = 0; 00081 00083 virtual bool contains(const unsigned long& val) const; 00084 00086 std::list<unsigned long>::const_iterator begin() const { return this->m_orbit.begin(); }; 00088 std::list<unsigned long>::const_iterator end() const { return this->m_orbit.end(); }; 00090 std::pair<std::list<unsigned long>::const_iterator,std::list<unsigned long>::const_iterator> pairIt() const { 00091 return std::make_pair(begin(), end()); 00092 } 00093 00095 unsigned int size() const { return this->m_orbit.size(); } 00096 00098 inline unsigned int n() const { return m_n; } 00099 00101 00105 template <class InputIterator> 00106 void sort(InputIterator Bbegin, InputIterator Bend); 00107 00109 inline bool sorted() const { return m_sorted; } 00110 00112 struct TrivialAction { 00114 unsigned long operator()(const PERM &p, unsigned long v) const { 00115 return p / v; 00116 } 00117 }; 00118 00120 00124 virtual void orbit(unsigned long alpha, const std::list<typename PERM::ptr> &generators); 00126 00131 virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g); 00132 00134 00138 virtual void permute(const PERM& g, const PERM& gInv); 00140 00143 virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {} 00144 00145 virtual const unsigned long& element() const; 00146 00148 friend std::ostream &operator<< <> (std::ostream &out, const Transversal<PERM> &p); 00149 protected: 00151 unsigned int m_n; 00152 00154 std::vector<boost::shared_ptr<PERM> > m_transversal; 00155 00157 std::list<unsigned long> m_orbit; 00158 00160 bool m_sorted; 00161 00163 virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p); 00164 00165 virtual bool foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p); 00166 }; 00167 00168 // 00169 // ---- IMPLEMENTATION 00170 // 00171 00172 template <class PERM> 00173 Transversal<PERM>::Transversal(unsigned int n_) 00174 : m_n(n_), m_transversal(n_), m_sorted(false) 00175 { } 00176 00177 template <class PERM> 00178 void Transversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) { 00179 Orbit<PERM,unsigned long>::orbit(beta, generators, TrivialAction(), m_orbit); 00180 } 00181 00182 template <class PERM> 00183 void Transversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) { 00184 Orbit<PERM,unsigned long>::orbitUpdate(beta, generators, g, TrivialAction(), m_orbit); 00185 } 00186 00187 template <class PERM> 00188 bool Transversal<PERM>::foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p) { 00189 BOOST_ASSERT( alpha_p < m_transversal.size() ); 00190 if (!m_transversal[alpha_p]) { 00191 if (!p) { 00192 typename PERM::ptr identity(new PERM(m_n)); 00193 registerMove(alpha, alpha_p, identity); 00194 } else { 00195 registerMove(alpha, alpha_p, p); 00196 } 00197 return true; 00198 } 00199 return false; 00200 } 00201 00202 template <class PERM> 00203 bool Transversal<PERM>::contains(const unsigned long& val) const { 00204 return m_transversal[val] != 0; 00205 } 00206 00207 template <class PERM> 00208 void Transversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) { 00209 m_sorted = false; 00210 } 00211 00212 00213 template <class PERM> 00214 template <class InputIterator> 00215 void Transversal<PERM>::sort(InputIterator Bbegin, InputIterator Bend) { 00216 this->m_orbit.sort(BaseSorter(m_n, Bbegin, Bend)); 00217 m_sorted = true; 00218 } 00219 00220 template <class PERM> 00221 void Transversal<PERM>::permute(const PERM& g, const PERM& gInv) { 00222 std::vector<boost::shared_ptr<PERM> > temp(m_n); 00223 for (unsigned long i=0; i<m_n; ++i) { 00224 const unsigned long j = g / i; 00225 temp[j] = m_transversal[i]; 00226 } 00227 std::copy(temp.begin(), temp.end(), m_transversal.begin()); 00228 BOOST_FOREACH(unsigned long& alpha, this->m_orbit) { 00229 alpha = g / alpha; 00230 } 00231 m_sorted = false; 00232 } 00233 00234 template <class PERM> 00235 inline const unsigned long& Transversal<PERM>::element() const { 00236 return m_orbit.front(); 00237 } 00238 00239 } 00240 00241 #endif // -- TRANSVERSAL_H_