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 ORBIT_H_ 00034 #define ORBIT_H_ 00035 00036 #include <list> 00037 00038 #include <boost/foreach.hpp> 00039 00040 namespace permlib { 00041 00043 template<class PERM,class PDOMAIN> 00044 class Orbit { 00045 public: 00046 virtual ~Orbit() {} 00047 00049 virtual bool contains(const PDOMAIN& val) const = 0; 00050 00052 virtual const PDOMAIN& element() const = 0; 00053 00055 typedef PERM PERMtype; 00056 protected: 00058 00064 template<class Action> 00065 void orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList); 00066 00068 00077 template<class Action> 00078 void orbitUpdate(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList); 00079 00081 00084 virtual bool foundOrbitElement(const PDOMAIN& alpha, const PDOMAIN& alpha_p, const typename PERM::ptr& p) = 0; 00085 }; 00086 00087 template <class PERM,class PDOMAIN> 00088 template<class Action> 00089 inline void Orbit<PERM,PDOMAIN>::orbit(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, Action a, std::list<PDOMAIN>& orbitList) { 00090 if (orbitList.empty()) { 00091 orbitList.push_back(beta); 00092 foundOrbitElement(beta, beta, typename PERM::ptr()); 00093 } 00094 BOOST_ASSERT( orbitList.size() >= 1 ); 00095 00096 PERMLIB_DEBUG(std::cout << "orbit of " << beta << std::endl;) 00097 typename std::list<PDOMAIN>::const_iterator it; 00098 for (it = orbitList.begin(); it != orbitList.end(); ++it) { 00099 const PDOMAIN &alpha = *it; 00100 BOOST_FOREACH(const typename PERM::ptr& p, generators) { 00101 //std::cout << " " << orbitList.size() << std::endl; 00102 PDOMAIN alpha_p = a(*p, alpha); 00103 if (alpha_p != alpha && foundOrbitElement(alpha, alpha_p, p)) 00104 orbitList.push_back(alpha_p); 00105 } 00106 } 00107 //std::cout << "orb size " << orbitList.size() << std::endl; 00108 } 00109 00110 template <class PERM,class PDOMAIN> 00111 template<class Action> 00112 inline void Orbit<PERM,PDOMAIN>::orbitUpdate(const PDOMAIN& beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g, Action a, std::list<PDOMAIN>& orbitList) { 00113 if (orbitList.empty()) { 00114 orbitList.push_back(beta); 00115 foundOrbitElement(beta, beta, typename PERM::ptr()); 00116 } 00117 BOOST_ASSERT( orbitList.size() >= 1 ); 00118 00119 PERMLIB_DEBUG(std::cout << "orbiUpdate of " << beta << " and " << *g << std::endl;) 00120 const unsigned int oldSize = orbitList.size(); 00121 // first, compute only ORBIT^g 00122 typename std::list<PDOMAIN>::const_iterator it; 00123 for (it = orbitList.begin(); it != orbitList.end(); ++it) { 00124 const PDOMAIN &alpha = *it; 00125 PDOMAIN alpha_g = a(*g, alpha); 00126 if (alpha_g != alpha && foundOrbitElement(alpha, alpha_g, g)) 00127 orbitList.push_back(alpha_g); 00128 } 00129 00130 if (oldSize == orbitList.size()) 00131 return; 00132 00133 orbit(beta, generators, a, orbitList); 00134 } 00135 00136 } 00137 00138 #endif // -- ORBIT_H_