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 PERMUTATION_H_ 00034 #define PERMUTATION_H_ 00035 00036 #include <permlib/common.h> 00037 00038 // for I/O 00039 #include <string> 00040 #include <iostream> 00041 #include <boost/tokenizer.hpp> 00042 #include <sstream> 00043 #include <set> 00044 #include <list> 00045 #include <map> 00046 00047 #include <boost/shared_ptr.hpp> 00048 #include <boost/dynamic_bitset.hpp> 00049 #include <boost/foreach.hpp> 00050 #include <boost/cstdint.hpp> 00051 #include <boost/math/common_factor_rt.hpp> 00052 00053 namespace permlib { 00054 00055 namespace exports { struct BSGSSchreierExport; } 00056 00058 class Permutation { 00059 public: 00061 typedef std::vector<dom_int> perm; 00062 00064 typedef boost::shared_ptr<Permutation> ptr; 00065 00067 explicit Permutation(dom_int n); 00069 Permutation(dom_int n, const std::string &cycles); 00071 Permutation(dom_int n, const char* cycles); 00073 explicit Permutation(const perm &p); 00075 Permutation(const Permutation &p) : m_perm(p.m_perm), m_isIdentity(p.m_isIdentity) {}; 00077 template<class InputIterator> 00078 Permutation(InputIterator begin, InputIterator end) : m_perm(begin, end), m_isIdentity(false) {} 00079 00081 Permutation operator*(const Permutation &p) const; 00083 00086 Permutation& operator*=(const Permutation &p); 00088 00091 Permutation& operator^=(const Permutation &p); 00093 Permutation operator~() const; 00095 Permutation& invertInplace(); 00097 bool operator==(const Permutation &p2) const { return m_perm == p2.m_perm; }; 00098 00100 inline dom_int operator/(dom_int val) const { return at(val); } 00102 inline dom_int at(dom_int val) const { return m_perm[val]; } 00103 00105 dom_int operator%(dom_int val) const; 00106 00108 friend std::ostream &operator<< (std::ostream &out, const Permutation &p); 00109 00111 00114 bool isIdentity() const; 00116 inline void flush() {}; 00118 inline dom_int size() const { return m_perm.size(); } 00119 00121 00125 std::list<std::pair<dom_int, unsigned int> > cycles(bool includeTrivialCycles = false) const; 00126 00128 00131 boost::uint64_t order() const; 00132 00134 00141 template<typename ForwardIterator> 00142 Permutation* project(unsigned int n_proj, ForwardIterator begin, ForwardIterator end) const; 00143 00145 void setTransposition(dom_int pos, dom_int val); 00146 protected: 00148 perm m_perm; 00149 00151 bool m_isIdentity; 00152 00154 Permutation(dom_int n, bool) : m_perm(n), m_isIdentity(false) {} 00155 00157 void initFromCycleString(const std::string& cycles); 00158 00159 friend struct permlib::exports::BSGSSchreierExport; 00160 }; 00161 00162 00163 // 00164 // ---- IMPLEMENTATION 00165 // 00166 00167 inline Permutation::Permutation(dom_int n) 00168 : m_perm(n), m_isIdentity(true) 00169 { 00170 for (dom_int i=0; i<n; ++i) 00171 m_perm[i] = i; 00172 } 00173 00174 inline void Permutation::initFromCycleString(const std::string& cycleString) { 00175 typedef boost::tokenizer<boost::char_separator<char> > tokenizer; 00176 boost::char_separator<char> sepCycles(","); 00177 tokenizer tokens(cycleString, sepCycles); 00178 00179 for (dom_int i=0; i<m_perm.size(); ++i) 00180 m_perm[i] = i; 00181 00182 #ifdef PERMLIB_DEBUGMODE 00183 boost::dynamic_bitset<> seenIndices(m_perm.size()); 00184 #endif 00185 00186 for (tokenizer::iterator tok_iter = tokens.begin(); tok_iter != tokens.end(); ++tok_iter) { 00187 std::stringstream ss(*tok_iter); 00188 00189 unsigned int first, last, temp; 00190 ss >> first; 00191 last = first; 00192 #ifdef PERMLIB_DEBUGMODE 00193 BOOST_ASSERT( !seenIndices[first-1] ); 00194 seenIndices.set(first-1, 1); 00195 #endif 00196 00197 while (!ss.eof()) { 00198 ss >> temp; 00199 #ifdef PERMLIB_DEBUGMODE 00200 BOOST_ASSERT( !seenIndices[temp-1] ); 00201 seenIndices.set(temp-1, 1); 00202 #endif 00203 m_perm[last-1] = temp-1; 00204 last = temp; 00205 } 00206 m_perm[last-1] = first-1; 00207 } 00208 } 00209 00210 00211 inline Permutation::Permutation(dom_int n, const std::string & cycleString) 00212 : m_perm(n), m_isIdentity(false) 00213 { 00214 initFromCycleString(cycleString); 00215 } 00216 00217 inline Permutation::Permutation(dom_int n, const char* cycleString) 00218 : m_perm(n), m_isIdentity(false) 00219 { 00220 initFromCycleString(std::string(cycleString)); 00221 } 00222 00223 00224 inline Permutation::Permutation(const perm& p) 00225 : m_perm(p), m_isIdentity(false) 00226 { 00227 #ifdef PERMLIB_DEBUGMODE 00228 // check that m_perm really is a permutation 00229 std::set<dom_int> values; 00230 for (dom_int i=0; i<m_perm.size(); ++i) { 00231 const dom_int& v = m_perm[i]; 00232 BOOST_ASSERT( v < m_perm.size() ); 00233 values.insert(v); 00234 } 00235 BOOST_ASSERT( values.size() == m_perm.size() ); 00236 #endif 00237 } 00238 00239 inline Permutation Permutation::operator*(const Permutation &p) const { 00240 BOOST_ASSERT(p.m_perm.size() == m_perm.size()); 00241 00242 Permutation res(m_perm.size(), true); 00243 for (dom_int i=0; i<m_perm.size(); ++i) { 00244 res.m_perm[i] = p.m_perm[m_perm[i]]; 00245 } 00246 return res; 00247 } 00248 00249 inline Permutation& Permutation::operator*=(const Permutation &p) { 00250 BOOST_ASSERT(p.m_perm.size() == m_perm.size()); 00251 m_isIdentity = false; 00252 perm tmp(m_perm); 00253 00254 for (dom_int i=0; i<m_perm.size(); ++i) { 00255 tmp[i] = p.m_perm[m_perm[i]]; 00256 } 00257 m_perm = tmp; 00258 00259 return *this; 00260 } 00261 00262 inline Permutation& Permutation::operator^=(const Permutation &p) { 00263 BOOST_ASSERT(p.m_perm.size() == m_perm.size()); 00264 m_isIdentity = false; 00265 perm tmp(m_perm); 00266 00267 for (dom_int i=0; i<m_perm.size(); ++i) { 00268 m_perm[i] = tmp[p.m_perm[i]]; 00269 } 00270 return *this; 00271 } 00272 00273 inline Permutation Permutation::operator~() const { 00274 Permutation res(m_perm.size(), true); 00275 for (dom_int i=0; i<m_perm.size(); ++i) { 00276 res.m_perm[m_perm[i]] = i; 00277 } 00278 return res; 00279 } 00280 00281 inline Permutation& Permutation::invertInplace() { 00282 perm tmp(m_perm); 00283 for (dom_int i=0; i<m_perm.size(); ++i) { 00284 m_perm[tmp[i]] = i; 00285 } 00286 return *this; 00287 } 00288 00289 inline dom_int Permutation::operator%(dom_int val) const { 00290 for (dom_int i = 0; i < m_perm.size(); ++i) { 00291 if (m_perm[i] == val) 00292 return i; 00293 } 00294 // must not happen, we have a permutation! 00295 BOOST_ASSERT(false); 00296 return -1; 00297 } 00298 00299 inline bool Permutation::isIdentity() const { 00300 if (m_isIdentity) 00301 return true; 00302 for (dom_int i=0; i<m_perm.size(); ++i) 00303 if (at(i) != i) 00304 return false; 00305 return true; 00306 } 00307 00308 inline std::list<std::pair<dom_int, unsigned int> > Permutation::cycles(bool includeTrivialCycles) const { 00309 boost::dynamic_bitset<> worked(m_perm.size()); 00310 typedef std::pair<dom_int, unsigned int> CyclePair; 00311 std::list<CyclePair> cycleList; 00312 unsigned int cycleLength = 0; 00313 00314 for (dom_int x=0; x<m_perm.size(); ++x) { 00315 if (worked[x]) 00316 continue; 00317 00318 dom_int px, startX; 00319 worked.set(x, 1); 00320 startX = x; 00321 px = m_perm[x]; 00322 if (x == px) { 00323 if (includeTrivialCycles) 00324 cycleList.push_back(CyclePair(x, 1)); 00325 continue; 00326 } 00327 00328 cycleLength = 2; 00329 00330 while (m_perm[px] != startX) { 00331 worked.set(px, 1); 00332 px = m_perm[px]; 00333 ++cycleLength; 00334 } 00335 worked.set(px, 1); 00336 cycleList.push_back(CyclePair(startX, cycleLength)); 00337 } 00338 00339 return cycleList; 00340 } 00341 00342 inline boost::uint64_t Permutation::order() const { 00343 typedef std::pair<dom_int, unsigned int> CyclePair; 00344 std::list<CyclePair> cycleList = this->cycles(); 00345 boost::uint64_t ord = 1; 00346 BOOST_FOREACH(const CyclePair& cyc, cycleList) { 00347 ord = boost::math::lcm(ord, static_cast<boost::uint64_t>(cyc.second)); 00348 } 00349 return ord; 00350 } 00351 00352 template<typename ForwardIterator> 00353 Permutation* Permutation::project(unsigned int n_proj, ForwardIterator begin, ForwardIterator end) const { 00354 std::map<dom_int, dom_int> projectionMap; 00355 dom_int c = 0; 00356 for (ForwardIterator it = begin; it != end; ++it) { 00357 projectionMap[*it] = c++; 00358 } 00359 00360 Permutation* proj = new Permutation(n_proj); 00361 bool is_identity = true; 00362 00363 while (begin != end) { 00364 dom_int x = *begin++; 00365 BOOST_ASSERT( projectionMap.find(x) != projectionMap.end() ); 00366 BOOST_ASSERT( projectionMap.find(m_perm[x]) != projectionMap.end() ); 00367 const dom_int proj_x = projectionMap[x]; 00368 const dom_int proj_px = projectionMap[ m_perm[x] ]; 00369 BOOST_ASSERT( proj_x < n_proj ); 00370 BOOST_ASSERT( proj_px < n_proj ); 00371 proj->m_perm[ proj_x ] = proj_px; 00372 00373 if (proj_x != proj_px) 00374 is_identity = false; 00375 } 00376 00377 proj->m_isIdentity = is_identity; 00378 00379 return proj; 00380 } 00381 00382 inline void Permutation::setTransposition(dom_int pos, dom_int val) { 00383 BOOST_ASSERT(pos < m_perm.size()); 00384 BOOST_ASSERT(val < m_perm.size()); 00385 00386 m_perm[pos] = val; 00387 m_perm[val] = pos; 00388 } 00389 00390 inline std::ostream& operator<<(std::ostream& out, const Permutation& p) { 00391 typedef std::pair<dom_int, unsigned int> CyclePair; 00392 bool output = false; 00393 00394 std::list<CyclePair> cycleList = p.cycles(); 00395 BOOST_FOREACH(const CyclePair& c, cycleList) { 00396 dom_int px = p / c.first; 00397 out << "(" << (c.first + 1) << ","; 00398 while (px != c.first) { 00399 out << (px+1); 00400 px = p / px; 00401 if (px == c.first) 00402 out << ")"; 00403 else 00404 out << ","; 00405 } 00406 output = true; 00407 } 00408 00409 if (!output) 00410 out << "()"; 00411 00412 return out; 00413 } 00414 00415 } 00416 00417 #endif // -- PERMUTATION_H_