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 SCHREIERSIMSCONSTRUCTION_H_ 00034 #define SCHREIERSIMSCONSTRUCTION_H_ 00035 00036 #include <permlib/construct/base_construction.h> 00037 #include <permlib/bsgs.h> 00038 #include <permlib/generator/schreier_generator.h> 00039 00040 #include <boost/foreach.hpp> 00041 00042 namespace permlib { 00043 00045 template <class PERM, class TRANS> 00046 class SchreierSimsConstruction : public BaseConstruction<PERM, TRANS> { 00047 public: 00049 00052 explicit SchreierSimsConstruction(unsigned int n); 00053 00055 00057 template <class ForwardIterator> 00058 BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const; 00059 00061 00067 template <class ForwardIterator, class InputIterator> 00068 BSGS<PERM, TRANS> construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const; 00069 00071 mutable unsigned int m_statScheierGeneratorsConsidered; 00072 }; 00073 00074 // 00075 // ---- IMPLEMENTATION 00076 // 00077 00078 template <class PERM, class TRANS> 00079 SchreierSimsConstruction<PERM,TRANS>::SchreierSimsConstruction(unsigned int n) 00080 : BaseConstruction<PERM, TRANS>(n), m_statScheierGeneratorsConsidered(0) 00081 { } 00082 00083 template <class PERM, class TRANS> 00084 template <class ForwardIterator> 00085 inline BSGS<PERM, TRANS> SchreierSimsConstruction<PERM,TRANS>::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const { 00086 return construct(generatorsBegin, generatorsEnd, BaseConstruction<PERM,TRANS>::empty, BaseConstruction<PERM,TRANS>::empty); 00087 } 00088 00089 template <class PERM, class TRANS> 00090 template <class ForwardIterator, class InputIterator> 00091 BSGS<PERM, TRANS> SchreierSimsConstruction<PERM, TRANS> 00092 ::construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd, InputIterator prescribedBaseBegin, InputIterator prescribedBaseEnd) const 00093 { 00094 const dom_int &n = this->m_n; 00095 BSGS<PERM, TRANS> ret(n); 00096 std::vector<dom_int> &B = ret.B; 00097 std::vector<TRANS> &U = ret.U; 00098 std::vector<std::list<typename PERM::ptr> > S; 00099 this->setup(generatorsBegin, generatorsEnd, prescribedBaseBegin, prescribedBaseEnd, ret, S); 00100 00101 std::vector<boost::shared_ptr<SchreierGenerator<PERM, TRANS> > > SchreierGens; 00102 for (unsigned int i = 0; i < B.size(); ++i) { 00103 BOOST_ASSERT( i < U.size() ); 00104 BOOST_ASSERT( i < S.size() ); 00105 SchreierGens.push_back(boost::shared_ptr<SchreierGenerator<PERM, TRANS> >(new SchreierGenerator<PERM, TRANS>(&U[i], S[i].begin(), S[i].end()))); 00106 } 00107 00108 unsigned int j = B.size(); 00109 bool breakUp = false; 00110 while (j >= 1) { 00111 breakUp = false; 00112 SchreierGenerator<PERM, TRANS> &sg = *SchreierGens[j-1]; 00113 sg.update(&U[j-1], S[j-1].begin(), S[j-1].end()); 00114 00115 while (sg.hasNext()) { 00116 ++m_statScheierGeneratorsConsidered; 00117 PERMLIB_DEBUG(for(unsigned int jjj=0; jjj<j; ++jjj) std::cout << " ";) 00118 PERMLIB_DEBUG(std::cout << "schreier j = " << (j-1) << " [" << S[j-1].size() << "," << U[j-1].size() << "]: ";) 00119 PERM g = sg.next(); 00120 PERM h(n); 00121 // sift for S_{j+1}, so use index j here 00122 unsigned int k = ret.sift(g, h, j); 00123 if (k < B.size() - j || !h.isIdentity()) { 00124 // flush it, because we add it as a generator 00125 h.flush(); 00126 00127 if (j == B.size()) { 00128 dom_int gamma = n+1; 00129 if (ret.chooseBaseElement(h, gamma)) { 00130 B.push_back(gamma); 00131 } 00132 BOOST_ASSERT(j < B.size()); 00133 S.push_back(std::list<typename PERM::ptr>()); 00134 U.push_back(TRANS(n)); 00135 } 00136 boost::shared_ptr<PERM> hPtr(new PERM(h)); 00137 S[j].insert(S[j].end(), hPtr); 00138 00139 ret.orbitUpdate(j, S[j], hPtr); 00140 if (j >= SchreierGens.size()) { 00141 boost::shared_ptr<SchreierGenerator<PERM, TRANS> > localVar(new SchreierGenerator<PERM, TRANS>(&U[j], S[j].begin(), S[j].end())); 00142 SchreierGens.push_back(localVar); 00143 } else { 00144 SchreierGens[j]->update(S[j].size() - 1); 00145 } 00146 00147 breakUp = true; 00148 ++j; 00149 break; 00150 } 00151 } 00152 if (!breakUp) 00153 --j; 00154 } 00155 00156 this->mergeGenerators(S, ret); 00157 00158 return ret; 00159 } 00160 00161 } 00162 00163 #endif // -- SCHREIERSIMSCONSTRUCTION_H_