permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/permutation.h
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_