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

#include <bsgs.h>

Inheritance diagram for permlib::BSGS< 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

PERMlist	S
	strong generating set

std::vector< TRANS >	U
	transversals 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
beta	element 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

g	permutation 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

g	group generator
updateOrbit	true 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
minPos	insert 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

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

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

i	the 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,
		unsigned int	k
	)		const

sifts an element through the specified transversal range

Parameters

g	permutation to sift
siftee
j	lowest transversal index to sift
k	highest transversal index to sift plus one

◆ sift() [2/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

g	permutation to sift
siftee
j	lowest transversal index to sift; i.e. sift through transversal U[j], U[j+1], ...

◆ 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

pos	index up to which transversals should be updated

See also: insertGenerator

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

include/permlib/bsgs.h

Public Types

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

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

Constructor & Destructor Documentation

◆ BSGS()

Member Function Documentation

◆ chooseBaseElement()

◆ conjugate()

◆ insertGenerator()

◆ insertRedundantBasePoint()

◆ operator=()

◆ orbit()

◆ orbitUpdate()

◆ order() [1/2]

◆ order() [2/2]

◆ random()

◆ sift() [1/2]

◆ sift() [2/2]

◆ stripRedundantStrongGenerators()

◆ updateOrbits()

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