Regina Calculation Engine
|
Represents a permutation of {0,1,2,3}.
More...
#include <maths/spec/perm4.h>
Public Types | |
typedef int | Index |
Denotes a native signed integer type large enough to count all permutations on four 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 (int a, int b, int c, int d) | |
Creates a permutation mapping (0,1,2,3) to (a,b,c,d) respectively. More... | |
Perm (const int *image) | |
Creates a permutation mapping i to image[i] for each i = 0,1,2,3. More... | |
Perm (const int *a, const int *b) | |
Creates a permutation mapping (a[0], ..., a[3]) to (b[0], ..., b[3]) respectively. More... | |
Perm (int a0, int a1, int b0, int b1, int c0, int c1, int d0, int d1) | |
Creates a permutation mapping (a0,b0,c0,d0) to (a1,b1,c1,d1) respectively. More... | |
Perm (const Perm< 4 > &cloneMe)=default | |
Creates a permutation that is a clone of the given permutation. More... | |
Code | permCode () const |
Returns the first-generation code representing this permutation. More... | |
Code | permCode2 () const |
Returns the second-generation code representing this permutation. More... | |
void | setPermCode (Code code) |
Sets this permutation to that represented by the given first-generation permutation code. More... | |
void | setPermCode2 (Code code) |
Sets this permutation to that represented by the given second-generation permutation code. More... | |
Perm< 4 > & | operator= (const Perm< 4 > &cloneMe)=default |
Sets this permutation to be equal to the given permutation. More... | |
Perm< 4 > | operator* (const Perm< 4 > &q) const |
Returns the composition of this permutation with the given permutation. More... | |
Perm< 4 > | inverse () const |
Finds the inverse of this permutation. More... | |
Perm< 4 > | 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< 4 > &other) const |
Determines if this is equal to the given permutation. More... | |
bool | operator!= (const Perm< 4 > &other) const |
Determines if this differs from the given permutation. More... | |
int | compareWith (const Perm< 4 > &other) const |
Lexicographically compares the images of (0,1,2,3) 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... | |
std::string | trunc2 () const |
Returns a string representation of this permutation with only the images of 0 and 1. More... | |
std::string | trunc3 () const |
Returns a string representation of this permutation with only the images of 0, 1 and 2 included. More... | |
void | clear (unsigned from) |
Resets the images of all integers from from onwards to the identity map. More... | |
int | S4Index () const |
Returns the index of this permutation in the Perm<4>::S4 array. More... | |
int | SnIndex () const |
Returns the index of this permutation in the Perm<4>::S4 array. More... | |
REGINA_INLINE_REQUIRED int | orderedS4Index () const |
Returns the index of this permutation in the Perm<4>::orderedS4 array. More... | |
int | orderedSnIndex () const |
Returns the index of this permutation in the Perm<4>::orderedS4 array. More... | |
template<class URBG > | |
Perm< 4 > | rand (URBG &&gen, bool even) |
Static Public Member Functions | |
static Perm< 4 > | fromPermCode (Code code) |
Creates a permutation from the given first-generation permutation code. More... | |
static Perm< 4 > | fromPermCode2 (Code code) |
Creates a permutation from the given second-generation permutation code. More... | |
static bool | isPermCode (Code code) |
Determines whether the given character is a valid first-generation permutation code. More... | |
static bool | isPermCode2 (Code code) |
Determines whether the given character is a valid second-generation permutation code. More... | |
static Perm | atIndex (Index i) |
Returns the ith permutation on four elements, where permutations are numbered lexicographically beginning at 0. More... | |
static Perm | rand (bool even=false) |
Returns a random permutation on four elements. More... | |
template<class URBG > | |
static Perm | rand (URBG &&gen, bool even=false) |
Returns a random permutation on four elements, using the given uniform random bit generator. More... | |
template<int k> | |
static Perm< 4 > | extend (Perm< k > p) |
Extends a k-element permutation to a 4-element permutation, where 2 ≤ k < 4. More... | |
template<int k> | |
static Perm< 4 > | contract (Perm< k > p) |
Restricts a k-element permutation to an 4-element permutation, where k > 4. More... | |
Static Public Attributes | |
static const Index | nPerms = 24 |
The total number of permutations on four elements. More... | |
static const Index | nPerms_1 = 6 |
The total number of permutations on three elements. More... | |
static const Perm< 4 > | S4 [24] |
Contains all possible permutations of four elements. More... | |
static const Perm< 4 > * | Sn |
A dimension-agnostic alias for Perm<4>::S4. More... | |
static const unsigned | invS4 [24] |
Contains the inverses of the permutations in the array S4. More... | |
static const unsigned * | invSn |
A dimension-agnostic alias for Perm<4>::invS4. More... | |
static const Perm< 4 > | orderedS4 [24] |
Contains all possible permutations of four elements in lexicographical order. More... | |
static const Perm< 4 > * | orderedSn |
A dimension-agnostic alias for Perm<4>::orderedS4. More... | |
static const Perm< 4 > | S3 [6] |
Contains all possible permutations of three elements. More... | |
static const Perm< 4 > * | Sn_1 |
A dimension-agnostic alias for Perm<4>::S3. More... | |
static const Perm< 4 > | orderedS3 [6] |
Contains all possible permutations of three elements in lexicographical order. More... | |
static const Perm< 4 > | S2 [2] |
Contains all possible permutations of two elements. More... | |
Represents a permutation of {0,1,2,3}.
This is a specialisation of the generic Perm template: it is highly optimised, and also offers some additional functionality. Amongst other things, this permutation class is used to specify how simplices of a 3-manifold triangulation are glued together.
As with all Perm template classes, these objects are small enough to pass about by value instead of by reference. Moreover, Perm<4> 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<4>, the internal permutation codes have changed as of Regina 4.6.1:
It is highly recommended that, if you need to work with permutation codes at all, you use second-generation codes where possible. This is because the first-generation routines incur additional overhead in converting back and forth between the second-generation codes (which are used internally by Perm<4>).
To use this class, simply include the main permutation header maths/perm.h.
typedef uint8_t regina::Perm< 4 >::Code |
Indicates the native unsigned integer type used to store the internal permutation code.
typedef int regina::Perm< 4 >::Index |
Denotes a native signed integer type large enough to count all permutations on four elements.
In other words, this is a native signed integer type large enough to store (4!).
|
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 (0,1,2,3) to (a,b,c,d) respectively.
a | the desired image of 0. |
b | the desired image of 1. |
c | the desired image of 2. |
d | the desired image of 3. |
|
inline |
Creates a permutation mapping i to image[i] for each i = 0,1,2,3.
image | the array of images. |
regina::Perm< 4 >::Perm | ( | const int * | a, |
const int * | b | ||
) |
Creates a permutation mapping (a[0], ..., a[3]) to (b[0], ..., b[3]) respectively.
a | the array of preimages; this must have length 4. |
b | the corresponding array of images; this must also have length 4. |
regina::Perm< 4 >::Perm | ( | int | a0, |
int | a1, | ||
int | b0, | ||
int | b1, | ||
int | c0, | ||
int | c1, | ||
int | d0, | ||
int | d1 | ||
) |
Creates a permutation mapping (a0,b0,c0,d0) to (a1,b1,c1,d1) respectively.
a0 | the desired preimage of a1. |
b0 | the desired preimage of b1. |
c0 | the desired preimage of c1. |
d0 | the desired preimage of d1. |
a1 | the desired image of a0. |
b1 | the desired image of b0. |
c1 | the desired image of c0. |
d1 | the desired image of d0. |
|
default |
Creates a permutation that is a clone of the given permutation.
cloneMe | the permutation to clone. |
|
inlinestatic |
Returns the ith permutation on four elements, where permutations are numbered lexicographically beginning at 0.
Lexicographical ordering treats each permutation p as the 4-tuple (p[0], p[1], p[2], p[3]).
The return value will be identical to orderedS4[i].
i | the lexicographical index of the permutation; this must be between 0 and 23 inclusive. |
void regina::Perm< 4 >::clear | ( | unsigned | from | ) |
Resets the images of all integers from from onwards to the identity map.
Specifically, for each i in the range from,...,3, this routine will ensure that image[i] == i
. The images of 0,1,...,from-1 will not be altered.
from | the first integer whose image should be reset. This must be between 0 and 4 inclusive. |
|
inline |
Lexicographically compares the images of (0,1,2,3) under this and the given permutation.
other | the permutation with which to compare this. |
|
static |
Restricts a k-element permutation to an 4-element permutation, where k > 4.
The resulting permutation will map 0,...,3 to their respective images under p, and will ignore the "unused" images p[4],...,p[k-1].
k | the number of elements for the input permutation; this must be strictly greater than 4. |
p | a permutation on k elements. |
|
static |
Extends a k-element permutation to a 4-element permutation, where 2 ≤ k < 4.
The resulting permutation will map 0,...,k-1 to their respective images under p, and will map the "unused" elements k,...,3 to themselves.
k | the number of elements for the input permutation; this must be 2 or 3. |
p | a permutation on k elements. |
|
inlinestatic |
Creates a permutation from the given first-generation permutation code.
code | the first-generation code for the new permutation. |
|
inlinestatic |
Creates a permutation from the given second-generation permutation code.
Second-generation codes are fast to work with, since they are used internally by the Perm<4> class.
code | the second-generation code for the new permutation. |
|
inline |
Returns the lexicographical index of this permutation.
This indicates where this permutation sits within a full lexicographical ordering of all 4! permutations on four elements.
Lexicographical ordering treats each permutation p as the 4-tuple (p[0], p[1], p[2], p[3]). In particular, the identity permutation has index 0, and the "reverse" permutation (which maps each i to 3-i) has index 23 = 4!-1.
This routine is identical to orderedS4Index().
|
inline |
Finds the inverse of this permutation.
|
inline |
Determines if this is the identity permutation.
This is true if and only if each of 0, 1, 2 and 3 is mapped to itself.
true
if and only if this is the identity permutation.
|
static |
Determines whether the given character is a valid first-generation permutation code.
Valid first-generation codes can be passed to setPermCode() or fromPermCode(), and are returned by permCode().
code | the permutation code to test. |
true
if and only if the given code is a valid first-generation permutation code.
|
inlinestatic |
Determines whether the given character is a valid second-generation permutation code.
Valid second-generation codes can be passed to setPermCode2() or fromPermCode2(), and are returned by permCode2().
Second-generation codes are fast to work with, since they are used internally by the Perm<4> class.
code | the permutation code to test. |
true
if and only if the given code is a valid second-generation 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 at least one of 0, 1, 2 or 3.
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 be p o q, satisfying (p*q)[x] == p[q[x]]
.
q | the permutation with which to compose this. |
|
default |
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 0, 1, 2 and 3.
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 3 inclusive. |
|
inline |
Returns the index of this permutation in the Perm<4>::orderedS4 array.
|
inline |
Returns the index of this permutation in the Perm<4>::orderedS4 array.
This is a dimension-agnostic alias for orderedS4Index().
|
inline |
Returns the first-generation code representing this permutation.
This code is sufficient to reproduce the entire permutation.
The code returned will be a valid first-generation permutation code as determined by isPermCode().
|
inline |
Returns the second-generation code representing this permutation.
This code is sufficient to reproduce the entire permutation.
The code returned will be a valid second-generation permutation code as determined by isPermCode2().
Second-generation codes are fast to work with, since they are used internally by the Perm<4> class.
|
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 3 inclusive. |
|
inlinestatic |
Returns a random permutation on four elements.
All permutations are returned with equal probability.
This routine is thread-safe, and uses RandomEngine for its random number generation.
rand(randomEngine.engine(), even)
.even | if true , then the resulting permutation is guaranteed to be even (and again all even permutations are returned with equal probability). |
|
static |
Returns a random permutation on four 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.
URBG | A type which, once any references are removed, must adhere to the C++ UniformRandomBitGenerator concept. |
gen | the source of randomness to use (e.g., one of the many options provided in the C++ standard random header). |
even | if true , then the resulting permutation is guaranteed to be even (and again all even permutations are returned with equal probability). |
|
inline |
Finds the reverse of this permutation.
Here reverse means that we reverse the images of 0,...,3. In other words, if permutation q is the reverse of p, then p[i] == q[3 - i]
for all i.
|
inline |
Returns the index of this permutation in the Perm<4>::S4 array.
|
inline |
Sets this permutation to that represented by the given first-generation permutation code.
code | the first-generation code that will determine the new value of this permutation. |
|
inline |
Sets this permutation to that represented by the given second-generation permutation code.
Second-generation codes are fast to work with, since they are used internally by the Perm<4> class.
code | the second-generation code that will determine the new value of this permutation. |
|
inline |
Determines the sign of this permutation.
|
inline |
Returns the index of this permutation in the Perm<4>::S4 array.
This is a dimension-agnostic alias for S4Index().
std::string regina::Perm< 4 >::str | ( | ) | const |
Returns a string representation of this permutation.
The representation will consist of four adjacent digits representing the images of 0, 1, 2 and 3 respectively. An example of a string representation is 1302
.
std::string regina::Perm< 4 >::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 4 inclusive. |
std::string regina::Perm< 4 >::trunc2 | ( | ) | const |
Returns a string representation of this permutation with only the images of 0 and 1.
The resulting string will therefore have length two.
std::string regina::Perm< 4 >::trunc3 | ( | ) | const |
Returns a string representation of this permutation with only the images of 0, 1 and 2 included.
The resulting string will therefore have length three.
|
static |
Contains the inverses of the permutations in the array S4.
Specifically, the inverse of permutation S4[i]
is the permutation S4[ invS4[i] ]
.
|
static |
A dimension-agnostic alias for Perm<4>::invS4.
In general, for each K the class PermK will define an alias invSn that references the list of all permutations PermK::invSK.
|
static |
The total number of permutations on four elements.
This is the size of the array Sn.
|
static |
The total number of permutations on three elements.
This is the size of the array Sn_1.
|
static |
Contains all possible permutations of three elements in lexicographical order.
In each permutation, 3 maps to 3.
|
static |
Contains all possible permutations of four elements in lexicographical order.
|
static |
A dimension-agnostic alias for Perm<4>::orderedS4.
In general, for each K the class PermK will define an alias orderedSn that references the list of all permutations PermK::orderedSK.
|
static |
Contains all possible permutations of two elements.
In each permutation, 2 maps to 2 and 3 maps to 3.
The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.
For all permutation classes (Perm<4>, Perm<5> and so on), the S2 array stores the same permutations in the same order (but of course using different data types).
Note that these permutations are already in lexicographical order.
|
static |
Contains all possible permutations of three elements.
In each permutation, 3 maps to 3.
The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.
For all permutation classes (Perm<4>, Perm<5> and so on), the S3 array stores the same permutations in the same order (but of course using different data types).
Note that the permutations are not necessarily in lexicographical order. For the corresponding inverse array, see Perm<3>::invS3.
|
static |
Contains all possible permutations of four elements.
The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.
For all permutation classes (Perm<4>, Perm<5> and so on), the S4 array stores the same permutations in the same order (but of course using different data types).
Note that the permutations are not necessarily in lexicographical order.
|
static |
A dimension-agnostic alias for Perm<4>::S4.
In general, for each K the class PermK will define an alias Sn that references the list of all permutations PermK::SK.
|
static |
A dimension-agnostic alias for Perm<4>::S3.
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).