Represents a group of permutations on n elements. More...

#include <maths/permgroup.h>

Inheritance diagram for regina::PermGroup< n, cached >:

Classes
class	iterator
	The iterator type for this group. More...

Public Types
using	const_iterator = iterator
	The iterator type for this group. More...

Public Member Functions
	PermGroup ()
	Constructs the trivial group, containing only the identity permutation. More...

	PermGroup (NamedPermGroup group)
	Construct the given well-known permutation group. More...

	PermGroup (int k)
	Constructs the symmetric group `S_k`, formed from all permutations of 1,...,k. More...

	PermGroup (const PermGroup &src)=default
	Creates a new copy of the given group. More...

template<typename Test , typename... Args>
	PermGroup (const PermGroup &parent, Test &&test, Args &&... args)
	Generates the subgroup of all elements in the given group that pass the given membership test. More...

PermGroup &	operator= (const PermGroup &src)=default
	Sets this to be a copy of the given group. More...

Perm< n >::Index	size () const
	Returns the total number of elements in this group. More...

bool	contains (Perm< n > p) const
	Determines whether the given permutation belongs to this group. More...

bool	operator== (const PermGroup &other) const
	Indicates whether this and the given group are identical. More...

bool	operator!= (const PermGroup &other) const
	Indicates whether this and the given group are different. More...

iterator	begin () const
	Returns a C++ iterator pointing to the first element of this group. More...

iterator	end () const
	Returns a C++ iterator beyond the last element of this group. More...

auto	__iter__ () const
	Returns a Python iterator over the elements of this group. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

void	writeTextLong (std::ostream &out) const
	Writes a detailed text representation of this object to the given output stream. More...

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. More...

Static Public Member Functions
static PermGroup	centraliser (const PermClass< n > &conj)
	Returns the group of all permutations that fix the minimal representative of the given conjugacy class under conjugation. More...

Detailed Description

template<int n, bool cached = false>
class regina::PermGroup< n, cached >

Represents a group of permutations on n elements.

This is a subgroup of the symmetric group S_n.

Groups are stored internally using Sims tables (see Knuth volume 4A for a description of how these work); these are called stabiliser chains in many places. This storage mechanism means that, even though a permutation group could have size factorial in n, the storage space required is only quadratic in n.

PermGroup objects are, in their current implementation, entirely stack-based. This means they cannot support fast move or swap operations. However, since their size is quadratic in n, copy operations involve significantly more overhead than (for example) just copying a Perm object (which just holds a single machine-native integer). This decision is a deliberate trade-off between speed versus space; the implication for end users is that you should be economical about copying PermGroup objects, and work with them in-place where possible.

Python: Python does not support templates. In Python, the "vanilla" non-cached variants Perm<n> are available under the names PermGroup2, PermGroup3, ..., PermGroup16, and the cached variants Perm<n, true> are available under the names PermGroup2_Cached, PermGroup3_Cached, ..., PermGroup16_Cached.

Template Parameters

n	the number of objects being permuted. This must be between 2 and 16 inclusive.
cached	`true` if we should use precomputation-assisted routines such as Perm<n>::cachedComp() and Perm<n>::cachedInverse(), or `false` (the default) if we should just use the composition operator, inverse(), and so on. If this argument is `true`, you must have called Perm<n>::precompute() at least once in the lifetime of the program before using this class.

Member Typedef Documentation

◆ const_iterator

template<int n, bool cached = false>

using regina::PermGroup< n, cached >::const_iterator = iterator

The iterator type for this group.

Both iterator and const_iterator are the same type, since a PermGroup only offers read-only access to its group members. See the PermGroup::iterator class for further details.

Constructor & Destructor Documentation

◆ PermGroup() [1/5]

template<int n, bool cached>

regina::PermGroup< n, cached >::PermGroup

inline

Constructs the trivial group, containing only the identity permutation.

◆ PermGroup() [2/5]

template<int n, bool cached = false>

regina::PermGroup< n, cached >::PermGroup ( NamedPermGroup< n, cached > group )

Construct the given well-known permutation group.

This constructor can (for example) be used to easily construct the symmetric or alternating group on n elements.

Parameters

group indicates which well-known permutation group to construct.

◆ PermGroup() [3/5]

template<int n, bool cached = false>

regina::PermGroup< n, cached >::PermGroup ( int k )

Constructs the symmetric group S_k, formed from all permutations of 1,...,k.

The elements (k + 1),...,n will remain fixed under all permutations in this group.

The size of this group will be k!.

Parameters

k	indicates how many elements should be permuted; this must be between 0 and n inclusive.

◆ PermGroup() [4/5]

template<int n, bool cached = false>

regina::PermGroup< n, cached >::PermGroup ( const PermGroup< n, cached > & src )

default

Creates a new copy of the given group.

Parameters

src	the group to copy.

◆ PermGroup() [5/5]

template<int n, bool cached>

template<typename Test , typename... Args>

regina::PermGroup< n, cached >::PermGroup	(	const PermGroup< n, cached > &	parent,
		Test &&	test,
		Args &&...	args
	)

inline

Generates the subgroup of all elements in the given group that pass the given membership test.

Specifically, this generates the subgroup of all permutations p in parent for which test(p, args...) returns true.

The argument test should be a function or some other callable object. It must return a boolean, and its first argument should be a permutation (either by value as type Perm<n>, or by const reference as type const Perm<n>&). If there are any additional arguments supplied in the list args, these will be forwarded through as additional arguments to test.

Note that test will not necessarily be called for all permutations in parent, since this routine will deduce some subgroup members using the standard subgroup properties (e.g., closure and inverse). It is, however, guaranteed that the only permutations passed to test will be permutations that are already known to belong to parent.

Precondition: The given membership test does actually define a subgroup (that is, it behaves appropriately with respect to identity, inverse and closure).

Python: This constructor is available in Python, and the test argument may be a pure Python function. However, its form is more restricted: test must take exactly one argument (the permutation), and the args argument to this constructor is not present.

Parameters

parent	the "starting" group of all permutations under consideration.
test	a function (or other callable object) that determines which permutations in parent become members of this subgroup.
args	any additional arguments that should be passed to test, following the initial permutation argument.

Member Function Documentation

◆ iter()

template<int n, bool cached = false>

auto regina::PermGroup< n, cached >::__iter__ ( ) const

Returns a Python iterator over the elements of this group.

The order of iteration is arbitrary, and may change in future releases of Regina.

C++: Not present. For C++ users, PermGroup provides the usual begin() and end() functions instead. In particular, you can iterate over the elements of this group in the usual way using a range-based for loop.

Returns: an iterator over the elements of this group.

◆ begin()

template<int n, bool cached>

PermGroup< n, cached >::iterator regina::PermGroup< n, cached >::begin

inline

Returns a C++ iterator pointing to the first element of this group.

The iterator range from begin() to end() runs through all permutations in this group. The order of iteration is arbitrary, and may change in future releases of Regina.

Python: Not present. For Python users, PermGroup implements the Python iterable interface. You can iterate over the elements of this group in the same way that you would iterate over any native Python container.

Returns: an iterator pointing to the first element of this group.

◆ centraliser()

template<int n, bool cached = false>

static PermGroup regina::PermGroup< n, cached >::centraliser ( const PermClass< n > & conj )

static

Returns the group of all permutations that fix the minimal representative of the given conjugacy class under conjugation.

Specifically, if r is the minimal representative of the given class as returned by conj.rep(), then this routine constructs the subgroup of all permutations p for which p.inverse() * r * p == r.

Warning: While "most" such centraliser groups are small, they could get very large. For example, if conj represents the identity permutation, then the centraliser will be all of S_n. For n ≥ 5, it can be show that the next-worst case is where conj represents a single pair swap, in which case the centraliser has size 2⋅(n-2)!.

Precondition: conj is not the past-the-end conjugacy class.

Returns: the group of all permutations that leave rep() fixed under conjugation.

◆ contains()

template<int n, bool cached = false>

bool regina::PermGroup< n, cached >::contains ( Perm< n > p ) const

Determines whether the given permutation belongs to this group.

Regardless of the size of this group, the running time for this routine is small polynomial in n.

Parameters

p	the permutation whose membership we wish to test.

Returns: true if and only if p belongs to this group.

◆ detail()

std::string regina::Output< PermGroup< n, false > , false >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ end()

template<int n, bool cached>

PermGroup< n, cached >::iterator regina::PermGroup< n, cached >::end

inline

Returns a C++ iterator beyond the last element of this group.

The iterator range from begin() to end() runs through all permutations in this group. The order of iteration is arbitrary, and may change in future releases of Regina.

Python: Not present. For Python users, PermGroup implements the Python iterable interface. You can iterate over the elements of this group in the same way that you would iterate over any native Python container.

Returns: an iterator beyond the last element of this group.

◆ operator!=()

template<int n, bool cached>

bool regina::PermGroup< n, cached >::operator!= ( const PermGroup< n, cached > & other ) const

inline

Indicates whether this and the given group are different.

This does not test group isomorphism, and it does not test whether the two groups use the same internal representation. Instead it tests membership; that is, whether or not the two groups contain precisely the same set of permutations.

As a result, this test is not trivial. It is small polynomial time in n, but it is not as fast as (for example) directly comparing the internal representations.

Parameters

other the group to compare this with.

Returns: true if and only if there is some permutation that belongs to one group but not the other.

◆ operator=()

template<int n, bool cached = false>

PermGroup & regina::PermGroup< n, cached >::operator= ( const PermGroup< n, cached > & src )

default

Sets this to be a copy of the given group.

Parameters

src	the group to copy.

Returns: a reference to this group.

◆ operator==()

template<int n, bool cached = false>

bool regina::PermGroup< n, cached >::operator== ( const PermGroup< n, cached > & other ) const

Indicates whether this and the given group are identical.

This does not test group isomorphism, and it does not test whether the two groups use the same internal representation. Instead it tests membership; that is, whether or not the two groups contain precisely the same set of permutations.

As a result, this test is not trivial. It is small polynomial time in n, but it is not as fast as (for example) directly comparing the internal representations.

Parameters

other the group to compare this with.

Returns: true if and only if this and the given group contain the same permutations.

◆ size()

template<int n, bool cached>

Perm< n >::Index regina::PermGroup< n, cached >::size

inline

Returns the total number of elements in this group.

Returns: the size of this group.

◆ str()

std::string regina::Output< PermGroup< n, false > , false >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python: The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ utf8()

std::string regina::Output< PermGroup< n, false > , false >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ writeTextLong()

template<int n, bool cached = false>

void regina::PermGroup< n, cached >::writeTextLong ( std::ostream & out ) const

Writes a detailed text representation of this object to the given output stream.

Python: Not present. Use detail() instead.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

template<int n, bool cached>

void regina::PermGroup< n, cached >::writeTextShort ( std::ostream & out ) const

inline

Writes a short text representation of this object to the given output stream.

Python: Not present. Use str() instead.

Parameters

out	the output stream to which to write.

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

maths/permgroup.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ PermGroup() [1/5]

◆ PermGroup() [2/5]

◆ PermGroup() [3/5]

◆ PermGroup() [4/5]

◆ PermGroup() [5/5]

Member Function Documentation

◆ __iter__()

◆ begin()

◆ centraliser()

◆ contains()

◆ detail()

◆ end()

◆ operator!=()

◆ operator=()

◆ operator==()

◆ size()

◆ str()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()

◆ iter()