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>
42#include <boost/foreach.hpp>
43#include <boost/integer/common_factor_rt.hpp>
60template<
typename PERM>
76 template<
typename ForwardIterator,
typename TRANS>
91 template<
typename ForwardIterator>
105 template<
typename ForwardIterator>
110 static GiantGroupType giantTypeByOrder(
const T& order,
const T& symOrder);
114template<
typename PERM>
115template<
typename ForwardIterator>
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)
131template<
typename PERM>
134 if (order == symOrder / 2)
136 if (order == symOrder)
141template<
typename PERM>
142template<
typename ForwardIterator,
typename TRANS>
149 for (ForwardIterator pit = begin; pit != end; ++pit) {
150 if ( ! (*pit)->isIdentity() )
156 bsgs = ssc.construct(begin, end);
157 const boost::uint64_t order = bsgs.order();
160 return giantTypeByOrder(order,
static_cast<boost::uint64_t
>(6));
162 return giantTypeByOrder(order,
static_cast<boost::uint64_t
>(24));
164 return giantTypeByOrder(order,
static_cast<boost::uint64_t
>(120));
166 return giantTypeByOrder(order,
static_cast<boost::uint64_t
>(720));
168 return giantTypeByOrder(order,
static_cast<boost::uint64_t
>(5040));
177 const unsigned int randomRuns =
static_cast<unsigned int>(-std::log(eps) * std::log(n) / 0.395);
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());
186 BOOST_FOREACH(
const CyclePair& c, cycleList) {
187 cycleLength[j++] = c.second;
189 for (j = 0; j < cycleLength.size(); ++j) {
190 const unsigned int len = cycleLength[j];
194 bool isCoprime =
true;
195 for (
unsigned int k = 0; k < cycleLength.size(); ++k) {
198 if (boost::integer::gcd(cycleLength[j], cycleLength[k]) != 1) {
206 if (isSubgroupOfAlternatingGroup(begin, end))
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 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, BSGS< PERM, TRANS > &bsgs, bool isKnownPrimitive=false) const
tests whether group given by generators is an Alternating or a Symmetric Group
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
static bool isPrimeNumber(unsigned int x, bool checkBounds)
checks if a given number is prime
Definition prime_helper.h:52
generates nearly-uniformly distributed random group elements using the product replacement algorithm
Definition product_replacement_generator.h:45
BSGS construction with classic Schreier-Sims algorithm.
Definition schreier_sims_construction.h:46
Represents a base and strong generating set (BSGS)
Definition bsgs.h:89
Definition giant_test.h:50
GiantGroupType
Enumeration of "giant" groups, i.e. Alternating and Symmetric group.
Definition giant_test.h:52