Regina Calculation Engine
|
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... | |
Perm & | operator= (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... | |
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.
n | the number of objects being permuted. This must be between 2 and 16 inclusive. |