Regina Calculation Engine
|
Represents a permutation of {0,1,...,n-1}. More...
#include <maths/nperm.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 | |
NPerm () | |
Creates the identity permutation. More... | |
NPerm (int a, int b) | |
Creates the transposition of a and b. More... | |
NPerm (const int *image) | |
Creates a permutation mapping i to image[i] for each 0 ≤ i < n. More... | |
NPerm (const int *a, const int *b) | |
Creates a permutation mapping (a[0], ..., a[n-1]) to (b[0], ..., b[n-1]) respectively. More... | |
NPerm (const NPerm< 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... | |
REGINA_DEPRECATED Code | getPermCode () const |
Deprecated routine that returns the internal code representing this permutation. More... | |
void | setPermCode (Code code) |
Sets this permutation to that represented by the given internal code. More... | |
NPerm & | operator= (const NPerm &cloneMe) |
Sets this permutation to be equal to the given permutation. More... | |
NPerm | operator* (const NPerm &q) const |
Returns the composition of this permutation with the given permutation. More... | |
NPerm | inverse () const |
Finds the inverse of this permutation. More... | |
NPerm | 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 NPerm &other) const |
Determines if this is equal to the given permutation. More... | |
bool | operator!= (const NPerm &other) const |
Determines if this differs from the given permutation. More... | |
int | compareWith (const NPerm &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... | |
Static Public Member Functions | |
static NPerm | 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 NPerm | atIndex (Index i) |
Returns the ith permutation on n elements, where permutations are numbered lexicographically beginning at 0. More... | |
static NPerm | rand () |
Returns a random permutation on n elements. More... | |
template<int k> | |
static NPerm | extend (NPerm< k > p) |
Extends a k-element permutation to an n-element permutation, where 2 ≤ k < n. More... | |
template<int k> | |
static NPerm | contract (NPerm< 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.
NPerm objects are small enough to pass about by value instead of by reference. The trade-off is that, for this to be possible, the NPerm 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. You will need to include the corresponding header(s) from nperm2.h, ..., nperm5.h to use these specialised classes; otherwise any code that uses NPerm<2>, ..., NPerm<5> will not compile. For convenience, the respective typedefs NPerm2, ..., NPerm5 are also available for these classes.
n | the number of objects being permuted. This must be between 2 and 16 inclusive. |
typedef IntOfMinSize<(imageBits * n + 7) / 8>::utype regina::NPerm< 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.
typedef IntOfMinSize<(imageBits * n + 7) / 8>::type regina::NPerm< 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!).
|
inline |
Creates the identity permutation.
|
inline |
Creates the transposition of a and b.
Note that a and b need not be distinct.
a | the element to switch with b. |
b | the element to switch with a. |
|
inline |
Creates a permutation mapping i to image[i] for each 0 ≤ i < n.
image | the array of images. |
|
inline |
Creates a permutation mapping (a[0], ..., a[n-1]) to (b[0], ..., b[n-1]) respectively.
a | the array of preimages; this must have length n. |
b | the corresponding array of images; this must also have length n. |
|
inline |
Creates a permutation that is a clone of the given permutation.
cloneMe | the permutation to clone. |
|
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]).
i | the lexicographical index of the permutation; this must be between 0 and n!-1 inclusive. |
int regina::NPerm< n >::compareWith | ( | const NPerm< n > & | other | ) | const |
Lexicographically compares the images of (0,1,...,n-1) under this and the given permutation.
other | the permutation with which to compare this. |
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].
k | the number of elements for the input permutation; this must be strictly greater than n. |
p | a permutation on k elements. |
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.
k | the number of elements for the input permutation; this must be at least 2, and strictly less than n. |
p | a permutation on k elements. |
|
inlinestatic |
Creates a permutation from the given internal code.
code | the internal code for the new permutation. |
|
inline |
Deprecated routine that returns the internal code representing this permutation.
NPerm< n >::Index regina::NPerm< 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.
|
inline |
Finds the inverse of this permutation.
|
inline |
Determines if this is the identity permutation.
This is true if and only if every integer 0 ≤ i < n is mapped to itself.
true
if and only if this is the identity permutation.
|
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().
true
if and only if the given code is a valid internal permutation code.
|
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.
other | the permutation with which to compare this. |
true
if and only if this and the given permutation differ.
|
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]]
.
q | the permutation to compose this with. |
|
inline |
Sets this permutation to be equal to the given permutation.
cloneMe | the permutation whose value will be assigned to this permutation. |
|
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.
other | the permutation with which to compare this. |
true
if and only if this and the given permutation are equal.
|
inline |
Determines the image of the given integer under this permutation.
source | the integer whose image we wish to find. This should be between 0 and n-1 inclusive. |
|
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().
|
inline |
Determines the preimage of the given integer under this permutation.
image | the integer whose preimage we wish to find. This should be between 0 and n-1 inclusive. |
|
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.
|
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.
|
inline |
Sets this permutation to that represented by the given internal code.
code | the internal code that will determine the new value of this permutation. |
int regina::NPerm< n >::sign | ( | ) | const |
Determines the sign of this permutation.
std::string regina::NPerm< 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
.
std::string regina::NPerm< n >::trunc | ( | unsigned | len | ) | const |
Returns a prefix of the string representation of this permutation, containing only the images of the first len integers.
len | the length of the prefix required; this must be between 0 and n inclusive. |
|
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 NPerm 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.
|
static |
The total number of permutations on n elements.
This is the size of the symmetric group Sn.
|
static |
The total number of permutations on n-1 elements.
This is the size of the symmetric group Sn-1.