permlib  0.2.9
Library for permutation computations
Public Types | Public Member Functions | Friends | List of all members
permlib::BSGS< PERM, TRANS > Struct Template Reference

Represents a base and strong generating set (BSGS) More...

#include <bsgs.h>

Inheritance diagram for permlib::BSGS< PERM, TRANS >:
permlib::BSGSCore< PERM, TRANS >

Public Types

typedef BSGSCore< PERM, TRANS >::PERMlist PERMlist
 
- Public Types inherited from permlib::BSGSCore< PERM, TRANS >
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 $G^{[i]}$ More...
 
void conjugate (const PERM &g)
 conjugate group with a permutation More...
 
- Public Member Functions inherited from permlib::BSGSCore< PERM, TRANS >
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

- Public Attributes inherited from permlib::BSGSCore< PERM, TRANS >
std::vector< dom_int > B
 base $B$
 
PERMlist S
 strong generating set $S$
 
std::vector< TRANS > U
 transversals $U$ along the stabilizer chain
 
dom_int n
 degree of group
 
- Protected Member Functions inherited from permlib::BSGSCore< PERM, TRANS >
 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
 
- Protected Attributes inherited from permlib::BSGSCore< PERM, TRANS >
int m_id
 id of this BSGS instance
 

Detailed Description

template<class PERM, class TRANS>
struct permlib::BSGS< PERM, TRANS >

Represents a base and strong generating set (BSGS)

Constructor & Destructor Documentation

◆ BSGS()

template<class PERM , class TRANS >
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

Member Function Documentation

◆ chooseBaseElement()

template<class PERM , class TRANS >
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

Parameters
h
betaelement moved by h
Returns
true iff an element h could be found

◆ conjugate()

template<class PERM , class TRANS >
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.

Parameters
gpermutation the group should be conjugated by

◆ insertGenerator()

template<class PERM , class TRANS >
int permlib::BSGS< PERM, TRANS >::insertGenerator ( const typename PERM::ptr &  g,
bool  updateOrbit 
)

adds a new group generator

Parameters
ggroup generator
updateOrbittrue iff transversals/orbits should be updates
Returns
index up to which transversals/orbits need update

◆ insertRedundantBasePoint()

template<class PERM , class TRANS >
unsigned int permlib::BSGS< PERM, TRANS >::insertRedundantBasePoint ( unsigned int  beta,
unsigned int  minPos = 0 
)

inserts a redundant base beta

Parameters
beta
minPosinsert point not before the minPos-th base element
Returns
insertion position

◆ operator=()

template<class PERM , class TRANS >
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

◆ orbit()

template<class PERM , class TRANS >
void permlib::BSGS< PERM, TRANS >::orbit ( unsigned int  j,
const PERMlist &  generators 
)

re-computes the j-th fundamental orbit with the given orbit generators

See also
Transversal<PERM>::orbit

◆ orbitUpdate()

template<class PERM , class TRANS >
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

See also
Transversal<PERM>::orbitUpdate

◆ order() [1/2]

template<class PERM , class TRANS >
template<typename Integer >
Integer permlib::BSGS< PERM, TRANS >::order ( ) const

order of the group

read from the transversal product

◆ order() [2/2]

template<class PERM , class TRANS >
boost::uint64_t permlib::BSGS< PERM, TRANS >::order ( ) const

order of the group

read from the transversal product

◆ random()

template<class PERM , class TRANS >
PERM permlib::BSGS< PERM, TRANS >::random ( const int  i = 0) const

generates a uniformly distributed random element of $G^{[i]}$

Parameters
ithe stabilizer chain index to generate the random element of. If set to 0 a random element of the whole group is returned.

◆ sift() [1/2]

template<class PERM , class TRANS >
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

Parameters
gpermutation to sift
siftee
jlowest transversal index to sift; i.e. sift through transversal U[j], U[j+1], ...

◆ sift() [2/2]

template<class PERM , class TRANS >
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

Parameters
gpermutation to sift
siftee
jlowest transversal index to sift
khighest transversal index to sift plus one

◆ stripRedundantStrongGenerators()

template<class PERM , class TRANS >
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.

◆ updateOrbits()

template<class PERM , class TRANS >
void permlib::BSGS< PERM, TRANS >::updateOrbits ( int  pos)

updates transversals/orbits

Parameters
posindex up to which transversals should be updated
See also
insertGenerator

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