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 SCHREIERTRANSVERSAL_H_ 00034 #define SCHREIERTRANSVERSAL_H_ 00035 00036 #include <permlib/transversal/transversal.h> 00037 00038 namespace permlib { 00039 00040 namespace exports { struct BSGSSchreierExport; struct BSGSSchreierImport; } 00041 00043 template <class PERM> 00044 class SchreierTreeTransversal : public Transversal<PERM> { 00045 public: 00047 SchreierTreeTransversal(unsigned int n); 00048 00049 virtual bool trivialByDefinition(const PERM& x, unsigned long to) const; 00050 virtual PERM* at(unsigned long val) const; 00051 00052 virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange); 00053 00055 00059 SchreierTreeTransversal<PERM> clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const; 00060 00062 mutable unsigned int m_statMaxDepth; 00063 protected: 00064 virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p); 00065 00066 friend struct permlib::exports::BSGSSchreierExport; 00067 friend struct permlib::exports::BSGSSchreierImport; 00068 }; 00069 00070 // 00071 // ---- IMPLEMENTATION 00072 // 00073 00074 template <class PERM> 00075 SchreierTreeTransversal<PERM>::SchreierTreeTransversal(unsigned int n_) 00076 : Transversal<PERM>(n_), m_statMaxDepth(0) 00077 { } 00078 00079 template <class PERM> 00080 bool SchreierTreeTransversal<PERM>::trivialByDefinition(const PERM& x, unsigned long to) const { 00081 return *Transversal<PERM>::m_transversal[to] == x; 00082 } 00083 00084 template <class PERM> 00085 void SchreierTreeTransversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) { 00086 Transversal<PERM>::registerMove(from, to, p); 00087 Transversal<PERM>::m_transversal[to] = p; 00088 } 00089 00090 00091 template <class PERM> 00092 PERM* SchreierTreeTransversal<PERM>::at(unsigned long val) const { 00093 const std::vector<boost::shared_ptr<PERM> > &transversal = Transversal<PERM>::m_transversal; 00094 00095 if (transversal[val] == 0) { 00096 return 0; 00097 } 00098 00099 unsigned int depth = 1; 00100 PERM *res = new PERM(*transversal[val]); 00101 const PERM* inv = 0; 00102 //std::cout << "Schreier " << *res << std::endl; 00103 unsigned long pred = *res % val; 00104 //TODO: reserve space for PermutationWord-res beforehand (we know how long the m_word vector will be) 00105 while (pred != val) { 00106 inv = transversal[pred].get(); 00107 BOOST_ASSERT(inv); 00108 PERMLIB_DEBUG(std::cout << "Schreier2 " << inv << " / " << val << " , " << pred << std::endl;) 00109 *res ^= *inv; 00110 val = pred; 00111 pred = *inv % pred; 00112 ++depth; 00113 } 00114 m_statMaxDepth = std::max(m_statMaxDepth, depth); 00115 //std::cout << "Schreier3 " << *res << std::endl; 00116 return res; 00117 } 00118 00119 template <class PERM> 00120 void SchreierTreeTransversal<PERM>::updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) { 00121 unsigned int missedCount = 0; 00122 BOOST_FOREACH(typename PERM::ptr& p, this->m_transversal) { 00123 if (!p) 00124 continue; 00125 //std::cout << "require " << p.get() << std::endl; 00126 typename std::map<PERM*,typename PERM::ptr>::const_iterator pIt = generatorChange.find(p.get()); 00127 //BOOST_ASSERT( pIt != generatorChange.end() ); 00128 if (pIt != generatorChange.end()) { 00129 p = (*pIt).second; 00130 } else { 00131 ++missedCount; 00132 //std::cout << "missed " << p.get() << " = " << *p << std::endl; 00133 } 00134 } 00135 // we always miss the identity -- and not anything else 00136 BOOST_ASSERT( missedCount == 1 ); 00137 } 00138 00139 template <class PERM> 00140 SchreierTreeTransversal<PERM> SchreierTreeTransversal<PERM>::clone(const std::map<PERM*,typename PERM::ptr>& generatorChange) const { 00141 SchreierTreeTransversal<PERM> ret(*this); 00142 ret.updateGenerators(generatorChange); 00143 return ret; 00144 } 00145 00146 } 00147 00148 #endif // -- SCHREIERTRANSVERSAL_H_