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 PRIMITIVITY_SGS_TEST_H_ 00034 #define PRIMITIVITY_SGS_TEST_H_ 00035 00036 #include <permlib/transversal/orbit_set.h> 00037 #include <permlib/transversal/transversal.h> 00038 00039 #include <boost/foreach.hpp> 00040 #include <boost/scoped_ptr.hpp> 00041 #include <boost/utility.hpp> 00042 #include <vector> 00043 #include <list> 00044 00045 namespace permlib { 00046 00048 00054 template<typename TRANS> 00055 class PrimitivitySGSTest { 00056 private: 00057 typedef typename TRANS::PERMtype PERM; 00058 public: 00069 template<typename InputIterator> 00070 PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U); 00071 00077 bool blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const; 00078 00082 bool isPrimitive() const { return blockOfImprimitivity(NULL); } 00083 00084 private: 00085 const TRANS& m_U; 00086 const dom_int m_alpha; 00087 const std::list<typename PERM::ptr> m_generators; 00088 const std::list<typename PERM::ptr> m_generatorsStab; 00089 }; 00090 00091 00092 00093 template<typename TRANS> 00094 template<typename InputIterator> 00095 PrimitivitySGSTest<TRANS>::PrimitivitySGSTest(InputIterator genBegin, InputIterator genEnd, dom_int alpha, InputIterator genStabBegin, InputIterator genStabEnd, const TRANS& U) 00096 : m_U(U), m_alpha(alpha), m_generators(genBegin, genEnd), m_generatorsStab(genStabBegin, genStabEnd) 00097 {} 00098 00099 00100 template<typename TRANS> 00101 bool PrimitivitySGSTest<TRANS>::blockOfImprimitivity(std::vector<dom_int>* minimalBlock) const { 00102 const unsigned int n = m_U.n(); 00103 std::vector<dom_int> AllLambdas(n); 00104 std::vector<dom_int> LambdaReverse(n, n); 00105 unsigned int LambdaLastIndex = 0; 00106 std::list<unsigned int> LambdaBegin; 00107 std::list<unsigned int> LambdaSize; 00108 00109 dom_int omega; 00110 for (omega = 0; omega < n; ++omega) 00111 if (m_alpha != omega) 00112 break; 00113 00114 BOOST_ASSERT( omega < n ); 00115 00116 OrbitSet<PERM, dom_int> omegaOrbit; 00117 omegaOrbit.orbit(omega, m_generatorsStab, typename Transversal<PERM>::TrivialAction()); 00118 for (typename OrbitSet<PERM, dom_int>::const_iterator oit = omegaOrbit.begin(); oit != omegaOrbit.end(); ++oit) { 00119 AllLambdas[LambdaLastIndex++] = *oit; 00120 LambdaReverse[*oit] = 0; 00121 } 00122 LambdaBegin.push_back(0); 00123 LambdaSize.push_back(omegaOrbit.size()); 00124 00125 while (true) { 00126 const dom_int lambda = AllLambdas[LambdaBegin.back()]; 00127 std::vector<dom_int>::const_iterator LambdaItBegin = AllLambdas.begin() + LambdaBegin.back(); 00128 std::vector<dom_int>::const_iterator LambdaItEnd = LambdaItBegin + LambdaSize.back(); 00129 bool needAnotherIteration = false; 00130 00131 PERMLIB_DEBUG( std::cout << "lambda = " << lambda << std::endl; ) 00132 00133 for (std::vector<dom_int>::const_iterator lit = LambdaItBegin; lit != LambdaItEnd; ++lit) { 00134 boost::scoped_ptr<PERM> u_lambda(m_U.at(lambda)); 00135 BOOST_ASSERT( u_lambda ); 00136 00137 const dom_int gamma = *lit; 00138 const dom_int mu = *u_lambda / gamma; 00139 00140 PERMLIB_DEBUG( std::cout << " u_lambda = " << *u_lambda << ", gamma = " << gamma << ", mu = " << mu << std::endl; ) 00141 00142 const unsigned int muIndex = LambdaReverse[mu]; 00143 if (mu != m_alpha && muIndex == n) { 00144 PERMLIB_DEBUG( std::cout << " add orbit of mu = " << mu << " at " << LambdaBegin.size() << std::endl; ) 00145 OrbitSet<PERM, dom_int> muOrbit; 00146 muOrbit.orbit(mu, m_generatorsStab, typename Transversal<PERM>::TrivialAction()); 00147 LambdaBegin.push_back(LambdaLastIndex); 00148 LambdaSize.push_back(muOrbit.size()); 00149 for (typename OrbitSet<PERM, dom_int>::const_iterator oit = muOrbit.begin(); oit != muOrbit.end(); ++oit) { 00150 AllLambdas[LambdaLastIndex++] = *oit; 00151 LambdaReverse[*oit] = LambdaBegin.size() - 1; 00152 } 00153 needAnotherIteration = true; 00154 break; 00155 } else if (muIndex < LambdaBegin.size() - 1) { 00156 std::list<unsigned int>::const_reverse_iterator sizeIt = LambdaSize.rbegin(); 00157 std::list<unsigned int>::const_reverse_iterator reprIt = LambdaBegin.rbegin(); 00158 unsigned int largestReprIndex = n; 00159 unsigned int largestLambdaSize = 0; 00160 for (dom_int i = muIndex; i < LambdaBegin.size(); ++i) { 00161 if (*sizeIt > largestLambdaSize) { 00162 largestLambdaSize = *sizeIt; 00163 largestReprIndex = *reprIt; 00164 } 00165 ++sizeIt; 00166 ++reprIt; 00167 } 00168 PERMLIB_DEBUG( std::cout << " merge sets from i = " << muIndex << " with representative " << AllLambdas[largestReprIndex] << std::endl; ) 00169 00170 std::swap(AllLambdas[*boost::next(LambdaBegin.begin(), muIndex)], AllLambdas[largestReprIndex]); 00171 for (dom_int i = LambdaBegin.size() - 1; i > muIndex ; --i) { 00172 const unsigned int oldSize = LambdaSize.back(); 00173 LambdaSize.pop_back(); 00174 LambdaBegin.pop_back(); 00175 LambdaSize.back() += oldSize; 00176 } 00177 for (unsigned int i = 0; i < n; ++i) 00178 if (LambdaReverse[i] > muIndex && LambdaReverse[i] < n) 00179 LambdaReverse[i] = muIndex; 00180 00181 PERMLIB_DEBUG( std::cout << " now there are " << LambdaBegin.size() << " sets left" << std::endl; ) 00182 needAnotherIteration = true; 00183 break; 00184 } 00185 } 00186 00187 BOOST_ASSERT( LambdaBegin.size() == LambdaSize.size() ); 00188 00189 if (!needAnotherIteration) 00190 break; 00191 } 00192 00193 if (minimalBlock) { 00194 minimalBlock->clear(); 00195 minimalBlock->resize(LambdaSize.back() + 1); 00196 minimalBlock->at(0) = m_alpha; 00197 for (unsigned int i = 1; i < minimalBlock->size(); ++i) 00198 minimalBlock->at(i) = AllLambdas[LambdaBegin.back() + i - 1]; 00199 } 00200 00201 return LambdaSize.back() == m_U.size() - 1; 00202 } 00203 00204 } 00205 00206 #endif