Represents a permutation of {0,1}. More...

#include <maths/spec/perm2.h>

Public Types
using	Index = int
	Denotes a native signed integer type large enough to count all permutations on two elements.

using	Code = uint8_t
	Indicates the native unsigned integer type used to store the internal permutation code.

using	Code2 = Code
	An alias for Code, indicating the native unsigned integer type used to store the internal permutation code.

Public Member Functions
constexpr	Perm ()
	Creates the identity permutation.

constexpr	Perm (int a, int b)
	Creates the transposition of a and b.

constexpr	Perm (const std::array< int, 2 > &image)
	Creates a permutation mapping i to image[i] for each i = 0,1.

constexpr	Perm (const Perm< 2 > &cloneMe)=default
	Creates a permutation that is a clone of the given permutation.

constexpr Code	permCode () const
	Returns the internal code representing this permutation.

void	setPermCode (Code code)
	Sets this permutation to that represented by the given internal code.

Perm< 2 > &	operator= (const Perm< 2 > &cloneMe)=default
	Sets this permutation to be equal to the given permutation.

constexpr Perm< 2 >	operator* (const Perm< 2 > &q) const
	Returns the composition of this permutation with the given permutation.

Perm< 2 >	cachedComp (const Perm< 2 > &q) const
	An alias for the composition operator, provided to assist with writing generic code.

Perm< 2 >	cachedComp (const Perm< 2 > &q, const Perm< 2 > &r) const
	Deprecated alias for using the composition operator twice, provided to assist with writing generic code.

constexpr Perm< 2 >	conjugate (const Perm< 2 > &q) const
	Computes the conjugate of this permutation by q.

Perm< 2 >	cachedConjugate (const Perm< 2 > &q) const
	An alias for conjugate(), provided to assist with writing generic code.

constexpr Perm< 2 >	inverse () const
	Finds the inverse of this permutation.

Perm< 2 >	cachedInverse () const
	An alias for inverse(), provided to assist with writing generic code.

constexpr Perm< 2 >	pow (long exp) const
	Computes the given power of this permutation.

Perm< 2 >	cachedPow (long exp) const
	An alias for pow(), provided to assist with writing generic code.

constexpr int	order () const
	Returns the order of this permutation.

int	cachedOrder () const
	An alias for order(), provided to assist with writing generic code.

constexpr Perm< 2 >	reverse () const
	Finds the reverse of this permutation.

constexpr int	sign () const
	Determines the sign of this permutation.

constexpr int	operator[] (int source) const
	Determines the image of the given integer under this permutation.

constexpr int	pre (int image) const
	Determines the preimage of the given integer under this permutation.

constexpr bool	operator== (const Perm &) const =default
	Determines if this is equal to the given permutation.

constexpr int	compareWith (const Perm< 2 > &other) const
	Lexicographically compares the images of (0,1) under this and the given permutation.

constexpr bool	isIdentity () const
	Determines if this is the identity permutation.

Perm< 2 > &	operator++ ()
	A preincrement operator that changes this to be the next permutation in the array Perm<2>::Sn.

constexpr Perm< 2 >	operator++ (int)
	A postincrement operator that changes this to be the next permutation in the array Perm<2>::Sn.

constexpr std::strong_ordering	operator<=> (const Perm &) const =default
	Compares two permutations according to which appears earlier in the array Perm<2>::Sn.

std::string	str () const
	Returns a string representation of this permutation.

std::string	trunc (int len) const
	Returns a prefix of the string representation of this permutation, containing only the images of the first len integers.

void	tightEncode (std::ostream &out) const
	Writes the tight encoding of this permutation to the given output stream.

std::string	tightEncoding () const
	Returns the tight encoding of this permutation.

constexpr size_t	hash () const
	Hashes this permutation to a non-negative integer, allowing it to be used for keys in hash tables.

void	clear (unsigned from)
	Resets the images of all integers from from onwards to the identity map.

constexpr Index	SnIndex () const
	Returns the index of this permutation in the Perm<2>::Sn array.

constexpr Index	S2Index () const
	Returns the index of this permutation in the Perm<2>::Sn array.

constexpr Index	orderedSnIndex () const
	Returns the lexicographical index of this permutation.

constexpr Index	orderedS2Index () const
	Returns the lexicographical index of this permutation.

constexpr bool	isConjugacyMinimal () const
	Is this permutation minimal in its conjugacy class?

Static Public Member Functions
static constexpr void	precompute ()
	A do-nothing routine that assists with writing generic code.

static constexpr Perm< 2 >	fromPermCode (Code code)
	Creates a permutation from the given internal code.

static constexpr bool	isPermCode (Code code)
	Determines whether the given integer is a valid internal permutation code.

static constexpr Perm	rot (int i)
	Returns the ith rotation.

static Perm	rand (bool even=false)
	Returns a random permutation on two elements.

template<class URBG >
static Perm	rand (URBG &&gen, bool even=false)
	Returns a random permutation on two elements, using the given uniform random bit generator.

static Perm	tightDecoding (const std::string &enc)
	Reconstructs a permutation from its given tight encoding.

static Perm	tightDecode (std::istream &input)
	Reconstructs a permutation from its given tight encoding.

template<int k>
static constexpr Perm< 2 >	contract (Perm< k > p)
	Restricts a k-element permutation to an 2-element permutation, where k > 2.

Static Public Attributes
static constexpr int	degree = 2
	The degree of the underlying symmetric group; that is, the template parameter n.

static constexpr PermCodeType	codeType = PermCodeType::Index
	Indicates what type of internal permutation code is used by this instance of the Perm class template.

static constexpr Index	nPerms = 2
	The total number of permutations on two elements.

static constexpr Index	nPerms_1 = 1
	Deprecated constant holding the total number of permutations on one element.

static constexpr PermSn< 2, PermOrder::Sign >	Sn {}
	Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

static constexpr PermSn< 2, PermOrder::Sign >	S2 {}
	Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

static constexpr PermSn< 2, PermOrder::Lex >	orderedSn {}
	Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

static constexpr PermSn< 2, PermOrder::Lex >	orderedS2 {}
	Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

static constexpr detail::PermSubSn< 2, 1 >	S1 {}
	Deprecated array-like object that lists all possible permutations of one element.

static constexpr detail::PermSubSn< 2, 1 >	Sn_1 {}
	Deprecated alias for S1, which gives fast array-like access to all possible permutations of one element.

Protected Member Functions
constexpr	Perm (Code code)
	Creates a permutation from the given internal code.

Protected Attributes
Code	code_
	The internal code representing this permutation.

Friends
class	PermSn< 2, PermOrder::Sign >

class	PermSn< 2, PermOrder::Lex >

Detailed Description

Represents a permutation of {0,1}.

This is a specialisation of the generic Perm template: it is highly optimised, but also somewhat trivial (since there are only two possible permutations). It is provided simply to optimise the general Perm<n> template for this trivial case.

As with all Perm template classes, these objects are small enough to pass by value and swap with std::swap(), with no need for any specialised move operations or swap functions. Moreover, Perm<2> in particular is extremely fast to work with.

Each permutation has an internal code, which is a single native integer that is sufficient to reconstruct the permutation. Thus the internal code may be a useful means for passing permutation objects to and from the engine. For Perm<2>, the internal code is 0 for the identity permutation, or 1 for the (unique) non-identity permutation. This is consistent with the second-generation codes used in classes Perm<4>,...,Perm<7>.

You can iterate through all permutations using a range-based for loop over Sn, and this will be extremely fast in both C++ and Python:

for (auto p : Perm<2>::Sn) { ... }

regina::Perm< 2 >::Sn

static constexpr PermSn< 2, PermOrder::Sign > Sn

Gives fast access to all possible permutations of two elements, with support for both array-like inde...

Definition perm2.h:195

regina::Perm

Represents a permutation of {0,1,...,n-1}.

Definition cut.h:56

This behaviour does not generalise to the large permutation classes Perm<n> with n ≥ 8, which are not as tightly optimised: such range-based for loops are still supported for n ≥ 8 but will be significantly slower in Python than in C++. See the generic Perm class notes for further details.

To use this class, simply include the main permutation header maths/perm.h.

Warning: Every permutation class Perm<n> provides a transposition (i.e., pair swap) constructor Perm<n>(a,b). In addition, the specialised classes Perm<3>, Perm<4> and Perm<5> provide "list of images" constructors Perm<3>(a,b,c), Perm<4>(a,b,c,d) and Perm<5>(a,b,c,d,e). For Perm<2>, these two constructors would be indistinguishable (since both would take two integer arguments). Here Perm<2> takes an approach that is consistent with the generic Perm<n> class: Perm<2>(a,b) is interpreted as the transposition of a and b. In particular, Perm(0,1) is not the identity permutation.

Python: Since Python does not support templates, this class is made available under the name Perm2.

Member Typedef Documentation

◆ Code

using regina::Perm< 2 >::Code = uint8_t

Indicates the native unsigned integer type used to store the internal permutation code.

◆ Code2

using regina::Perm< 2 >::Code2 = Code

An alias for Code, indicating the native unsigned integer type used to store the internal permutation code.

This alias is provided to assist with generic programming, since permutation codes for Perm<2> are (and always have been) consistent with the second-generation permutation codes used with medium-sized permutation types ‘Perm<4..7>’, which represent indices into Sn.

◆ Index

using regina::Perm< 2 >::Index = int

Denotes a native signed integer type large enough to count all permutations on two elements.

In other words, this is a native signed integer type large enough to store (2!).

Constructor & Destructor Documentation

◆ Perm() [1/5]

regina::Perm< 2 >::Perm ( )

inlineconstexpr

Creates the identity permutation.

◆ Perm() [2/5]

regina::Perm< 2 >::Perm	(	int	a,
		int	b )

inlineconstexpr

Creates the transposition of a and b.

Note that a and b need not be distinct.

Precondition: a and b are in {0,1}.

Parameters

a	the element to switch with b.
b	the element to switch with a.

◆ Perm() [3/5]

regina::Perm< 2 >::Perm ( const std::array< int, 2 > & image )

inlineconstexpr

Creates a permutation mapping i to image[i] for each i = 0,1.

Precondition: The elements of image are 0 and 1 in some order.

Parameters

image the array of images.

◆ Perm() [4/5]

regina::Perm< 2 >::Perm ( const Perm< 2 > & cloneMe )

constexprdefault

Creates a permutation that is a clone of the given permutation.

Parameters

cloneMe the permutation to clone.

◆ Perm() [5/5]

regina::Perm< 2 >::Perm ( Code code )

inlineconstexprprotected

Creates a permutation from the given internal code.

Precondition: the given code is a valid permutation code; see isPermCode() for details.

Parameters

code	the internal code from which the new permutation will be created.

Member Function Documentation

◆ cachedComp() [1/2]

Perm< 2 > regina::Perm< 2 >::cachedComp ( const Perm< 2 > & q ) const

inline

An alias for the composition operator, provided to assist with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations. The only point of having cachedComp() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you should just use the composition operator instead.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using cachedComp(). (For Perm<2>, which does not use precomputation for its optimisations, precompute() does nothing.)

The permutation that is returned is the same as you would obtain by calling (*this) * q.

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedComp(). For Perm<2>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Parameters

q	the permutation to compose this with.

Returns: the composition of both permutations.

◆ cachedComp() [2/2]

Perm< 2 > regina::Perm< 2 >::cachedComp	(	const Perm< 2 > &	q,
		const Perm< 2 > &	r ) const

inline

Deprecated alias for using the composition operator twice, provided to assist with writing generic code.

The permutation that is returned is the same as you would obtain by calling (*this) * q * r.

Deprecated: The three-way cachedComp() was originally written to support conjugation. If you are indeed conjugating, then call cachedConjugate() instead; otherwise just call the two-way cachedComp() twice.

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedComp(). For Perm<2>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Parameters

q	the first permutation to compose this with.
r	the second permutation to compose this with.

Returns: the composition of both permutations.

◆ cachedConjugate()

Perm< 2 > regina::Perm< 2 >::cachedConjugate ( const Perm< 2 > & q ) const

inline

An alias for conjugate(), provided to assist with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations. The only point of having cachedConjugate() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you should just call conjugate() instead.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using cachedConjugate(). (For Perm<2>, which does not use precomputation for its optimisations, precompute() does nothing.)

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedConjugate(). For Perm<6>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Parameters

q	the permutation to conjugate this by.

Returns: the conjugate of this permutation by q.

◆ cachedInverse()

Perm< 2 > regina::Perm< 2 >::cachedInverse ( ) const

inline

An alias for inverse(), provided to assist with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations. The only point of having cachedInverse() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you should just call inverse() instead.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using cachedInverse(). (For Perm<2>, which does not use precomputation for its optimisations, precompute() does nothing.)

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedInverse(). For Perm<2>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Returns: the inverse of this permutation.

◆ cachedOrder()

int regina::Perm< 2 >::cachedOrder ( ) const

inline

An alias for order(), provided to assist with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations. The only point of having cachedOrder() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you should just call order() instead.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using cachedOrder(). (For Perm<2>, which does not use precomputation for its optimisations, precompute() does nothing.)

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedOrder(). For Perm<2>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Returns: the order of this permutation.

◆ cachedPow()

Perm< 2 > regina::Perm< 2 >::cachedPow ( long exp ) const

inline

An alias for pow(), provided to assist with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations. The only point of having cachedPow() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you should just call pow() instead.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using cachedPow(). (For Perm<2>, which does not use precomputation for its optimisations, precompute() does nothing.)

Precondition: You must have called precompute() at least once in the lifetime of this program before calling cachedPow(). For Perm<2>, precompute() does nothing; however, for other Perm<n> classes a failure to do this will almost certainly crash your program.

Parameters

exp	the exponent; this may be positive, zero or negative.

Returns: this permutation raised to the power of exp.

◆ clear()

void regina::Perm< 2 >::clear ( unsigned from )

Resets the images of all integers from from onwards to the identity map.

Specifically, for each i in the range from,...,1, this routine will ensure that image[i] == i. The images of 0,1,...,from-1 will not be altered.

Precondition: The images of from,...,1 are exactly from,...,1, but possibly in a different order.

Parameters

from	the first integer whose image should be reset. This must be between 0 and 2 inclusive.

◆ compareWith()

int regina::Perm< 2 >::compareWith ( const Perm< 2 > & other ) const

inlineconstexpr

Lexicographically compares the images of (0,1) under this and the given permutation.

Parameters

other the permutation with which to compare this.

Returns: -1 if this permutation produces a smaller image, 0 if the permutations are equal and 1 if this permutation produces a greater image.

◆ conjugate()

Perm< 2 > regina::Perm< 2 >::conjugate ( const Perm< 2 > & q ) const

inlineconstexpr

Computes the conjugate of this permutation by q.

Specifically, calling p.conjugate(q) is equivalent to computing q * p * q.inverse(). The resulting permutation will have the same cycle structure as p, but with the cycle elements translated according to q.

Parameters

q	the permutation to conjugate this by.

Returns: the conjugate of this permutation by q.

◆ contract()

template<int k>

static constexpr Perm< 2 > regina::Perm< 2 >::contract ( Perm< k > p )

staticconstexpr

Restricts a k-element permutation to an 2-element permutation, where k > 2.

The resulting permutation will map 0,1 to their respective images under p, and will ignore the "unused" images p[2],...,p[k-1].

Precondition: The given permutation maps 0,1 to 0,1 in some order.

Template Parameters

k	the number of elements for the input permutation; this must be strictly greater than 2.

Parameters

p	a permutation on k elements.

Returns: the same permutation restricted to a permutation on 2 elements.

◆ fromPermCode()

Perm< 2 > regina::Perm< 2 >::fromPermCode ( Code code )

inlinestaticconstexpr

Creates a permutation from the given internal code.

Precondition: the given code is a valid permutation code; see isPermCode() for details.

Parameters

code	the internal code for the new permutation.

Returns: the permutation represented by the given internal code.

◆ hash()

size_t regina::Perm< 2 >::hash ( ) const

inlineconstexpr

Hashes this permutation to a non-negative integer, allowing it to be used for keys in hash tables.

The implementation currently returns the internal permutation code (which for Perm<2> will always fit within a size_t). This implementation (and therefore the specific hash values obtained) is subject to change in future versions of Regina.

Python: For Python users, this function uses the standard Python name hash(). This allows permutations to be used as keys in Python dictionaries and sets.

Returns: The integer hash of this permutation.

◆ inverse()

Perm< 2 > regina::Perm< 2 >::inverse ( ) const

inlineconstexpr

Finds the inverse of this permutation.

Returns: the inverse of this permutation.

◆ isConjugacyMinimal()

bool regina::Perm< 2 >::isConjugacyMinimal ( ) const

inlineconstexpr

Is this permutation minimal in its conjugacy class?

Here "minimal" means that, amongst all its conjugates, this permutation has the smallest index in the array Perm<2>::Sn.

See Sn for further information on how permutations are indexed.

This routine is extremely fast for Perm<2>, since the answer is always true.

Returns: true if and only if this permutation is minimal in its conjugacy class.

◆ isIdentity()

bool regina::Perm< 2 >::isIdentity ( ) const

inlineconstexpr

Determines if this is the identity permutation.

This is true if and only if each of 0 and 1 is mapped to itself.

Returns: true if and only if this is the identity permutation.

◆ isPermCode()

bool regina::Perm< 2 >::isPermCode ( Code code )

inlinestaticconstexpr

Determines whether the given integer is a valid internal permutation code.

Valid permutation codes can be passed to setPermCode() or fromPermCode(), and are returned by permCode().

Parameters

code	the permutation code to test.

Returns: true if and only if the given code is a valid internal permutation code.

◆ operator*()

Perm< 2 > regina::Perm< 2 >::operator* ( const Perm< 2 > & q ) const

inlineconstexpr

Returns the composition of this permutation with the given permutation.

If this permutation is p, the resulting permutation will be p∘q, and will satisfy (p*q)[x] == p[q[x]].

Parameters

q	the permutation with which to compose this.

Returns: the composition of both permutations.

◆ operator++() [1/2]

Perm< 2 > & regina::Perm< 2 >::operator++ ( )

inline

A preincrement operator that changes this to be the next permutation in the array Perm<2>::Sn.

If this is the last such permutation then this will wrap around to become the first permutation in Perm<2>::Sn, which is the identity.

Python: Not present. The postincrement operator is present in Python as the member function inc().

Returns: a reference to this permutation after the increment.

◆ operator++() [2/2]

Perm< 2 > regina::Perm< 2 >::operator++ ( int )

inlineconstexpr

A postincrement operator that changes this to be the next permutation in the array Perm<2>::Sn.

If this is the last such permutation then this will wrap around to become the first permutation in Perm<2>::Sn, which is the identity.

Python: This routine is named inc() since python does not support the increment operator.

Returns: a copy of this permutation before the increment took place.

◆ operator<=>()

std::strong_ordering regina::Perm< 2 >::operator<=> ( const Perm< 2 > & ) const

constexprdefault

Compares two permutations according to which appears earlier in the array Perm<2>::Sn.

For the special case of permutations on two elements, this ordering is consistent with the ordering implied by compareWith() (but beware: for other permutation classes this is not true). Also, like all permutation classes, this ordering is consistent with the ordering implied by the ++ operators.

This generates all of the usual comparison operators, including <, <=, >, and >=.

Python: This spaceship operator x <=> y is not available, but the other comparison operators that it generates are available.

Returns: The result that indicates which permutation appears earlier in Sn.

◆ operator=()

Perm< 2 > & regina::Perm< 2 >::operator= ( const Perm< 2 > & cloneMe )

default

Sets this permutation to be equal to the given permutation.

Parameters

cloneMe the permutation whose value will be assigned to this permutation.

Returns: a reference to this permutation.

◆ operator==()

bool regina::Perm< 2 >::operator== ( const Perm< 2 > & ) const

constexprdefault

Determines if this is equal to the given permutation.

This is true if and only if both permutations have the same images for 0 and 1.

Returns: true if and only if this and the given permutation are equal.

◆ operator[]()

int regina::Perm< 2 >::operator[] ( int source ) const

inlineconstexpr

Determines the image of the given integer under this permutation.

Parameters

source the integer whose image we wish to find. This should be 0 or 1.

Returns: the image of source.

◆ order()

int regina::Perm< 2 >::order ( ) const

inlineconstexpr

Returns the order of this permutation.

In other words; this routine returns the smallest positive integer k for which the kth power of this permutation is the identity.

Returns: the order of this permutation.

◆ orderedS2Index()

Perm< 2 >::Index regina::Perm< 2 >::orderedS2Index ( ) const

inlineconstexpr

Returns the lexicographical index of this permutation.

This will be the index of this permutation in the Perm<2>::orderedSn array.

This is a dimension-specific alias for orderedSnIndex(). In general, for every n there will be a member function Perm<n>::orderedSnIndex(); however, these numerical aliases Perm<2>::orderedS2Index(), ..., Perm<7>::orderedS7Index() are only available for small n.

See orderedSn for further information on lexicographical ordering.

Returns: the lexicographical index of this permutation. This will be 0 or 1.

◆ orderedSnIndex()

Perm< 2 >::Index regina::Perm< 2 >::orderedSnIndex ( ) const

inlineconstexpr

Returns the lexicographical index of this permutation.

This will be the index of this permutation in the Perm<2>::orderedSn array.

See orderedSn for further information on lexicographical ordering.

Returns: the lexicographical index of this permutation. This will be 0 or 1.

◆ permCode()

Perm< 2 >::Code regina::Perm< 2 >::permCode ( ) const

inlineconstexpr

Returns the internal code representing this permutation.

Note that the internal code is sufficient to reproduce the entire permutation.

The code returned will be a valid permutation code as determined by isPermCode().

Returns: the internal code.

◆ pow()

Perm< 2 > regina::Perm< 2 >::pow ( long exp ) const

inlineconstexpr

Computes the given power of this permutation.

This routine runs in constant time.

Parameters

exp	the exponent; this may be positive, zero or negative.

Returns: this permutation raised to the power of exp.

◆ pre()

int regina::Perm< 2 >::pre ( int image ) const

inlineconstexpr

Determines the preimage of the given integer under this permutation.

Parameters

image the integer whose preimage we wish to find. This should be 0 or 1.

Returns: the preimage of image.

◆ precompute()

void regina::Perm< 2 >::precompute ( )

inlinestaticconstexpr

A do-nothing routine that assists with writing generic code.

This specialised Perm<2> class does not use precomputation for its optimisations, and so this precompute() function does nothing. The only point of having precompute() in Perm<2> is to make it easier to write generic code that works with Perm<n> for any n.

If you know you are only working with Perm<2>, you do not need to call this function at all.
If you are writing generic code, you must remember to call precompute() at least once in the lifetime of this program before using any of the optimised cachedXXX() functions, such as cachedComp(), cachedInverse(), and so on.

All Perm<n>::precompute() routines are thread-safe, and are harmless if called multiple times (since any call after the first will do nothing).

◆ rand() [1/2]

Perm< 2 > regina::Perm< 2 >::rand ( bool even = false )

inlinestatic

Returns a random permutation on two elements.

All permutations are returned with equal probability.

This routine is thread-safe, and uses RandomEngine for its random number generation.

Warning: This routine is expensive, since it locks and unlocks the mutex protecting Regina's global uniform random bit generator. If you are calling this many times in quick succession, consider creating a single RandomEngine object yourself and then calling rand(randomEngine.engine(), even).

Parameters

even	if `true`, then the resulting permutation is guaranteed to be even (which means, for a permutation on two elements, the resulting permutation must be the identity).

Returns: a random permutation.

◆ rand() [2/2]

template<class URBG >

static Perm regina::Perm< 2 >::rand	(	URBG &&	gen,
		bool	even = false )

static

Returns a random permutation on two elements, using the given uniform random bit generator.

All permutations are returned with equal probability.

The thread safety of this routine is of course dependent on the thread safety of your uniform random bit generator gen.

Template Parameters

URBG	A type which, once any references are removed, must adhere to the C++ UniformRandomBitGenerator concept.

Python: Not present. Python users are still able to use the non-thread-safe variant without the gen argument.

Parameters

gen	the source of randomness to use (e.g., one of the many options provided in the C++ standard `random` header).
even	if `true`, then the resulting permutation is guaranteed to be even (which means, for a permutation on two elements, the resulting permutation must be the identity).

Returns: a random permutation.

◆ reverse()

Perm< 2 > regina::Perm< 2 >::reverse ( ) const

inlineconstexpr

Finds the reverse of this permutation.

Here reverse means that we reverse the images of 0 and 1. In other words, if permutation q is the reverse of p, then p[i] == q[1 - i] for all i.

◆ rot()

Perm< 2 > regina::Perm< 2 >::rot ( int i )

inlinestaticconstexpr

Returns the ith rotation.

This maps k to k + i (mod 2) for all k.

Parameters

i	the image of 0; this must be 0 or 1.

Returns: the ith rotation.

◆ S2Index()

Perm< 2 >::Index regina::Perm< 2 >::S2Index ( ) const

inlineconstexpr

Returns the index of this permutation in the Perm<2>::Sn array.

This is a dimension-specific alias for SnIndex(). In general, for every n there will be a member function Perm<n>::SnIndex(); however, these numerical aliases Perm<2>::S2Index(), ..., Perm<7>::S7Index() are only available for small n.

See Sn for further information on how these permutations are indexed.

Returns: the index i for which this permutation is equal to Perm<2>::Sn[i]. This will be 0 or 1.

◆ setPermCode()

void regina::Perm< 2 >::setPermCode ( Code code )

inline

Sets this permutation to that represented by the given internal code.

Precondition: the given code is a valid permutation code; see isPermCode() for details.

Parameters

code	the internal code that will determine the new value of this permutation.

◆ sign()

int regina::Perm< 2 >::sign ( ) const

inlineconstexpr

Determines the sign of this permutation.

Returns: 1 if this permutation is even, or -1 if this permutation is odd.

◆ SnIndex()

Perm< 2 >::Index regina::Perm< 2 >::SnIndex ( ) const

inlineconstexpr

Returns the index of this permutation in the Perm<2>::Sn array.

See Sn for further information on how these permutations are indexed.

Returns: the index i for which this permutation is equal to Perm<2>::Sn[i]. This will be 0 or 1.

◆ str()

std::string regina::Perm< 2 >::str ( ) const

inline

Returns a string representation of this permutation.

The representation will consist of two adjacent digits representing the images of 0 and 1 respectively. An example of a string representation is 10.

Returns: a string representation of this permutation.

◆ tightDecode()

Perm< 2 > regina::Perm< 2 >::tightDecode ( std::istream & input )

inlinestatic

Reconstructs a permutation from its given tight encoding.

See the page on tight encodings for details.

The tight encoding will be read from the given input stream. If the input stream contains leading whitespace then it will be treated as an invalid encoding (i.e., this routine will throw an exception). The input stream may contain further data: if this routine is successful then the input stream will be left positioned immediately after the encoding, without skipping any trailing whitespace.

Tight encodings are fast to work with for small permutation classes (n ≤ 7), but slower for larger permutation classes (8 ≤ n ≤ 16). See tightEncoding() for further details.

Exceptions

InvalidInput The given input stream does not begin with a tight encoding of a 2-element permutation.

Python: Not present. Use tightDecoding() instead, which takes a string as its argument.

Parameters

input an input stream that begins with the tight encoding for a 2-element permutation.

Returns: the permutation represented by the given tight encoding.

◆ tightDecoding()

Perm< 2 > regina::Perm< 2 >::tightDecoding ( const std::string & enc )

inlinestatic

Reconstructs a permutation from its given tight encoding.

See the page on tight encodings for details.

The tight encoding will be given as a string. If this string contains leading whitespace or any trailing characters at all (including trailing whitespace), then it will be treated as an invalid encoding (i.e., this routine will throw an exception).

Tight encodings are fast to work with for small permutation classes (n ≤ 7), but slower for larger permutation classes (8 ≤ n ≤ 16). See tightEncoding() for further details.

Exceptions

InvalidArgument The given string is not a tight encoding of a 2-element permutation.

Parameters

enc	the tight encoding for a 2-element permutation.

Returns: the permutation represented by the given tight encoding.

◆ tightEncode()

void regina::Perm< 2 >::tightEncode ( std::ostream & out ) const

inline

Writes the tight encoding of this permutation to the given output stream.

See the page on tight encodings for details.

For all permutation classes Perm<n>, the tight encoding is based on the index into the full permutation group S_n. For smaller permutation classes (n ≤ 7), such encodings are very fast to work with since the S_n index is used as the internal permutation code. For larger permutation classes however (8 ≤ n ≤ 16), the S_n index requires some non-trivial work to compute.

Python: Not present. Use tightEncoding() instead, which returns a string.

Parameters

out	the output stream to which the encoded string will be written.

◆ tightEncoding()

std::string regina::Perm< 2 >::tightEncoding ( ) const

inline

Returns the tight encoding of this permutation.

See the page on tight encodings for details.

For all permutation classes Perm<n>, the tight encoding is based on the index into the full permutation group S_n. For smaller permutation classes (n ≤ 7), such encodings are very fast to work with since the S_n index is used as the internal permutation code. For larger permutation classes however (8 ≤ n ≤ 16), the S_n index requires some non-trivial work to compute.

Returns: the resulting encoded string.

◆ trunc()

std::string regina::Perm< 2 >::trunc ( int len ) const

inline

Returns a prefix of the string representation of this permutation, containing only the images of the first len integers.

Parameters

len	the length of the prefix required; this must be between 0 and 2 inclusive.

Returns: the corresponding prefix of the string representation of this permutation.

Member Data Documentation

◆ code_

Code regina::Perm< 2 >::code_

protected

The internal code representing this permutation.

◆ codeType

PermCodeType regina::Perm< 2 >::codeType = PermCodeType::Index

staticconstexpr

Indicates what type of internal permutation code is used by this instance of the Perm class template.

◆ degree

int regina::Perm< 2 >::degree = 2

staticconstexpr

The degree of the underlying symmetric group; that is, the template parameter n.

This compile-time constant allows the programmer to extract n from the type (e.g., when writing templated code).

◆ nPerms

Index regina::Perm< 2 >::nPerms = 2

staticconstexpr

The total number of permutations on two elements.

This is the size of the array Sn.

◆ nPerms_1

Index regina::Perm< 2 >::nPerms_1 = 1

staticconstexpr

Deprecated constant holding the total number of permutations on one element.

Deprecated: This is a trivial case: just use the constant 1 instead.

◆ orderedS2

PermSn<2, PermOrder::Lex> regina::Perm< 2 >::orderedS2 {}

staticconstexpr

Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

This is a dimension-specific alias for Perm<2>::orderedSn; see that member for further information. In general, for every n there will be a static member Perm<n>::orderedSn; however, these numerical aliases Perm<2>::orderedS2, ..., Perm<7>::orderedS7 are only available for small n.

◆ orderedSn

PermSn<2, PermOrder::Lex> regina::Perm< 2 >::orderedSn {}

staticconstexpr

Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

This array contains the same permutations in the same order as Sn, since for permutations of two elements, sign-based ordering and lexicographical ordering are the same (this is not true for Perm<n> when n ≥ 3).

See the documentation for Sn for further information on how to this object (since Sn and orderedSn are used in the same way).

◆ S1

detail::PermSubSn<2, 1> regina::Perm< 2 >::S1 {}

staticconstexpr

Deprecated array-like object that lists all possible permutations of one element.

Of course, this list is trivial: it contains just the identity permutation.

To access the permutation at index i, you simply use the square bracket operator: S1[i]. The index i must be 0. Unlike Sn, you cannot iterate over S1 in C++ (though you can still do this in Python).

In Regina 6.0.1 and earlier, this was a hard-coded C-style array; since Regina 7.0 it has changed type, but accessing elements as described above remains extremely fast. This is now a lightweight object, and is defined in the headers only; in particular, you cannot make a reference to it (but you can always make a copy).

Deprecated: Just use the identity permutation directly.

◆ S2

PermSn<2, PermOrder::Sign> regina::Perm< 2 >::S2 {}

staticconstexpr

Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

This is a dimension-specific alias for Perm<2>::Sn; see that member for further information. In general, for every n there will be a static member Perm<n>::Sn; however, these numerical aliases Perm<2>::S2, ..., Perm<7>::S7 are only available for small n.

Note that all small permutation classes (Perm<2>, ..., Perm<5>) have an S2 array: these all store the same two permutations in the same order (but of course using different data types).

◆ Sn

PermSn<2, PermOrder::Sign> regina::Perm< 2 >::Sn {}

staticconstexpr

Gives fast access to all possible permutations of two elements, with support for both array-like indexing and iteration.

To access the permutation at index i, you simply use the square bracket operator: Sn[i]. The index i must be between 0 and 1 inclusive.

You can also iterate over all permutations in Sn using a range-based for loop:

for (auto p : Perm<2>::Sn) { ... }

For this class (and all Perm<n> with n ≤ 7), such index-based access and iteration are both extremely fast.

The ordering is both sign-based and lexicographical (which means there is no distinction between Sn and orderedSn): the identity permutation (which is even) has index 0, and the unique non-identity permutation (which is odd) has index 1.

Therefore this array holds the same permutations in the same order as Perm<2>::orderedSn. Note however that for n ≥ 3, the arrays Perm<n>::Sn and Perm<n>::orderedSn are different: Sn alternates between even and odd permutations, whereas orderedSn accesses permutations in lexicographical order.

In Regina 6.0.1 and earlier, this was a hard-coded C-style array; since Regina 7.0 it has changed type, but accessing elements as described above remains extremely fast. This is now a lightweight object, and is defined in the headers only; in particular, you cannot make a reference to it (but you can always make a copy).

See the PermSn documentation for further details, including time complexity of lookup and iteration.

◆ Sn_1

detail::PermSubSn<2, 1> regina::Perm< 2 >::Sn_1 {}

staticconstexpr

Deprecated alias for S1, which gives fast array-like access to all possible permutations of one element.

See the S1 documentation for further information.

Deprecated: Just use the identity permutation directly.

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

maths/spec/perm2.h

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Code

◆ Code2

◆ Index

Constructor & Destructor Documentation

◆ Perm() [1/5]

◆ Perm() [2/5]

◆ Perm() [3/5]

◆ Perm() [4/5]

◆ Perm() [5/5]

Member Function Documentation

◆ cachedComp() [1/2]

◆ cachedComp() [2/2]

◆ cachedConjugate()

◆ cachedInverse()

◆ cachedOrder()

◆ cachedPow()

◆ clear()

◆ compareWith()

◆ conjugate()

◆ contract()

◆ fromPermCode()

◆ hash()

◆ inverse()

◆ isConjugacyMinimal()

◆ isIdentity()

◆ isPermCode()

◆ operator*()

◆ operator++() [1/2]

◆ operator++() [2/2]

◆ operator<=>()

◆ operator=()

◆ operator==()

◆ operator[]()

◆ order()

◆ orderedS2Index()

◆ orderedSnIndex()

◆ permCode()

◆ pow()

◆ pre()

◆ precompute()

◆ rand() [1/2]

◆ rand() [2/2]

◆ reverse()

◆ rot()

◆ S2Index()

◆ setPermCode()

◆ sign()

◆ SnIndex()

◆ str()

◆ tightDecode()

◆ tightDecoding()

◆ tightEncode()

◆ tightEncoding()

◆ trunc()

Member Data Documentation

◆ code_

◆ codeType

◆ degree

◆ nPerms

◆ nPerms_1

◆ orderedS2

◆ orderedSn

◆ S1

◆ S2

◆ Sn

◆ Sn_1