permlib
0.2.9
Library for permutation computations
|
Represents a base and strong generating set (BSGS) More...
#include <bsgs.h>
Public Types | |
typedef BSGSCore< PERM, TRANS >::PERMlist | PERMlist |
![]() | |
typedef PERM | PERMtype |
permutation type used by this BSGS | |
typedef TRANS | TRANStype |
transversal type used by this BSGS | |
typedef std::list< typename PERM::ptr > | PERMlist |
Public Member Functions | |
BSGS (dom_int n) | |
constructs an empty group of degree n | |
BSGS (const BSGS< PERM, TRANS > &bsgs) | |
copy constructor More... | |
BSGS< PERM, TRANS > & | operator= (const BSGS< PERM, TRANS > &) |
assignment operator More... | |
template<typename Integer > | |
Integer | order () const |
order of the group More... | |
boost::uint64_t | order () const |
order of the group More... | |
unsigned int | sift (const PERM &g, PERM &siftee, unsigned int j=0) const |
sifts an element through the specified transversal range More... | |
unsigned int | sift (const PERM &g, PERM &siftee, unsigned int j, unsigned int k) const |
sifts an element through the specified transversal range More... | |
bool | sifts (const PERM &g) const |
true iff g sifts through transversal system | |
bool | chooseBaseElement (const PERM &h, dom_int &beta) const |
tries to find a new base element More... | |
unsigned int | insertRedundantBasePoint (unsigned int beta, unsigned int minPos=0) |
inserts a redundant base beta More... | |
void | stripRedundantBasePoints (int minPos=0) |
strips redundant base points from the end to the minPos-th base element | |
void | stripRedundantStrongGenerators () |
removes redundant generators More... | |
void | orbit (unsigned int j, const PERMlist &generators) |
re-computes the j-th fundamental orbit with the given orbit generators More... | |
void | orbitUpdate (unsigned int j, const PERMlist &generators, const typename PERM::ptr &g) |
updates the j-th fundamental orbit with the given orbit generators and a new generator g More... | |
int | insertGenerator (const typename PERM::ptr &g, bool updateOrbit) |
adds a new group generator More... | |
void | updateOrbits (int pos) |
updates transversals/orbits More... | |
PERM | random (const int i=0) const |
generates a uniformly distributed random element of ![]() | |
void | conjugate (const PERM &g) |
conjugate group with a permutation More... | |
![]() | |
virtual | ~BSGSCore () |
empty destructor | |
virtual bool | operator== (const BSGSCore< PERM, TRANS > &bsgs) const |
checks for equality by internal id only More... | |
virtual bool | isSymmetricGroup () const |
true if this structure represents a symmetric group | |
Friends | |
std::ostream & | operator<< (std::ostream &out, const BSGS< PERM, TRANS > &bsgs) |
writes base, SGS and transversals | |
Additional Inherited Members | |
![]() | |
std::vector< dom_int > | B |
base ![]() | |
PERMlist | S |
strong generating set ![]() | |
std::vector< TRANS > | U |
transversals ![]() | |
dom_int | n |
degree of group | |
![]() | |
BSGSCore (unsigned int id) | |
constructs empty data structure with given group id | |
BSGSCore (unsigned int id, dom_int n_, dom_int bSize) | |
constructs empty data structure with given group id, group degree n and base size n | |
BSGSCore (unsigned int id, const std::vector< dom_int > &B_, const std::vector< TRANS > &U_, dom_int n_) | |
kind of copy constructor, initializes data structure with given data | |
![]() | |
int | m_id |
id of this BSGS instance | |
Represents a base and strong generating set (BSGS)
permlib::BSGS< PERM, TRANS >::BSGS | ( | const BSGS< PERM, TRANS > & | bsgs | ) |
copy constructor
creates a deep copy of generator list and transversals, so there is no link between the original BSGS and the copy
bool permlib::BSGS< PERM, TRANS >::chooseBaseElement | ( | const PERM & | h, |
dom_int & | beta | ||
) | const |
tries to find a new base element
find an element which is moved by h
h | |
beta | element moved by h |
void permlib::BSGS< PERM, TRANS >::conjugate | ( | const PERM & | g | ) |
conjugate group with a permutation
If S is the generating set of this group, then after conjugation the group will be generated by c^{-1} S c.
g | permutation the group should be conjugated by |
int permlib::BSGS< PERM, TRANS >::insertGenerator | ( | const typename PERM::ptr & | g, |
bool | updateOrbit | ||
) |
adds a new group generator
g | group generator |
updateOrbit | true iff transversals/orbits should be updates |
unsigned int permlib::BSGS< PERM, TRANS >::insertRedundantBasePoint | ( | unsigned int | beta, |
unsigned int | minPos = 0 |
||
) |
inserts a redundant base beta
beta | |
minPos | insert point not before the minPos-th base element |
BSGS< PERM, TRANS > & permlib::BSGS< PERM, TRANS >::operator= | ( | const BSGS< PERM, TRANS > & | bsgs | ) |
assignment operator
creates a deep copy of generator list and transversals, so there is no link between the original BSGS and the copy
void permlib::BSGS< PERM, TRANS >::orbit | ( | unsigned int | j, |
const PERMlist & | generators | ||
) |
re-computes the j-th fundamental orbit with the given orbit generators
void permlib::BSGS< PERM, TRANS >::orbitUpdate | ( | unsigned int | j, |
const PERMlist & | generators, | ||
const typename PERM::ptr & | g | ||
) |
updates the j-th fundamental orbit with the given orbit generators and a new generator g
Integer permlib::BSGS< PERM, TRANS >::order | ( | ) | const |
order of the group
read from the transversal product
boost::uint64_t permlib::BSGS< PERM, TRANS >::order | ( | ) | const |
order of the group
read from the transversal product
PERM permlib::BSGS< PERM, TRANS >::random | ( | const int | i = 0 | ) | const |
generates a uniformly distributed random element of
i | the stabilizer chain index to generate the random element of. If set to 0 a random element of the whole group is returned. |
unsigned int permlib::BSGS< PERM, TRANS >::sift | ( | const PERM & | g, |
PERM & | siftee, | ||
unsigned int | j = 0 |
||
) | const |
sifts an element through the specified transversal range
g | permutation to sift |
siftee | |
j | lowest transversal index to sift; i.e. sift through transversal U[j], U[j+1], ... |
unsigned int permlib::BSGS< PERM, TRANS >::sift | ( | const PERM & | g, |
PERM & | siftee, | ||
unsigned int | j, | ||
unsigned int | k | ||
) | const |
sifts an element through the specified transversal range
g | permutation to sift |
siftee | |
j | lowest transversal index to sift |
k | highest transversal index to sift plus one |
void permlib::BSGS< PERM, TRANS >::stripRedundantStrongGenerators | ( | ) |
removes redundant generators
The remaining set S is still a strong generating set. Its size will be at most log |G|.
Note that applying this method may result in a difference between transversals and strong generating set. If you use a SchreierTree, then the transversal will no longer automatically return elements from the strong generating set.
void permlib::BSGS< PERM, TRANS >::updateOrbits | ( | int | pos | ) |
updates transversals/orbits
pos | index up to which transversals should be updated |