Regina Calculation Engine
Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | List of all members
regina::Perm< 2 > Class Template Reference


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

#include <maths/spec/perm2.h>

Public Types

typedef int Index
 Denotes a native signed integer type large enough to count all permutations on two elements. More...
 
typedef uint8_t Code
 Indicates the native unsigned integer type used to store the internal permutation code. More...
 

Public Member Functions

 Perm ()
 Creates the identity permutation. More...
 
 Perm (int a, int b)
 Creates the transposition of a and b. More...
 
 Perm (const int *image)
 
Creates a permutation mapping i to image[i] for each i = 0,1. More...
 
 Perm (const int *a, const int *b)
 
Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively. More...
 
 Perm (const Perm< 2 > &cloneMe)=default
 Creates a permutation that is a clone of the given permutation. More...
 
Code permCode () const
 Returns the internal code representing this permutation. More...
 
void setPermCode (Code code)
 Sets this permutation to that represented by the given internal code. More...
 
Perm< 2 > & operator= (const Perm< 2 > &cloneMe)=default
 Sets this permutation to be equal to the given permutation. More...
 
Perm< 2 > operator* (const Perm< 2 > &q) const
 Returns the composition of this permutation with the given permutation. More...
 
Perm< 2 > inverse () const
 Finds the inverse of this permutation. More...
 
Perm< 2 > reverse () const
 Finds the reverse of this permutation. More...
 
int sign () const
 Determines the sign of this permutation. More...
 
int operator[] (int source) const
 Determines the image of the given integer under this permutation. More...
 
int preImageOf (int image) const
 Determines the preimage of the given integer under this permutation. More...
 
bool operator== (const Perm< 2 > &other) const
 Determines if this is equal to the given permutation. More...
 
bool operator!= (const Perm< 2 > &other) const
 Determines if this differs from the given permutation. More...
 
int compareWith (const Perm< 2 > &other) const
 Lexicographically compares the images of (0,1) under this and the given permutation. More...
 
bool isIdentity () const
 Determines if this is the identity permutation. More...
 
Index index () const
 Returns the lexicographical index of this permutation. More...
 
std::string str () const
 Returns a string representation of this permutation. More...
 
std::string trunc (unsigned len) const
 Returns a prefix of the string representation of this permutation, containing only the images of the first len integers. More...
 
void clear (unsigned from)
 Resets the images of all integers from from onwards to the identity map. More...
 
int S2Index () const
 Returns the index of this permutation in the Perm<2>::S2 array. More...
 
int SnIndex () const
 Returns the index of this permutation in the Perm<2>::S2 array. More...
 
int orderedS2Index () const
 Returns the index of this permutation in the Perm<2>::orderedS2 array. More...
 
int orderedSnIndex () const
 Returns the index of this permutation in the Perm<2>::orderedS2 array. More...
 
template<class URBG >
Perm< 2 > rand (URBG &&gen, bool even)
 

Static Public Member Functions

static Perm< 2 > fromPermCode (Code code)
 Creates a permutation from the given internal code. More...
 
static bool isPermCode (Code code)
 Determines whether the given integer is a valid internal permutation code. More...
 
static Perm atIndex (Index i)
 Returns the ith permutation on two elements, where permutations are numbered lexicographically beginning at 0. More...
 
static Perm rand (bool even=false)
 Returns a random permutation on two elements. More...
 
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. More...
 
template<int k>
static Perm< 2 > contract (Perm< k > p)
 Restricts a k-element permutation to an 2-element permutation, where k > 2. More...
 

Static Public Attributes

static const Index nPerms = 2
 The total number of permutations on two elements. More...
 
static const Index nPerms_1 = 1
 The total number of permutations on one element. More...
 
static const Perm< 2 > S2 [2]
 Contains all possible permutations of two elements. More...
 
static const Perm< 2 > * Sn
 A dimension-agnostic alias for Perm<2>::S2. More...
 
static const unsigned invS2 [2]
 Contains the inverses of the permutations in the array S2. More...
 
static const unsigned * invSn
 A dimension-agnostic alias for Perm<2>::invS2. More...
 
static const Perm< 2 > * orderedS2
 Contains all possible permutations of two elements in lexicographical order. More...
 
static const Perm< 2 > * orderedSn
 A dimension-agnostic alias for Perm<2>::orderedS2. More...
 
static const Perm< 2 > * S1
 Contains all possible permutations of one element. More...
 
static const Perm< 2 > * Sn_1
 A dimension-agnostic alias for Perm<2>::S1. More...
 

Detailed Description

template<>
class regina::Perm< 2 >


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 about by value instead of by reference. 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.

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

typedef uint8_t regina::Perm< 2 >::Code

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

◆ Index

typedef int regina::Perm< 2 >::Index

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 ( )
inline

Creates the identity permutation.

◆ Perm() [2/5]

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

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
athe element to switch with b.
bthe element to switch with a.

◆ Perm() [3/5]

regina::Perm< 2 >::Perm ( const int *  image)
inline


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

Precondition
The array image contains two elements, which are 0 and 1 in some order.
Python
Not present.
Parameters
imagethe array of images.

◆ Perm() [4/5]

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


Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively.

Precondition
Both arrays a and b contain two elements, which are 0 and 1 in some order.
Python
Not present.
Parameters
athe array of preimages; this must have length 2.
bthe corresponding array of images; this must also have length 2.

◆ Perm() [5/5]

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

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

Parameters
cloneMethe permutation to clone.

Member Function Documentation

◆ atIndex()

Perm< 2 > regina::Perm< 2 >::atIndex ( Index  i)
inlinestatic

Returns the ith permutation on two elements, where permutations are numbered lexicographically beginning at 0.

Lexicographical ordering treats each permutation p as the pair (p[0], p[1]).

The return value will be identical to orderedS2[i].

Parameters
ithe lexicographical index of the permutation; this must be 0 or 1.
Returns
the ith permutation.

◆ 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
fromthe 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
inline

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

Parameters
otherthe 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.

◆ contract()

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

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
kthe number of elements for the input permutation; this must be strictly greater than 2.
Parameters
pa permutation on k elements.
Returns
the same permutation restricted to a permutation on 2 elements.

◆ fromPermCode()

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

Creates a permutation from the given internal code.

Precondition
the given code is a valid permutation code; see isPermCode() for details.
Parameters
codethe internal code for the new permutation.
Returns
the permutation represented by the given internal code.

◆ index()

Perm< 2 >::Index regina::Perm< 2 >::index ( ) const
inline

Returns the lexicographical index of this permutation.

This indicates where this permutation sits within a full lexicographical ordering of all 2! permutations on two elements.

Lexicographical ordering treats each permutation p as the pair (p[0], p[1]). That is, the identity permutation has index 0, and the (unique) non-identity permutation has index 1.

This routine is identical to orderedS2Index().

Returns
the index of this permutation, which will be 0 or 1.

◆ inverse()

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

Finds the inverse of this permutation.

Returns
the inverse of this permutation.

◆ isIdentity()

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

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)
inlinestatic

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().

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

◆ operator!=()

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

Determines if this differs from the given permutation.

This is true if and only if the two permutations have different images for at least one of 0 or 1.

Parameters
otherthe permutation with which to compare this.
Returns
true if and only if this and the given permutation differ.

◆ operator*()

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

Returns the composition of this permutation with the given permutation.

If this permutation is p, the resulting permutation will be p o q, satisfying (p*q)[x] == p[q[x]].

Parameters
qthe permutation with which to compose this.
Returns
the composition of both permutations.

◆ operator=()

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

Sets this permutation to be equal to the given permutation.

Parameters
cloneMethe permutation whose value will be assigned to this permutation.
Returns
a reference to this permutation.

◆ operator==()

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

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.

Parameters
otherthe permutation with which to compare this.
Returns
true if and only if this and the given permutation are equal.

◆ operator[]()

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

Determines the image of the given integer under this permutation.

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

◆ orderedS2Index()

int regina::Perm< 2 >::orderedS2Index ( ) const
inline

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

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

◆ orderedSnIndex()

int regina::Perm< 2 >::orderedSnIndex ( ) const
inline

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

This is a dimension-agnostic alias for orderedS2Index().

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

◆ permCode()

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

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.

◆ preImageOf()

int regina::Perm< 2 >::preImageOf ( int  image) const
inline

Determines the preimage of the given integer under this permutation.

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

◆ 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
evenif 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
URBGA type which, once any references are removed, must adhere to the C++ UniformRandomBitGenerator concept.
Python
Not present, though the non-thread-safe variant without the gen argument is available.
Parameters
genthe source of randomness to use (e.g., one of the many options provided in the C++ standard random header).
evenif 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
inline

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.

◆ S2Index()

int regina::Perm< 2 >::S2Index ( ) const
inline

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

Returns
the index i for which this permutation is equal to Perm<2>::S2[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
codethe internal code that will determine the new value of this permutation.

◆ sign()

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

Determines the sign of this permutation.

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

◆ SnIndex()

int regina::Perm< 2 >::SnIndex ( ) const
inline

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

This is a dimension-agnostic alias for S2Index().

Returns
the index i for which this permutation is equal to Perm<2>::S2[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.

◆ trunc()

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

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

Parameters
lenthe 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

◆ invS2

const unsigned regina::Perm< 2 >::invS2[2]
static

Contains the inverses of the permutations in the array S2.

Specifically, the inverse of permutation S2[i] is the permutation S2[ invS2[i] ].

This array is provided for consistency with larger permutation classes; of course, for permutations of two elements, the inverse of p is always p itself.

◆ invSn

const unsigned* regina::Perm< 2 >::invSn
static

A dimension-agnostic alias for Perm<2>::invS2.

In general, for each K the class PermK will define an alias invSn that references the list of all permutations PermK::invSK.

◆ nPerms

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

The total number of permutations on two elements.

This is the size of the array Sn.

◆ nPerms_1

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

The total number of permutations on one element.

This is the size of the array Sn_1.

◆ orderedS2

const Perm<2>* regina::Perm< 2 >::orderedS2
static

Contains all possible permutations of two elements in lexicographical order.

This is identical to the array Perm<2>::S2, and in fact orderedS2 and S2 are pointers to the same array in memory. Note however that for n ≥ 3, the arrays Perm<n>::Sn and Perm<n>::orderedSn are different: Sn alternates between even and odd permutations, and orderedSn stores permutations in lexicograpical order.

◆ orderedSn

const Perm<2>* regina::Perm< 2 >::orderedSn
static

A dimension-agnostic alias for Perm<2>::orderedS2.

In general, for each K the class PermK will define an alias orderedSn that references the list of all permutations PermK::orderedSK.

◆ S1

const Perm<2>* regina::Perm< 2 >::S1
static

Contains all possible permutations of one element.

In each permutation, 1 maps to 1.

Of course, this array is trivial: it contains just the identity permutation. This array is provided for consistency with larger permutation classes Perm<n>.

Note that, as an implementation detail, the arrays S1 and S2 point to the same location in memory (however, they are treated as arrays of different lengths).

◆ S2

const Perm<2> regina::Perm< 2 >::S2[2]
static

Contains all possible permutations of two elements.

The identity permutation has index 0, and the non-identity permutation has index 1. As a result, S2[i] is an even permutation if and only if i is even.

For all permutation classes (Perm<2>, Perm<3> and so on), the S2 array stores the same permutations in the same order (but of course using different data types).

◆ Sn

const Perm<2>* regina::Perm< 2 >::Sn
static

A dimension-agnostic alias for Perm<2>::S2.

In general, for each K the class PermK will define an alias Sn that references the list of all permutations PermK::SK.

◆ Sn_1

const Perm<2>* regina::Perm< 2 >::Sn_1
static

A dimension-agnostic alias for Perm<2>::S1.

In general, for each K the class PermK will define an alias Sn_1 that references the list of all permutations PermK::S(K-1).


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

Copyright © 1999-2021, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).