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 PERMUTATIONWORD_H_ 00034 #define PERMUTATIONWORD_H_ 00035 00036 #include <permlib/permutation.h> 00037 #include <vector> 00038 00039 #include <boost/shared_ptr.hpp> 00040 #include <boost/foreach.hpp> 00041 00042 namespace permlib { 00043 00044 typedef boost::shared_ptr<Permutation> PermutationPtr; 00045 00047 00050 class PermutationWord { 00051 public: 00053 typedef Permutation::perm perm; 00054 00056 typedef boost::shared_ptr<PermutationWord> ptr; 00057 00059 explicit PermutationWord(unsigned int n); 00061 PermutationWord(unsigned int n, const std::string &cycles); 00063 explicit PermutationWord(const perm &p); 00065 PermutationWord(const PermutationWord &p); 00066 00068 PermutationWord operator*(const PermutationWord &p) const; 00070 00073 PermutationWord& operator*=(const PermutationWord &p); 00075 00078 PermutationWord& operator^=(const PermutationWord &p); 00080 PermutationWord operator~() const; 00082 PermutationWord& invertInplace(); 00084 bool operator==(const PermutationWord &p2) const; 00085 00087 inline unsigned long operator/(unsigned long val) const { return at(val); } 00089 unsigned long at(unsigned long val) const; 00091 unsigned long operator%(unsigned long val) const; 00092 00094 friend std::ostream &operator<< (std::ostream &out, const PermutationWord &p); 00095 00097 00101 bool isIdentity(bool flush = false) const; 00102 00104 //TODO: it must be the other way round: isIdentity should call flush 00105 inline void flush() { isIdentity(true); } 00107 inline unsigned int size() const { return m_n; } 00108 00110 static unsigned long elementsNumber() { return ms_elements.size(); } 00111 00113 static void clearStorage(); 00114 private: 00115 static std::vector<PermutationPtr> ms_elements; 00116 static std::vector<PermutationPtr> ms_elementsInverse; 00117 static void addElement(const perm &p); 00118 static void addElement(const perm &p, const perm &pInv); 00119 static void addElement(PermutationPtr p); 00120 00121 mutable std::vector<int> m_word; 00122 unsigned int m_n; 00123 }; 00124 00125 std::vector<PermutationPtr> PermutationWord::ms_elements(1); 00126 std::vector<PermutationPtr> PermutationWord::ms_elementsInverse(1); 00127 00128 inline PermutationWord::PermutationWord(unsigned int n) 00129 : m_n(n) 00130 { } 00131 00132 inline PermutationWord::PermutationWord(unsigned int n, const std::string &cycles) 00133 : m_n(n) 00134 { 00135 Permutation *pp = new Permutation(n, cycles); 00136 ms_elements.push_back(PermutationPtr(pp)); 00137 ms_elementsInverse.push_back(PermutationPtr(new Permutation(~*pp))); 00138 m_word.reserve(2); 00139 m_word.push_back(ms_elements.size()-1); 00140 } 00141 00142 inline PermutationWord::PermutationWord(const PermutationWord &p) 00143 : m_word(p.m_word), m_n(p.m_n) 00144 { } 00145 00146 inline PermutationWord::PermutationWord(const perm &p) 00147 : m_n(p.size()) 00148 { 00149 addElement(p); 00150 m_word.reserve(2); 00151 m_word.push_back(ms_elements.size()-1); 00152 } 00153 00154 inline void PermutationWord::addElement(const perm &p) { 00155 PermutationPtr gen(new Permutation(p)); 00156 ms_elements.push_back(gen); 00157 PermutationPtr genInv(new Permutation(~*gen)); 00158 ms_elementsInverse.push_back(genInv); 00159 } 00160 inline void PermutationWord::addElement(PermutationPtr p) { 00161 ms_elements.push_back(p); 00162 PermutationPtr genInv(new Permutation(~*p)); 00163 ms_elementsInverse.push_back(genInv); 00164 } 00165 00166 inline void PermutationWord::addElement(const perm &p, const perm &pInv) { 00167 PermutationPtr gen(new Permutation(p)); 00168 ms_elements.push_back(gen); 00169 PermutationPtr genInv(new Permutation(pInv)); 00170 ms_elementsInverse.push_back(genInv); 00171 } 00172 00173 00174 inline PermutationWord PermutationWord::operator*(const PermutationWord &p) const { 00175 PermutationWord res(*this); 00176 res *= p; 00177 return res; 00178 } 00179 00180 inline PermutationWord& PermutationWord::operator*=(const PermutationWord &p) { 00181 if (m_word.empty()) { 00182 m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end()); 00183 return *this; 00184 } else if (p.m_word.empty()) 00185 return *this; 00186 00187 m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end()); 00188 return *this; 00189 } 00190 00191 inline PermutationWord& PermutationWord::operator^=(const PermutationWord &p) { 00192 if (m_word.empty()) { 00193 m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end()); 00194 return *this; 00195 } else if (p.m_word.empty()) 00196 return *this; 00197 00198 m_word.insert(m_word.begin(), p.m_word.begin(), p.m_word.end()); 00199 return *this; 00200 } 00201 00202 00203 inline PermutationWord& PermutationWord::invertInplace() { 00204 std::vector<int> oldWord(m_word); 00205 for (unsigned int i=0; i<oldWord.size(); ++i) { 00206 m_word[i] = -oldWord[oldWord.size() - 1 - i]; 00207 } 00208 return *this; 00209 } 00210 00211 inline PermutationWord PermutationWord::operator~() const { 00212 PermutationWord inv(*this); 00213 for (unsigned int i=0; i<m_word.size(); ++i) { 00214 inv.m_word[i] = -m_word[m_word.size() - 1 - i]; 00215 } 00216 return inv; 00217 } 00218 00219 inline unsigned long PermutationWord::at(unsigned long val) const { 00220 unsigned long ret = val; 00221 BOOST_FOREACH(int e, m_word) { 00222 if (e > 0) 00223 ret = *(ms_elements[e]) / ret; 00224 else 00225 ret = *(ms_elementsInverse[-e]) / ret; 00226 } 00227 return ret; 00228 } 00229 00230 inline unsigned long PermutationWord::operator%(unsigned long val) const { 00231 unsigned long ret = val; 00232 for (std::vector<int>::reverse_iterator lit = m_word.rbegin(); lit != m_word.rend(); ++lit) { 00233 int e = *lit; 00234 if (e < 0) 00235 ret = *(ms_elements[-e]) / ret; 00236 else 00237 ret = *(ms_elementsInverse[e]) / ret; 00238 } 00239 return ret; 00240 } 00241 00242 inline bool PermutationWord::isIdentity(bool flush_) const { 00243 if (m_word.empty()) { 00244 return true; 00245 } 00246 if (m_word.size() == 1) { 00247 if (flush_) 00248 return true; 00249 int e = m_word.front(); 00250 if (e>0) 00251 return ms_elements[e]->isIdentity(); 00252 else 00253 return ms_elementsInverse[-e]->isIdentity(); 00254 } 00255 00256 perm mult(m_n); 00257 perm multInv(m_n); 00258 00259 PermutationPtr resMult(new Permutation(m_n)); 00260 BOOST_FOREACH(int e, m_word) { 00261 *resMult *= (e > 0) 00262 ? *ms_elements[e].get() 00263 : *ms_elementsInverse[-e].get(); 00264 } 00265 00266 const bool permIsIdentity = resMult->isIdentity(); 00267 00268 if (!permIsIdentity) { 00269 addElement(resMult); 00270 m_word.clear(); 00271 m_word.reserve(2); 00272 m_word.push_back(ms_elements.size()-1); 00273 } 00274 00275 00276 return permIsIdentity; 00277 } 00278 00279 inline std::ostream &operator<< (std::ostream &out, const PermutationWord &p) { 00280 out << "W["; 00281 BOOST_FOREACH(int g, p.m_word) { 00282 out << g << ","; 00283 } 00284 out << "]"; 00285 return out; 00286 } 00287 00288 inline bool PermutationWord::operator==(const PermutationWord &p2) const { 00289 if (m_n != p2.m_n) 00290 return false; 00291 00292 //TODO: is this correct or do we need the old code (below) or keep references to all perm instances? 00293 //note: this is not correct: compare result of \inv{g} * g and g * \inv{g}, but this can be fixed by .... -x x ...... stripping when multiplying 00294 // in other cases it might have a good chance to work as intended 00295 // 00296 // NOTE: old code deleted from below during clean-up 00297 return m_word == p2.m_word; 00298 } 00299 00300 inline void PermutationWord::clearStorage() { 00301 ms_elements.clear(); 00302 ms_elements.resize(1); 00303 ms_elementsInverse.clear(); 00304 ms_elementsInverse.resize(1); 00305 } 00306 00307 } 00308 00309 #endif // -- PERMUTATIONWORD_H_