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)=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...
 
Permoperator= (const Perm &cloneMe)=default
 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...
 
template<class URBG >
Perm< n > rand (URBG &&gen, bool even)
 

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 (bool even=false)
 Returns a random permutation on n elements. More...
 
template<class URBG >
static Perm rand (URBG &&gen, bool even=false)
 Returns a random permutation on n elements, using the given uniform random bit generator. 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:\n 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.

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

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