permlib  0.2.9
Library for permutation computations
Public Member Functions | Static Public Member Functions | List of all members
permlib::GiantTest< PERM > Class Template Reference

Tests a group given by generators for being an Alternating Group or a Symmetric Group. More...

#include <giant_test.h>

Inheritance diagram for permlib::GiantTest< PERM >:
permlib::GiantTestBase

Public Member Functions

template<typename ForwardIterator , typename TRANS >
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 More...
 
template<typename ForwardIterator >
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 More...
 
template<typename T >
GiantTestBase::GiantGroupType giantTypeByOrder (const T &order, const T &symOrder)
 
template<typename ForwardIterator , typename TRANS >
GiantTestBase::GiantGroupType determineGiantType (double eps, unsigned int n, ForwardIterator begin, ForwardIterator end, BSGS< PERM, TRANS > &bsgs, bool isKnownPrimitive) const
 

Static Public Member Functions

template<typename ForwardIterator >
static bool isSubgroupOfAlternatingGroup (ForwardIterator begin, ForwardIterator end)
 tests whether group given by generators is a subgroup of an Alternating Group More...
 

Additional Inherited Members

- Public Types inherited from permlib::GiantTestBase
enum  GiantGroupType { None, Alternating, Symmetric }
 Enumeration of "giant" groups, i.e. Alternating and Symmetric group.
 

Detailed Description

template<typename PERM>
class permlib::GiantTest< PERM >

Tests a group given by generators for being an Alternating Group or a Symmetric Group.

This an implementation of the algorithm given in Holt, Eick, O'Brien: Handbook of Computational Group Theory, 2005. Chapter 4.2

Member Function Documentation

◆ determineGiantType() [1/2]

template<typename PERM >
template<typename ForwardIterator , typename TRANS >
GiantGroupType permlib::GiantTest< PERM >::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

The test is deterministic for n < 8 and randomized for n >= 8. The randomized test assumes that n is smaller than

Parameters
epsIf randomized, 1-eps is the probability that the decision "None" is wrong
nDegree of the group
beginiterator of Permutation::ptr, group generators
enditerator of Permutation::ptr, group generators
bsgsif for the test a BSGS is computed, it is stored into this variable
isKnownPrimitivetrue if group is known to be primitive
Returns
Result "None" may be wrong if n >= 8 with probability eps

◆ determineGiantType() [2/2]

template<typename PERM >
template<typename ForwardIterator >
GiantGroupType permlib::GiantTest< PERM >::determineGiantType ( double  eps,
unsigned int  n,
ForwardIterator  begin,
ForwardIterator  end,
bool  isKnownPrimitive = false 
) const
inline

tests whether group given by generators is an Alternating or a Symmetric Group

The test is deterministic for n < 8 and randomized for n >= 8. The randomized test assumes that n is smaller than

Parameters
epsIf randomized, 1-eps is the probability that the decision "None" is wrong
nDegree of the group
beginiterator of Permutation::ptr, group generators
enditerator of Permutation::ptr, group generators
isKnownPrimitivetrue if group is known to be primitive
Returns
Result "None" may be wrong if n >= 8 with probability eps

◆ isSubgroupOfAlternatingGroup()

template<typename PERM >
template<typename ForwardIterator >
bool permlib::GiantTest< PERM >::isSubgroupOfAlternatingGroup ( ForwardIterator  begin,
ForwardIterator  end 
)
static

tests whether group given by generators is a subgroup of an Alternating Group

Tests subgroup property by computing parity of all generators.

Parameters
beginiterator of Permutation::ptr, group generators
enditerator of Permutation::ptr, group generators
Returns
true if the group is a subgroup of an alternating group

The documentation for this class was generated from the following file: