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 BASETRANSPOSE_H_ 00034 #define BASETRANSPOSE_H_ 00035 00036 #include <permlib/predicate/pointwise_stabilizer_predicate.h> 00037 #include <permlib/generator/generator.h> 00038 00039 #include <boost/scoped_ptr.hpp> 00040 #include <boost/iterator/indirect_iterator.hpp> 00041 00042 namespace permlib { 00043 00045 00048 template<class PERM, class TRANS> 00049 class BaseTranspose { 00050 public: 00052 BaseTranspose(); 00054 virtual ~BaseTranspose() {} 00055 00057 00061 void transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const; 00062 00064 mutable unsigned int m_statScheierGeneratorsConsidered; 00066 mutable unsigned int m_statNewGenerators; 00067 protected: 00068 typedef std::list<typename PERM::ptr> PERMlist; 00069 00071 00077 virtual Generator<PERM>* setupGenerator(BSGS<PERM,TRANS> &bsgs, unsigned int i, const PERMlist &S_i, const TRANS &U_i) const = 0; 00078 }; 00079 00080 // 00081 // ---- IMPLEMENTATION 00082 // 00083 00084 template<class PERM, class TRANS> 00085 BaseTranspose<PERM,TRANS>::BaseTranspose() 00086 : m_statScheierGeneratorsConsidered(0), m_statNewGenerators(0) 00087 { } 00088 00089 template<class PERM, class TRANS> 00090 void BaseTranspose<PERM,TRANS>::transpose(BSGS<PERM,TRANS> &bsgs, unsigned int i) const { 00091 std::vector<dom_int> &B = bsgs.B; 00092 std::vector<TRANS> &U = bsgs.U; 00093 00094 if (i+1 >= B.size()) 00095 // illegal transpose index 00096 return; 00097 00098 PERMlist S_i; 00099 std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + i)); 00100 00101 std::swap(B[i], B[i+1]); 00102 00103 PERMlist S_i1; 00104 std::copy_if(bsgs.S.begin(), bsgs.S.end(), std::back_inserter(S_i1), PointwiseStabilizerPredicate<PERM>(B.begin(), B.begin() + (i+1))); 00105 00106 unsigned int targetTransversalSize = U[i+1].size() * U[i].size(); 00107 00108 // new transversal 00109 TRANS U_i(U[i].n()); 00110 U_i.orbit(B[i], S_i); 00111 targetTransversalSize /= U_i.size(); 00112 00113 m_statScheierGeneratorsConsidered = 0; 00114 m_statNewGenerators = 0; 00115 TRANS U_i1(U[i+1].n()); 00116 U_i1.orbit(B[i+1], S_i1); 00117 boost::scoped_ptr<Generator<PERM> > generator(setupGenerator(bsgs, i, S_i, U_i)); 00118 BOOST_ASSERT(generator != 0); 00119 00120 while (U_i1.size() < targetTransversalSize) { 00121 bool newGeneratorFound = false; 00122 while (generator->hasNext()) { 00123 PERM g = generator->next(); 00124 ++m_statScheierGeneratorsConsidered; 00125 boost::indirect_iterator<typename PERMlist::iterator> sBegin(S_i1.begin()), sEnd(S_i1.end()); 00126 if (!U_i1.contains(g / B[i+1]) && std::find(sBegin, sEnd, g) == sEnd) { 00127 g.flush(); 00128 boost::shared_ptr<PERM> gen(new PERM(g)); 00129 S_i1.push_front(gen); 00130 ++m_statNewGenerators; 00131 U_i1.orbitUpdate(B[i+1], S_i1, gen); 00132 newGeneratorFound = true; 00133 break; 00134 } 00135 } 00136 if (!newGeneratorFound) 00137 // we have exhausted all available generators, and we won't find any new ones in the loop 00138 break; 00139 } 00140 BOOST_ASSERT(U_i1.size() >= targetTransversalSize); 00141 00142 bsgs.S.insert(bsgs.S.end(), S_i1.begin(), boost::next(S_i1.begin(), m_statNewGenerators)); 00143 U[i] = U_i; 00144 U[i+1] = U_i1; 00145 } 00146 00147 } 00148 00149 #endif // -- BASETRANSPOSE_H_