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

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

#include <maths/perm.h>

Public Types

typedef IntOfMinSize<(imageBits *n+7)/8 >::type Index
 Denotes a native signed integer type large enough to count all permutations on n elements. More...
 
typedef IntOfMinSize<(imageBits *n+7)/8 >::utype 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 0 ≤ i < n. More...
 
 Perm (const int *a, const int *b)
 Creates a permutation mapping (a[0], ..., a[n-1]) to (b[0], ..., b[n-1]) respectively. More...
 
 Perm (const Perm< n > &cloneMe)
 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...
 
Permoperator= (const Perm &cloneMe)
 Sets this permutation to be equal to the given permutation. More...
 
Perm operator* (const Perm &q) const
 Returns the composition of this permutation with the given permutation. More...
 
Perm inverse () const
 Finds the inverse of this permutation. More...
 
Perm 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 &other) const
 Determines if this is equal to the given permutation. More...
 
bool operator!= (const Perm &other) const
 Determines if this differs from the given permutation. More...
 
int compareWith (const Perm &other) const
 Lexicographically compares the images of (0,1,...,n-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...
 

Static Public Member Functions

static Perm fromPermCode (Code code)
 Creates a permutation from the given internal code. More...
 
static bool isPermCode (Code newCode)
 Determines whether the given integer is a valid internal permutation code. More...
 
static Perm atIndex (Index i)
 Returns the ith permutation on n elements, where permutations are numbered lexicographically beginning at 0. More...
 
static Perm rand ()
 Returns a random permutation on n elements. More...
 
template<int k>
static Perm extend (Perm< k > p)
 Extends a k-element permutation to an n-element permutation, where 2 ≤ k < n. More...
 
template<int k>
static Perm contract (Perm< k > p)
 Restricts a k-element permutation to an n-element permutation, where k > n. More...
 

Static Public Attributes

static constexpr int imageBits = regina::bitsRequired(n)
 Indicates the number of bits used by the permutation code to store the image of a single integer. More...
 
static constexpr Index nPerms = factorial(n)
 The total number of permutations on n elements. More...
 
static constexpr Index nPerms_1 = factorial(n-1)
 The total number of permutations on n-1 elements. More...
 

Detailed Description

template<int n>
class regina::Perm< n >

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

Amongst other things, such permutations are used to describe simplex gluings in (n-1)-manifold triangulations.

Perm objects are small enough to pass about by value instead of by reference. The trade-off is that, for this to be possible, the Perm template class can only work with n ≤ 16.

Each permutation has an internal code, which is a single native integer that is sufficient to reconstruct the entire permutation. Thus the internal code may be a useful means for passing permutation objects to and from the engine. These codes are constructed as follows:

For n = 2,...,5 (which appear throughout 2-, 3- and 4-manifold triangulations), this template is specialised: the code is highly optimised and also offers some extra functionality.

Python:
Python does not support templates. For each n = 2,...,16, this class is available in Python under the corresponding name Perm2, Perm3, ..., Perm16.
Template Parameters
nthe number of objects being permuted. This must be between 2 and 16 inclusive.

Member Typedef Documentation

◆ Code

template<int n>
typedef IntOfMinSize<(imageBits * n + 7) / 8>::utype regina::Perm< n >::Code

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

This typedef is present for all values of n, though its precise size depends on how the permutation code is constructed. In particular, this type is defined differently for n ≤ 4 than for n ≥ 5.

◆ Index

template<int n>
typedef IntOfMinSize<(imageBits * n + 7) / 8>::type regina::Perm< n >::Index

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

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

Constructor & Destructor Documentation

◆ Perm() [1/5]

template<int n>
regina::Perm< n >::Perm ( )
inline

Creates the identity permutation.

◆ Perm() [2/5]

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

Creates the transposition of a and b.

Note that a and b need not be distinct.

Precondition
0 ≤ a,b < n.
Parameters
athe element to switch with b.
bthe element to switch with a.

◆ Perm() [3/5]

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

Creates a permutation mapping i to image[i] for each 0 ≤ i < n.

Precondition
The array image contains n elements, which are 0,...,n-1 in some order.
Parameters
imagethe array of images.

◆ Perm() [4/5]

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

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

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

◆ Perm() [5/5]

template<int n>
regina::Perm< n >::Perm ( const Perm< n > &  cloneMe)
inline

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

Parameters
cloneMethe permutation to clone.

Member Function Documentation

◆ atIndex()

template<int n>
Perm< n > regina::Perm< n >::atIndex ( Index  i)
static

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

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

Parameters
ithe lexicographical index of the permutation; this must be between 0 and n!-1 inclusive.
Returns
the ith permutation.

◆ clear()

template<int n>
void regina::Perm< n >::clear ( unsigned  from)

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

Specifically, for each i in the range from,...,n-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,...,n-1 are exactly from,...,n-1, but possibly in a different order.
Parameters
fromthe first integer whose image should be reset. This must be between 0 and n inclusive.

◆ compareWith()

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

Lexicographically compares the images of (0,1,...,n-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 n>
template<int k>
static Perm regina::Perm< n >::contract ( Perm< k >  p)
static

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

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

Precondition
The given permutation maps 0,...,n-1 to 0,...,n-1 in some order.
Template Parameters
kthe number of elements for the input permutation; this must be strictly greater than n.
Parameters
pa permutation on k elements.
Returns
the same permutation restricted to a permutation on n elements.

◆ extend()

template<int n>
template<int k>
static Perm regina::Perm< n >::extend ( Perm< k >  p)
static

Extends a k-element permutation to an n-element permutation, where 2 ≤ k < n.

The resulting permutation will map 0,...,k-1 to their respective images under p, and will map the "unused" elements k,...,n-1 to themselves.

Template Parameters
kthe number of elements for the input permutation; this must be at least 2, and strictly less than n.
Parameters
pa permutation on k elements.
Returns
the same permutation expressed as a permutation on n elements.

◆ fromPermCode()

template<int n>
Perm< n > regina::Perm< n >::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 reprsented by the given internal code.

◆ index()

template<int n>
Perm< n >::Index regina::Perm< n >::index ( ) const

Returns the lexicographical index of this permutation.

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

Lexicographical ordering treats each permutation p as the n-tuple (p[0], p[1], ..., p[n-1]). In particular, the identity permutation has index 0, and the "reverse" permutation (which maps each i to n-i-1) has index n!-1.

Returns
the index of this permutation, which will be between 0 and n!-1 inclusive.

◆ inverse()

template<int n>
Perm< n > regina::Perm< n >::inverse ( ) const
inline

Finds the inverse of this permutation.

Returns
the inverse of this permutation.

◆ isIdentity()

template<int n>
bool regina::Perm< n >::isIdentity ( ) const
inline

Determines if this is the identity permutation.

This is true if and only if every integer 0 ≤ i < n is mapped to itself.

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

◆ isPermCode()

template<int n>
bool regina::Perm< n >::isPermCode ( Code  newCode)
static

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!=()

template<int n>
bool regina::Perm< n >::operator!= ( const Perm< n > &  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 some 0 ≤ i < n.

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

◆ operator*()

template<int n>
Perm< n > regina::Perm< n >::operator* ( const Perm< n > &  q) const
inline

Returns the composition of this permutation with the given permutation.

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

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

◆ operator=()

template<int n>
Perm< n > & regina::Perm< n >::operator= ( const Perm< n > &  cloneMe)
inline

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

template<int n>
bool regina::Perm< n >::operator== ( const Perm< n > &  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 all 0 ≤ i < n.

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

◆ operator[]()

template<int n>
int regina::Perm< n >::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 between 0 and n-1 inclusive.
Returns
the image of source.

◆ permCode()

template<int n>
Perm< n >::Code regina::Perm< n >::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()

template<int n>
int regina::Perm< n >::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 between 0 and n-1 inclusive.
Returns
the preimage of image.

◆ rand()

template<int n>
Perm< n > regina::Perm< n >::rand ( )
static

Returns a random permutation on n elements.

All permutations are returned with equal probability.

The implementation uses the C standard ::rand() function for its random number generation.

Returns
a random permutation.

◆ reverse()

template<int n>
Perm< n > regina::Perm< n >::reverse ( ) const
inline

Finds the reverse of this permutation.

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

◆ setPermCode()

template<int n>
void regina::Perm< n >::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()

template<int n>
int regina::Perm< n >::sign ( ) const

Determines the sign of this permutation.

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

◆ str()

template<int n>
std::string regina::Perm< n >::str ( ) const

Returns a string representation of this permutation.

The representation will consist of n adjacent digits representing the images of 0,...,n-1 respectively. If n > 10, then lower-case hexadecimal digits will be used.

An example of a string representation for n = 5 is 30421.

Returns
a string representation of this permutation.

◆ trunc()

template<int n>
std::string regina::Perm< n >::trunc ( unsigned  len) const

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 n inclusive.
Returns
the corresponding prefix of the string representation of this permutation.

Member Data Documentation

◆ imageBits

template<int n>
constexpr int regina::Perm< n >::imageBits = regina::bitsRequired(n)
static

Indicates the number of bits used by the permutation code to store the image of a single integer.

This constant refers to the "image packing" codes that are used for n ≥ 5, as described in the Perm class notes. For n ≤ 4 the permutation codes are constructed in a different way, and so this constant is not present.

The full permutation code packs n such images together, and so uses n * imageBits bits in total.

◆ nPerms

template<int n>
constexpr Perm< n >::Index regina::Perm< n >::nPerms = factorial(n)
static

The total number of permutations on n elements.

This is the size of the symmetric group Sn.

◆ nPerms_1

template<int n>
constexpr Perm< n >::Index regina::Perm< n >::nPerms_1 = factorial(n-1)
static

The total number of permutations on n-1 elements.

This is the size of the symmetric group Sn-1.


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

Copyright © 1999-2016, 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).