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);
91 const unsigned int m_n;
92 std::list<typename PERM::ptr> m_generators;
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) {
127 m_bsgs = PermutationGroupPtr(
new BSGS<PERM, TRANSVERSAL>(ssc.construct(m_generators.begin(), m_generators.end())));
131 const double eps = 1e-3;
134 const unsigned int groupIntOrder = m_bsgs->template order<unsigned int>();
136 if (groupIntOrder == 1)
137 return new TrivialGroupType(m_n);
139 if (groupIntOrder == 2)
140 return new SymmetricGroupType(groupIntOrder, m_n);
146 BOOST_ASSERT( m_n % groupIntOrder == 0 );
147 return new CyclicGroupType(groupIntOrder, m_n);
150 if (groupIntOrder == 4) {
152 BSGSGenerator<TRANSVERSAL> bsgsGen(m_bsgs->U);
153 while (bsgsGen.hasNext()) {
154 PERM el = bsgsGen.next();
156 return new CyclicGroupType(4, m_n);
158 return new DirectProductGroupType(
new SymmetricGroupType(2,2),
new SymmetricGroupType(2,2), m_n);
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)
190 return new SymmetricGroupType(symmetricGroupCandidateDegree, m_n);
193 if (m_bsgs->U[0].size() == m_n) {
194 std::list<typename PERM::ptr> S1;
195 PointwiseStabilizerPredicate<PERM> stabPred(m_bsgs->B[0]);
196 BOOST_FOREACH(
const typename PERM::ptr& p, m_bsgs->S) {
200 PrimitivitySGSTest<TRANSVERSAL> primitivityTest(m_bsgs->S.begin(), m_bsgs->S.end(), m_bsgs->B[0], S1.begin(), S1.end(), m_bsgs->U[0]);
201 std::vector<dom_int> minimalBlock;
202 bool groupIsPrimitive = primitivityTest.blockOfImprimitivity(&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())
217 return new WreathSymmetricGroupType(degreeG, degreeH, m_n);
220 GiantTest<PERM> giantTest;
222 m_n, m_bsgs->S.begin(), m_bsgs->S.end(),
true);
223 if (giant == GiantTestBase::Symmetric)
224 return new SymmetricGroupType(m_n, m_n);
225 else if (giant == GiantTestBase::Alternating)
226 return new AlternatingGroupType(m_n, m_n);
231 if (allowRecursiveCalls) {
234 GroupType* t = checkOrbitActions();
242 GiantTest<PERM> giantTest;
244 m_n, m_generators.begin(), m_generators.end());
245 if (giant == GiantTestBase::Symmetric)
246 return new SymmetricGroupType(m_n, m_n);
247 else if (giant == GiantTestBase::Alternating)
248 return new AlternatingGroupType(m_n, m_n);
250 if (allowRecursiveCalls) {
251 GroupType* t = checkOrbitActions();
258 return new AnonymousGroupType<>(m_n, m_bsgs->order());
259 return new AnonymousGroupType<>(m_n);
262 template<
class PERM,
class TRANSVERSAL>
263 GroupType* TypeRecognition<PERM,TRANSVERSAL>::checkOrbitActions() {
264 if (m_generators.empty())
267 typedef typename PERM::ptr PERMptr;
268 boost::dynamic_bitset<> worked(m_n);
269 GroupType* candidateType = 0;
270 unsigned int groupSupport = m_n;
272 for (
unsigned int i = 0; i < m_n; ++i) {
276 OrbitSet<PERM, dom_int> orbit;
277 orbit.orbit(i, m_generators,
typename Transversal<PERM>::TrivialAction());
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())));
292 TypeRecognition<PERM, TRANSVERSAL> orbitTypeRecognition(orbit.size(), orbitGenerators.begin(), orbitGenerators.end());
293 GroupType* orbitType = orbitTypeRecognition.analyze(
false);
294 if ( ! candidateType )
295 candidateType = orbitType;
297 const bool isEqualType = candidateType->equals(orbitType);
304 candidateType->setNonNaturalAction(groupSupport);
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
GroupType * analyze()
analyzes the given group and attempts to determine the group type
Definition: type_recognition.h:78
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
GroupType * largeSymmetricDiagonalSubgroup(std::vector< dom_int > &orbitCharacteristic) const
attempts to find a large diagonal subgroup of symmetric groups
Definition: type_recognition.h:320
const char * name() const
the name of the group
Definition: group_type.h:164
bool equals(const GroupType *type_) const
checks if two group types represent the same permutation group
Definition: group_type.h:72
static bool isPrimeNumber(unsigned int x, bool checkBounds)
checks if a given number is prime
Definition: prime_helper.h:52
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
void setNonNaturalAction(unsigned int realDegree_)
stores the information that this group acts non-naturally on realDegree many elements ...
Definition: group_type.h:83
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
BSGS construction with classic Schreier-Sims algorithm.
Definition: schreier_sims_construction.h:46
Definition: abstract_bsgs.h:49