permlib  0.2.9
Library for permutation computations
giant_test.h
1 // ---------------------------------------------------------------------------
2 //
3 // This file is part of PermLib.
4 //
5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions
10 // are met:
11 // 1. Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // 2. Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // 3. The name of the author may not be used to endorse or promote products
17 // derived from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // ---------------------------------------------------------------------------
31 
32 
33 #ifndef GIANT_TEST_H_
34 #define GIANT_TEST_H_
35 
36 #include <permlib/generator/product_replacement_generator.h>
37 #include <permlib/transversal/explicit_transversal.h>
38 #include <permlib/bsgs.h>
39 #include <permlib/construct/schreier_sims_construction.h>
40 #include <permlib/prime_helper.h>
41 
42 #include <boost/foreach.hpp>
43 #include <boost/math/common_factor_rt.hpp>
44 #include <cmath>
45 #include <algorithm>
46 
47 namespace permlib {
48 
49 
50 struct GiantTestBase {
52  enum GiantGroupType { None, Alternating, Symmetric };
53 };
54 
56 
60 template<typename PERM>
61 class GiantTest : public GiantTestBase {
62 public:
64 
76  template<typename ForwardIterator, typename TRANS>
77  GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive = false) const;
78 
80 
91  template<typename ForwardIterator>
92  GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, bool isKnownPrimitive = false) const {
93  typedef ExplicitTransversal<PERM> TRANS;
94  BSGS<PERM, TRANS> bsgs(n);
95  return determineGiantType<ForwardIterator, TRANS>(eps, n, begin, end, bsgs, isKnownPrimitive);
96  }
97 
99 
105  template<typename ForwardIterator>
106  static bool isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end);
107 
108 private:
109  template<class T>
110  static GiantGroupType giantTypeByOrder(const T& order, const T& symOrder);
111 };
112 
113 
114 template<typename PERM>
115 template<typename ForwardIterator>
116 bool GiantTest<PERM>::isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end) {
117  typedef std::pair<dom_int, unsigned int> CyclePair;
118  for (ForwardIterator pit = begin; pit != end; ++pit) {
119  unsigned int parity = 0;
120  std::list<CyclePair> genCycles = (*pit)->cycles();
121  BOOST_FOREACH(const CyclePair& c, genCycles) {
122  if (c.second % 2 == 0)
123  ++parity;
124  }
125  if (parity % 2 != 0)
126  return false;
127  }
128  return true;
129 }
130 
131 template<typename PERM>
132 template<typename T>
133 GiantTestBase::GiantGroupType GiantTest<PERM>::giantTypeByOrder(const T& order, const T& symOrder) {
134  if (order == symOrder / 2)
135  return Alternating;
136  if (order == symOrder)
137  return Symmetric;
138  return None;
139 }
140 
141 template<typename PERM>
142 template<typename ForwardIterator, typename TRANS>
143 GiantTestBase::GiantGroupType GiantTest<PERM>::determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS<PERM, TRANS>& bsgs, bool isKnownPrimitive) const {
144  BOOST_ASSERT(n > 1);
145 
146  // special cases for n < 8
147 
148  if (n == 2) {
149  for (ForwardIterator pit = begin; pit != end; ++pit) {
150  if ( ! (*pit)->isIdentity() )
151  return Symmetric;
152  }
153  return None;
154  } else if (n < 8) {
155  SchreierSimsConstruction<PERM, TRANS> ssc(n);
156  bsgs = ssc.construct(begin, end);
157  const boost::uint64_t order = bsgs.order();
158  switch (n) {
159  case 3:
160  return giantTypeByOrder(order, static_cast<boost::uint64_t>(6));
161  case 4:
162  return giantTypeByOrder(order, static_cast<boost::uint64_t>(24));
163  case 5:
164  return giantTypeByOrder(order, static_cast<boost::uint64_t>(120));
165  case 6:
166  return giantTypeByOrder(order, static_cast<boost::uint64_t>(720));
167  case 7:
168  return giantTypeByOrder(order, static_cast<boost::uint64_t>(5040));
169  default:
170  // should not happen
171  BOOST_ASSERT(false);
172  return None;
173  }
174  }
175 
176  // This constant 0.395 comes from 0.57 * log(2)
177  const unsigned int randomRuns = static_cast<unsigned int>(-std::log(eps) * std::log(n) / 0.395);
178 
179  ProductReplacementGenerator<PERM> rng(n, begin, end);
180  for (unsigned int i = 0; i < randomRuns; ++i) {
181  PERM randPerm = rng.next();
182  typedef std::pair<dom_int, unsigned int> CyclePair;
183  std::list<CyclePair> cycleList = randPerm.cycles();
184  std::vector<unsigned int> cycleLength(cycleList.size());
185  unsigned int j = 0;
186  BOOST_FOREACH(const CyclePair& c, cycleList) {
187  cycleLength[j++] = c.second;
188  }
189  for (j = 0; j < cycleLength.size(); ++j) {
190  const unsigned int len = cycleLength[j];
191  if (len < n-2 && PrimeHelper::isPrimeNumber(len, true) && (isKnownPrimitive || len > n/2)) {
192  // check whether $len is co-prime to all other cycle length.
193  // if so, the group contains a real cycle of length $len
194  bool isCoprime = true;
195  for (unsigned int k = 0; k < cycleLength.size(); ++k) {
196  if (j == k)
197  continue;
198  if (boost::math::gcd(cycleLength[j], cycleLength[k]) != 1) {
199  isCoprime = false;
200  break;
201  }
202  }
203  if ( ! isCoprime )
204  continue;
205 
206  if (isSubgroupOfAlternatingGroup(begin, end))
207  return Alternating;
208  else
209  return Symmetric;
210  }
211  }
212  }
213 
214  return None;
215 }
216 
217 
218 } // end NS permlib
219 
220 #endif
Definition: giant_test.h:50
GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS< PERM, TRANS > &bsgs, bool isKnownPrimitive=false) const
tests whether group given by generators is an Alternating or a Symmetric Group
Transversal class that stores all transversal elements explicitly.
Definition: explicit_transversal.h:42
Tests a group given by generators for being an Alternating Group or a Symmetric Group.
Definition: giant_test.h:61
static bool isPrimeNumber(unsigned int x, bool checkBounds)
checks if a given number is prime
Definition: prime_helper.h:52
GiantGroupType
Enumeration of "giant" groups, i.e. Alternating and Symmetric group.
Definition: giant_test.h:52
static bool isSubgroupOfAlternatingGroup(ForwardIterator begin, ForwardIterator end)
tests whether group given by generators is a subgroup of an Alternating Group
Definition: giant_test.h:116
GiantGroupType determineGiantType(double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, bool isKnownPrimitive=false) const
tests whether group given by generators is an Alternating or a Symmetric Group
Definition: giant_test.h:92
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
Definition: abstract_bsgs.h:49