32 #ifndef TYPE_RECOGNITION_H_ 33 #define TYPE_RECOGNITION_H_ 35 #include <permlib/prime_helper.h> 36 #include <permlib/transversal/schreier_tree_transversal.h> 37 #include <permlib/generator/bsgs_generator.h> 38 #include <permlib/construct/schreier_sims_construction.h> 39 #include <permlib/transversal/orbit_set.h> 40 #include <permlib/test/giant_test.h> 41 #include <permlib/test/group_type.h> 42 #include <permlib/test/primitivity_sgs_test.h> 43 #include <permlib/test/primitivity_test.h> 44 #include <permlib/permlib_api.h> 46 #include <boost/shared_ptr.hpp> 47 #include <boost/math/common_factor_rt.hpp> 58 template<
class PERM,
class TRANSVERSAL = SchreierTreeTransversal<PERM> >
69 template<
class InputIterator>
70 TypeRecognition(
unsigned int n, InputIterator genBegin, InputIterator genEnd);
80 PermutationGroupPtr
bsgs()
const {
return m_bsgs; }
91 const unsigned int m_n;
92 std::list<typename PERM::ptr> m_generators;
93 const PermutationGroupPtr m_externalBSGS;
94 PermutationGroupPtr m_bsgs;
108 static const unsigned int m_bsgsComputationDegreeLimit = 50;
111 template<
class PERM,
class TRANSVERSAL>
112 template<
class InputIterator>
114 : m_n(n), m_generators(genBegin, genEnd)
117 template<
class PERM,
class TRANSVERSAL>
119 : m_n(bsgs_->n), m_generators(bsgs_->S.begin(), bsgs_->S.end()), m_externalBSGS(bsgs_), m_bsgs(m_externalBSGS)
123 template<
class PERM,
class TRANSVERSAL>
125 if (m_n < m_bsgsComputationDegreeLimit && ! m_bsgs) {
131 const double eps = 1e-3;
134 const unsigned int groupIntOrder = m_bsgs->template order<unsigned int>();
136 if (groupIntOrder == 1)
139 if (groupIntOrder == 2)
146 BOOST_ASSERT( m_n % groupIntOrder == 0 );
150 if (groupIntOrder == 4) {
154 PERM el = bsgsGen.
next();
164 unsigned int symmetricGroupCandidateDegree = 0;
166 std::vector<unsigned int> transversalSizes(m_bsgs->U.size());
167 for (
unsigned int i = 0; i < m_bsgs->U.size(); ++i) {
168 transversalSizes[i] = m_bsgs->U[i].size();
170 std::sort(transversalSizes.begin(), transversalSizes.end());
174 unsigned int expectedFactor = 2;
175 for (std::vector<unsigned int>::const_iterator it = transversalSizes.begin(); it != transversalSizes.end(); ++it) {
178 if (*it == expectedFactor)
186 if (expectedFactor > 0)
187 symmetricGroupCandidateDegree = expectedFactor - 1;
189 if (symmetricGroupCandidateDegree == m_n)
193 if (m_bsgs->U[0].size() == m_n) {
194 std::list<typename PERM::ptr> S1;
196 BOOST_FOREACH(
const typename PERM::ptr& p, m_bsgs->S) {
201 std::vector<dom_int> minimalBlock;
203 if ( ! groupIsPrimitive ) {
205 unsigned int degreeG = minimalBlock.size();
206 unsigned int degreeH = m_n / degreeG;
207 if (m_n % degreeG == 0) {
208 boost::uint64_t wreathSize = 1;
210 for (
unsigned int i = 1; i <= degreeH; ++i) {
211 for (
unsigned int j = 2; j <= degreeG; ++j) {
216 if (wreathSize == m_bsgs->order())
222 m_n, m_bsgs->S.begin(), m_bsgs->S.end(),
true);
223 if (giant == GiantTestBase::Symmetric)
225 else if (giant == GiantTestBase::Alternating)
231 if (allowRecursiveCalls) {
244 m_n, m_generators.begin(), m_generators.end());
245 if (giant == GiantTestBase::Symmetric)
247 else if (giant == GiantTestBase::Alternating)
250 if (allowRecursiveCalls) {
262 template<
class PERM,
class TRANSVERSAL>
264 if (m_generators.empty())
267 typedef typename PERM::ptr PERMptr;
268 boost::dynamic_bitset<> worked(m_n);
270 unsigned int groupSupport = m_n;
272 for (
unsigned int i = 0; i < m_n; ++i) {
278 for (
typename OrbitSet<PERM, dom_int>::const_iterator it = orbit.
begin(); it != orbit.
end(); ++it) {
279 worked.set(*it,
true);
282 if (orbit.
size() == 1) {
288 std::list<PERMptr> orbitGenerators;
289 BOOST_FOREACH(
const PERMptr& p, m_generators) {
290 orbitGenerators.push_back(PERMptr(p->project(orbit.
size(), orbit.
begin(), orbit.
end())));
293 GroupType* orbitType = orbitTypeRecognition.analyze(
false);
294 if ( ! candidateType )
295 candidateType = orbitType;
297 const bool isEqualType = candidateType->
equals(orbitType);
305 return candidateType;
308 template<
typename PERM>
310 std::vector<dom_int> operator()(
const PERM& p,
const std::vector<dom_int>& v)
const {
311 std::vector<dom_int> ret(v.size());
312 for (
unsigned int i = 0; i < v.size(); ++i)
314 std::sort(ret.begin(), ret.end());
319 template<
class PERM,
class TRANSVERSAL>
321 if (m_generators.empty())
324 typedef boost::shared_ptr<OrbitSet<PERM, dom_int> > OrbitPtr;
325 typedef typename PERM::ptr PERMptr;
327 orbitCharacteristic.clear();
328 orbitCharacteristic.resize(m_n);
329 unsigned int orbitCharacteristicCounter = 0;
331 std::list<OrbitPtr> orbits;
332 boost::dynamic_bitset<> worked(m_n);
333 for (
unsigned int i = 0; i < m_n; ++i) {
339 for (
typename OrbitSet<PERM, dom_int>::const_iterator it = orbit->begin(); it != orbit->end(); ++it) {
340 worked.set(*it,
true);
342 orbits.push_back(orbit);
345 size_t orbitGCD = orbits.front()->size();
346 BOOST_FOREACH(
const OrbitPtr& orbit, orbits) {
347 orbitGCD = boost::math::gcd(orbitGCD, orbit->size());
351 BOOST_FOREACH(
const OrbitPtr& orbit, orbits) {
354 std::list<PERMptr> orbitGenerators;
356 std::vector<dom_int> orbitV(orbit->begin(), orbit->end());
357 BOOST_FOREACH(
const PERMptr& p, m_generators) {
358 orbitGenerators.push_back(PERMptr(p->project(orbit->size(), orbitV.begin(), orbitV.end())));
361 PermutationGroupPtr orbitGroup = construct(orbit->size(), orbitGenerators.begin(), orbitGenerators.end());
364 PrimitivityTest<PERM> primitivityTest(orbit->size(), orbitGenerators.begin(), orbitGenerators.end());
365 std::list<std::vector<dom_int> > blocks;
366 bool groupIsPrimitive = primitivityTest.
allBlocks(&blocks);
368 if (!groupIsPrimitive) {
369 BOOST_FOREACH(
const std::vector<dom_int>& b, blocks) {
371 if (orbits.size() != 1 && b.size() % orbitGCD != 0)
379 std::list<PERMptr> suborbitGenerators;
380 BOOST_FOREACH(
const PERMptr& p, stab->S) {
381 suborbitGenerators.push_back(PERMptr(p->project(b.size(), b.begin(), b.end())));
384 GroupType* subType = suborbitRecognition.analyze(
false);
385 if (subType->type() == GroupType::Named && subType->isNaturalAction()) {
387 if (strcmp(namedType->
name(),
"S") == 0) {
394 BOOST_FOREACH(
const std::vector<dom_int>& block, std::make_pair(blockOrbit.
begin(), blockOrbit.
end())) {
395 BOOST_FOREACH(
const dom_int j, block) {
396 orbitCharacteristic[orbitV[j]] = orbitCharacteristicCounter;
398 ++orbitCharacteristicCounter;
407 orbitType = suborbitRecognition.analyze(
false);
408 BOOST_FOREACH(
const dom_int& o, orbitV) {
409 orbitCharacteristic[o] = orbitCharacteristicCounter;
411 ++orbitCharacteristicCounter;
419 lastType = orbitType;
421 if (!lastType->equals(orbitType)) {
action of a PERM on unsigned long element
Definition: transversal.h:112
const_iterator begin() const
begin-iterator to orbit elements
Definition: orbit_set.h:66
Group type for alternating groups.
Definition: group_type.h:199
Group type for cyclic groups.
Definition: group_type.h:211
Group type for a direct product of two groups.
Definition: group_type.h:248
virtual PERM next()
generates an element
Definition: bsgs_generator.h:88
GroupType * analyze()
analyzes the given group and attempts to determine the group type
Definition: type_recognition.h:78
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
stores an orbit in a set for fast contains() operation
Definition: orbit_set.h:42
abstract base class for named groups (such as cyclic and symmetric groups)
Definition: group_type.h:157
const_iterator end() const
end-iterator to orbit elements
Definition: orbit_set.h:68
BSGS< PERM, TRANS > construct(ForwardIterator generatorsBegin, ForwardIterator generatorsEnd) const
constructs a BSGS for group given by generators with no base prescribed
Definition: schreier_sims_construction.h:85
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
GroupType * largeSymmetricDiagonalSubgroup(std::vector< dom_int > &orbitCharacteristic) const
attempts to find a large diagonal subgroup of symmetric groups
Definition: type_recognition.h:320
Tests a transitive group for which a strong generating set is availble for primitivity.
Definition: primitivity_sgs_test.h:55
Group type for symmetric groups.
Definition: group_type.h:187
const char * name() const
the name of the group
Definition: group_type.h:164
virtual bool hasNext()
true, iff more elements can be generated
Definition: bsgs_generator.h:82
bool equals(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:72
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
bool blockOfImprimitivity(std::vector< dom_int > *minimalBlock) const
Definition: primitivity_sgs_test.h:101
Group type for a permutation group whose type could not be determined.
Definition: group_type.h:131
Group type for a trivial permutation group.
Definition: group_type.h:114
bool allBlocks(std::list< std::vector< dom_int > > *blocks, bool findOnlyOneBlock=false) const
Definition: primitivity_test.h:132
boost::shared_ptr< BSGS< PERM, TRANSVERSAL > > PermutationGroupPtr
abbreviation for a pointer to a BSGS structure
Definition: type_recognition.h:62
Definition: type_recognition.h:309
GiantGroupType
Enumeration of "giant" groups, i.e. Alternating and Symmetric group.
Definition: giant_test.h:52
PermutationGroupPtr bsgs() const
returns a BSGS if one was constructed during the analysis
Definition: type_recognition.h:80
size_t size() const
number of orbit elements
Definition: orbit_set.h:60
void setNonNaturalAction(unsigned int realDegree_)
stores the information that this group acts non-naturally on realDegree many elements ...
Definition: group_type.h:83
Group type for a wreath product of symmetric groups.
Definition: group_type.h:226
abstract base class for permutation group types
Definition: group_type.h:40
Class for a basic type recognition of permutation groups.
Definition: type_recognition.h:59
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
void orbit(const PDOMAIN &beta, const std::list< typename PERM::ptr > &generators, Action a)
computes orbit of beta under generators
Definition: orbit_set.h:92
Tests a transitive group is availble for primitivity.
Definition: primitivity_test.h:55
TypeRecognition(unsigned int n, InputIterator genBegin, InputIterator genEnd)
Definition: type_recognition.h:113
stateful generator of BSGS elements
Definition: bsgs_generator.h:48
BSGS construction with classic Schreier-Sims algorithm.
Definition: schreier_sims_construction.h:46
Definition: abstract_bsgs.h:49