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 #ifndef TYPE_RECOGNITION_H_ 00033 #define TYPE_RECOGNITION_H_ 00034 00035 #include <permlib/prime_helper.h> 00036 #include <permlib/transversal/schreier_tree_transversal.h> 00037 #include <permlib/generator/bsgs_generator.h> 00038 #include <permlib/construct/schreier_sims_construction.h> 00039 #include <permlib/transversal/orbit_set.h> 00040 #include <permlib/test/giant_test.h> 00041 #include <permlib/test/group_type.h> 00042 #include <permlib/test/primitivity_sgs_test.h> 00043 00044 #include <iostream> 00045 00046 00047 namespace permlib { 00048 00050 00054 template<class PERM, class TRANSVERSAL = SchreierTreeTransversal<PERM> > 00055 class TypeRecognition { 00056 public: 00058 typedef boost::shared_ptr<BSGS<PERM, TRANSVERSAL> > PermutationGroupPtr; 00059 00065 template<class InputIterator> 00066 TypeRecognition(unsigned int n, InputIterator genBegin, InputIterator genEnd); 00067 00071 TypeRecognition(const PermutationGroupPtr& bsgs); 00072 00074 GroupType* analyze() { return analyze(true); } 00076 PermutationGroupPtr bsgs() const { return m_bsgs; } 00077 private: 00078 const unsigned int m_n; 00079 std::list<typename PERM::ptr> m_generators; 00080 const PermutationGroupPtr m_externalBSGS; 00081 PermutationGroupPtr m_bsgs; 00082 00086 GroupType* analyze(bool allowRecursiveCalls); 00087 00089 00092 GroupType* checkOrbitActions(); 00093 00095 static const unsigned int m_bsgsComputationDegreeLimit = 50; 00096 }; 00097 00098 template<class PERM, class TRANSVERSAL> 00099 template<class InputIterator> 00100 TypeRecognition<PERM,TRANSVERSAL>::TypeRecognition(unsigned int n, InputIterator genBegin, InputIterator genEnd) 00101 : m_n(n), m_generators(genBegin, genEnd) 00102 { } 00103 00104 template<class PERM, class TRANSVERSAL> 00105 TypeRecognition<PERM,TRANSVERSAL>::TypeRecognition(const PermutationGroupPtr& bsgs_) 00106 : m_n(bsgs_->n), m_generators(bsgs_->S.begin(), bsgs_->S.end()), m_externalBSGS(bsgs_), m_bsgs(m_externalBSGS) 00107 { } 00108 00109 00110 template<class PERM, class TRANSVERSAL> 00111 GroupType* TypeRecognition<PERM,TRANSVERSAL>::analyze(bool allowRecursiveCalls) { 00112 if (m_n < m_bsgsComputationDegreeLimit && ! m_bsgs) { 00113 SchreierSimsConstruction<PERM,TRANSVERSAL> ssc(m_n); 00114 m_bsgs = PermutationGroupPtr(new BSGS<PERM, TRANSVERSAL>(ssc.construct(m_generators.begin(), m_generators.end()))); 00115 } 00116 00117 // error probability for randomized algorithms 00118 const double eps = 1e-3; 00119 00120 if (m_bsgs) { 00121 const unsigned int groupIntOrder = m_bsgs->template order<unsigned int>(); 00122 00123 if (groupIntOrder == 1) 00124 return new TrivialGroupType(m_n); 00125 00126 if (groupIntOrder == 2) 00127 return new SymmetricGroupType(groupIntOrder, m_n); 00128 00129 // 00130 // check for cyclic groups 00131 // 00132 if (PrimeHelper::isPrimeNumber(groupIntOrder, false)) { 00133 BOOST_ASSERT( m_n % groupIntOrder == 0 ); 00134 return new CyclicGroupType(groupIntOrder, m_n); 00135 } 00136 00137 if (groupIntOrder == 4) { 00138 // distinguish between C_4 and the Klein four group 00139 BSGSGenerator<TRANSVERSAL> bsgsGen(m_bsgs->U); 00140 while (bsgsGen.hasNext()) { 00141 PERM el = bsgsGen.next(); 00142 if (el.order() == 4) 00143 return new CyclicGroupType(4, m_n); 00144 } 00145 return new DirectProductGroupType(new SymmetricGroupType(2,2), new SymmetricGroupType(2,2), m_n); 00146 } 00147 00148 // 00149 // check for symmetric groups, natural action 00150 // 00151 unsigned int symmetricGroupCandidateDegree = 0; 00152 00153 std::vector<unsigned int> transversalSizes(m_bsgs->U.size()); 00154 for (unsigned int i = 0; i < m_bsgs->U.size(); ++i) { 00155 transversalSizes[i] = m_bsgs->U[i].size(); 00156 } 00157 std::sort(transversalSizes.begin(), transversalSizes.end()); 00158 00159 // test whether group order is a factorial of some natural number 00160 00161 unsigned int expectedFactor = 2; 00162 for (std::vector<unsigned int>::const_iterator it = transversalSizes.begin(); it != transversalSizes.end(); ++it) { 00163 if (*it == 1) 00164 continue; 00165 if (*it == expectedFactor) 00166 ++expectedFactor; 00167 else { 00168 expectedFactor = 0; 00169 break; 00170 } 00171 } 00172 00173 if (expectedFactor > 0) 00174 symmetricGroupCandidateDegree = expectedFactor - 1; 00175 00176 if (symmetricGroupCandidateDegree == m_n) 00177 return new SymmetricGroupType(symmetricGroupCandidateDegree, m_n); 00178 00179 // check for wreath products of symmetric groups if group is transitive 00180 if (m_bsgs->U[0].size() == m_n) { 00181 std::list<typename PERM::ptr> S1; 00182 PointwiseStabilizerPredicate<PERM> stabPred(m_bsgs->B[0]); 00183 BOOST_FOREACH(const typename PERM::ptr& p, m_bsgs->S) { 00184 if (stabPred(p)) 00185 S1.push_back(p); 00186 } 00187 PrimitivitySGSTest<TRANSVERSAL> primitivityTest(m_bsgs->S.begin(), m_bsgs->S.end(), m_bsgs->B[0], S1.begin(), S1.end(), m_bsgs->U[0]); 00188 std::vector<dom_int> minimalBlock; 00189 bool groupIsPrimitive = primitivityTest.blockOfImprimitivity(&minimalBlock); 00190 if ( ! groupIsPrimitive ) { 00191 // TODO: avoid integer overflow in order computation 00192 unsigned int degreeG = minimalBlock.size(); 00193 unsigned int degreeH = m_n / degreeG; 00194 if (m_n % degreeG == 0) { 00195 boost::uint64_t wreathSize = 1; 00196 // group order must equal factorial(deg G)^(deg H) * factorial(deg H) 00197 for (unsigned int i = 1; i <= degreeH; ++i) { 00198 for (unsigned int j = 2; j <= degreeG; ++j) { 00199 wreathSize *= j; 00200 } 00201 wreathSize *= i; 00202 } 00203 if (wreathSize == m_bsgs->order()) 00204 return new WreathSymmetricGroupType(degreeG, degreeH, m_n); 00205 } 00206 } else { 00207 GiantTest<PERM> giantTest; 00208 GiantTestBase::GiantGroupType giant = giantTest.determineGiantType(eps, 00209 m_n, m_bsgs->S.begin(), m_bsgs->S.end(), true); 00210 if (giant == GiantTestBase::Symmetric) 00211 return new SymmetricGroupType(m_n, m_n); 00212 else if (giant == GiantTestBase::Alternating) 00213 return new AlternatingGroupType(m_n, m_n); 00214 } 00215 } 00216 00217 00218 if (allowRecursiveCalls) { 00219 // check for multiple linked copies of S_k 00220 // TODO: check for inner direct products of S_k \times S_l 00221 GroupType* t = checkOrbitActions(); 00222 if (t) { 00223 return t; 00224 } 00225 } 00226 } // end if m_bsgs 00227 else // else if ! m_bsgs 00228 { 00229 GiantTest<PERM> giantTest; 00230 GiantTestBase::GiantGroupType giant = giantTest.determineGiantType(eps, 00231 m_n, m_generators.begin(), m_generators.end()); 00232 if (giant == GiantTestBase::Symmetric) 00233 return new SymmetricGroupType(m_n, m_n); 00234 else if (giant == GiantTestBase::Alternating) 00235 return new AlternatingGroupType(m_n, m_n); 00236 00237 if (allowRecursiveCalls) { 00238 GroupType* t = checkOrbitActions(); 00239 if (t) 00240 return t; 00241 } 00242 } 00243 00244 if (m_bsgs) 00245 return new AnonymousGroupType<>(m_n, m_bsgs->order()); 00246 return new AnonymousGroupType<>(m_n); 00247 } 00248 00249 template<class PERM, class TRANSVERSAL> 00250 GroupType* TypeRecognition<PERM,TRANSVERSAL>::checkOrbitActions() { 00251 if (m_generators.empty()) 00252 return NULL; 00253 00254 typedef typename PERM::ptr PERMptr; 00255 boost::dynamic_bitset<> worked(m_n); 00256 GroupType* candidateType = 0; 00257 00258 for (unsigned int i = 0; i < m_n; ++i) { 00259 if (worked[i]) 00260 continue; 00261 worked.set(i, true); 00262 OrbitSet<PERM, dom_int> orbit; 00263 orbit.orbit(i, m_generators, typename Transversal<PERM>::TrivialAction()); 00264 for (typename OrbitSet<PERM, dom_int>::const_iterator it = orbit.begin(); it != orbit.end(); ++it) { 00265 worked.set(*it, true); 00266 } 00267 00268 // restrict group to this orbit 00269 std::list<PERMptr> orbitGenerators; 00270 BOOST_FOREACH(const PERMptr& p, m_generators) { 00271 orbitGenerators.push_back(PERMptr(p->project(orbit.size(), orbit.begin(), orbit.end()))); 00272 } 00273 TypeRecognition<PERM, TRANSVERSAL> orbitTypeRecognition(orbit.size(), orbitGenerators.begin(), orbitGenerators.end()); 00274 GroupType* orbitType = orbitTypeRecognition.analyze(false); 00275 if ( ! candidateType ) 00276 candidateType = orbitType; 00277 else { 00278 const bool isEqualType = candidateType->equals(orbitType); 00279 delete orbitType; 00280 if ( ! isEqualType ) 00281 return NULL; 00282 } 00283 } 00284 if (candidateType) 00285 candidateType->setNonNaturalAction(m_n); 00286 return candidateType; 00287 } 00288 00289 00290 } 00291 00292 #endif 00293