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 GIANT_TEST_H_ 00034 #define GIANT_TEST_H_ 00035 00036 #include <permlib/generator/product_replacement_generator.h> 00037 #include <permlib/transversal/explicit_transversal.h> 00038 #include <permlib/bsgs.h> 00039 #include <permlib/construct/schreier_sims_construction.h> 00040 #include <permlib/prime_helper.h> 00041 00042 #include <boost/foreach.hpp> 00043 #include <boost/math/common_factor_rt.hpp> 00044 #include <cmath> 00045 #include <algorithm> 00046 00047 namespace permlib { 00048 00049 00050 struct GiantTestBase { 00052 enum GiantGroupType { None, Alternating, Symmetric }; 00053 }; 00054 00056 00060 template<typename PERM> 00061 class GiantTest : public GiantTestBase { 00062 public: 00064 00076 template<typename ForwardIterator, typename TRANS> 00077 GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive = false) const; 00078 00080 00091 template<typename ForwardIterator> 00092 GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, bool isKnownPrimitive = false) const { 00093 typedef ExplicitTransversal<PERM> TRANS; 00094 BSGS<PERM, TRANS> bsgs(n); 00095 return determineGiantType<ForwardIterator, TRANS>(eps, n, begin, end, bsgs, isKnownPrimitive); 00096 } 00097 00099 00105 template<typename ForwardIterator> 00106 static bool isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end); 00107 00108 private: 00109 template<class T> 00110 static GiantGroupType giantTypeByOrder(const T& order, const T& symOrder); 00111 }; 00112 00113 00114 template<typename PERM> 00115 template<typename ForwardIterator> 00116 bool GiantTest<PERM>::isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end) { 00117 typedef std::pair<dom_int, unsigned int> CyclePair; 00118 for (ForwardIterator pit = begin; pit != end; ++pit) { 00119 unsigned int parity = 0; 00120 std::list<CyclePair> genCycles = (*pit)->cycles(); 00121 BOOST_FOREACH(const CyclePair& c, genCycles) { 00122 if (c.second % 2 == 0) 00123 ++parity; 00124 } 00125 if (parity % 2 != 0) 00126 return false; 00127 } 00128 return true; 00129 } 00130 00131 template<typename PERM> 00132 template<typename T> 00133 GiantTestBase::GiantGroupType GiantTest<PERM>::giantTypeByOrder(const T& order, const T& symOrder) { 00134 if (order == symOrder / 2) 00135 return Alternating; 00136 if (order == symOrder) 00137 return Symmetric; 00138 return None; 00139 } 00140 00141 template<typename PERM> 00142 template<typename ForwardIterator, typename TRANS> 00143 GiantTestBase::GiantGroupType GiantTest<PERM>::determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive) const { 00144 BOOST_ASSERT(n > 1); 00145 00146 // special cases for n < 8 00147 00148 if (n == 2) { 00149 for (ForwardIterator pit = begin; pit != end; ++pit) { 00150 if ( ! (*pit)->isIdentity() ) 00151 return Symmetric; 00152 } 00153 return None; 00154 } else if (n < 8) { 00155 SchreierSimsConstruction<PERM, TRANS> ssc(n); 00156 bsgs = ssc.construct(begin, end); 00157 const boost::uint64_t order = bsgs.order(); 00158 switch (n) { 00159 case 3: 00160 return giantTypeByOrder(order, static_cast<boost::uint64_t>(6)); 00161 case 4: 00162 return giantTypeByOrder(order, static_cast<boost::uint64_t>(24)); 00163 case 5: 00164 return giantTypeByOrder(order, static_cast<boost::uint64_t>(120)); 00165 case 6: 00166 return giantTypeByOrder(order, static_cast<boost::uint64_t>(720)); 00167 case 7: 00168 return giantTypeByOrder(order, static_cast<boost::uint64_t>(5040)); 00169 default: 00170 // should not happen 00171 BOOST_ASSERT(false); 00172 return None; 00173 } 00174 } 00175 00176 // This constant 0.395 comes from 0.57 * log(2) 00177 const unsigned int randomRuns = static_cast<unsigned int>(-std::log(eps) * std::log(n) / 0.395); 00178 00179 ProductReplacementGenerator<PERM> rng(n, begin, end); 00180 for (unsigned int i = 0; i < randomRuns; ++i) { 00181 PERM randPerm = rng.next(); 00182 typedef std::pair<dom_int, unsigned int> CyclePair; 00183 std::list<CyclePair> cycleList = randPerm.cycles(); 00184 std::vector<unsigned int> cycleLength(cycleList.size()); 00185 unsigned int j = 0; 00186 BOOST_FOREACH(const CyclePair& c, cycleList) { 00187 cycleLength[j++] = c.second; 00188 } 00189 for (j = 0; j < cycleLength.size(); ++j) { 00190 const unsigned int len = cycleLength[j]; 00191 if (len < n-2 && PrimeHelper::isPrimeNumber(len, true) && (isKnownPrimitive || len > n/2)) { 00192 // check whether $len is co-prime to all other cycle length. 00193 // if so, the group contains a real cycle of length $len 00194 bool isCoprime = true; 00195 for (unsigned int k = 0; k < cycleLength.size(); ++k) { 00196 if (j == k) 00197 continue; 00198 if (boost::math::gcd(cycleLength[j], cycleLength[k]) != 1) { 00199 isCoprime = false; 00200 break; 00201 } 00202 } 00203 if ( ! isCoprime ) 00204 continue; 00205 00206 if (isSubgroupOfAlternatingGroup(begin, end)) 00207 return Alternating; 00208 else 00209 return Symmetric; 00210 } 00211 } 00212 } 00213 00214 return None; 00215 } 00216 00217 00218 } // end NS permlib 00219 00220 #endif