Regina Calculation Engine
|
Represents a permutation of {0,1}. More...
#include <maths/nperm2.h>
Public Types | |
typedef int | Index |
Denotes a native signed integer type large enough to count all permutations on two elements. More... | |
typedef uint8_t | 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 i = 0,1. More... | |
NPerm (const int *a, const int *b) | |
Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively. More... | |
NPerm (const NPerm< 2 > &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< 2 > & | operator= (const NPerm< 2 > &cloneMe) |
Sets this permutation to be equal to the given permutation. More... | |
NPerm< 2 > | operator* (const NPerm< 2 > &q) const |
Returns the composition of this permutation with the given permutation. More... | |
NPerm< 2 > | inverse () const |
Finds the inverse of this permutation. More... | |
NPerm< 2 > | 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< 2 > &other) const |
Determines if this is equal to the given permutation. More... | |
bool | operator!= (const NPerm< 2 > &other) const |
Determines if this differs from the given permutation. More... | |
int | compareWith (const NPerm< 2 > &other) const |
Lexicographically compares the images of (0,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... | |
int | S2Index () const |
Returns the index of this permutation in the NPerm<2>::S2 array. More... | |
int | SnIndex () const |
Returns the index of this permutation in the NPerm<2>::S2 array. More... | |
int | orderedS2Index () const |
Returns the index of this permutation in the NPerm<2>::orderedS2 array. More... | |
int | orderedSnIndex () const |
Returns the index of this permutation in the NPerm<2>::orderedS2 array. More... | |
Static Public Member Functions | |
static NPerm< 2 > | fromPermCode (Code code) |
Creates a permutation from the given internal code. More... | |
static bool | isPermCode (Code code) |
Determines whether the given integer is a valid internal permutation code. More... | |
static NPerm | atIndex (Index i) |
Returns the ith permutation on two elements, where permutations are numbered lexicographically beginning at 0. More... | |
static NPerm | rand () |
Returns a random permutation on two elements. More... | |
template<int k> | |
static NPerm< 2 > | contract (NPerm< k > p) |
Restricts a k-element permutation to an 2-element permutation, where k > 2. More... | |
Static Public Attributes | |
static const Index | nPerms = 2 |
The total number of permutations on two elements. More... | |
static const Index | nPerms_1 = 1 |
The total number of permutations on one element. More... | |
static const NPerm< 2 > | S2 [2] |
Contains all possible permutations of two elements. More... | |
static const NPerm< 2 > * | Sn |
A dimension-agnostic alias for NPerm<2>::S2. More... | |
static const unsigned | invS2 [2] |
Contains the inverses of the permutations in the array S2. More... | |
static const unsigned * | invSn |
A dimension-agnostic alias for NPerm<2>::invS2. More... | |
static const NPerm< 2 > * | orderedS2 |
Contains all possible permutations of two elements in lexicographical order. More... | |
static const NPerm< 2 > * | orderedSn |
A dimension-agnostic alias for NPerm<2>::orderedS2. More... | |
static const NPerm< 2 > * | S1 |
Contains all possible permutations of one element. More... | |
static const NPerm< 2 > * | Sn_1 |
A dimension-agnostic alias for NPerm<2>::S1. More... | |
Represents a permutation of {0,1}.
This is a specialisation of the generic NPerm template: it is highly optimised, but also somewhat trivial (since there are only two possible permutations). It is provided simply to optimise the general NPerm<n> template for this trivial case.
As with all NPerm template classes, these objects are small enough to pass about by value instead of by reference. Moreover, NPerm2 in particular 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 NPerm2, the internal code is 0 for the identity permutation, or 1 for the (unique) non-identity permutation.
NPerm<n>(a,b).
In addition, the specialised classes NPerm3, NPerm4 and NPerm5 provide "list of images" constructors NPerm3(a,b,c)
, NPerm4(a,b,c,d)
and NPerm5(a,b,c,d,e)
. For NPerm2, these two constructors would be indistinguishable (since both would take two integer arguments). Here NPerm2 takes an approach that is consistent with the generic NPerm<n> class: NPerm2(a,b)
is interpreted as the transposition of a and b. In particular, NPerm(0,1)
is not the identity permutation.typedef uint8_t regina::NPerm< 2 >::Code |
Indicates the native unsigned integer type used to store the internal permutation code.
typedef int regina::NPerm< 2 >::Index |
Denotes a native signed integer type large enough to count all permutations on two elements.
In other words, this is a native signed integer type large enough to store (2!).
|
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 i = 0,1.
image | the array of images. |
|
inline |
Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively.
a | the array of preimages; this must have length 2. |
b | the corresponding array of images; this must also have length 2. |
|
inline |
Creates a permutation that is a clone of the given permutation.
cloneMe | the permutation to clone. |
|
inlinestatic |
Returns the ith permutation on two elements, where permutations are numbered lexicographically beginning at 0.
Lexicographical ordering treats each permutation p as the pair (p[0], p[1]).
The return value will be identical to orderedS2[i].
i | the lexicographical index of the permutation; this must be 0 or 1. |
|
inline |
Lexicographically compares the images of (0,1) under this and the given permutation.
other | the permutation with which to compare this. |
|
static |
Restricts a k-element permutation to an 2-element permutation, where k > 2.
The resulting permutation will map 0,1 to their respective images under p, and will ignore the "unused" images p[2],...,p[k-1].
k | the number of elements for the input permutation; this must be strictly greater than 2. |
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.
|
inline |
Returns the lexicographical index of this permutation.
This indicates where this permutation sits within a full lexicographical ordering of all 2! permutations on two elements.
Lexicographical ordering treats each permutation p as the pair (p[0], p[1]). That is, the identity permutation has index 0, and the (unique) non-identity permutation has index 1.
This routine is identical to orderedS2Index().
|
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 and 1 is mapped to itself.
true
if and only if this is the identity permutation.
|
inlinestatic |
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 at least one of 0 or 1.
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. |
|
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 0 and 1.
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 0 or 1. |
|
inline |
Returns the index of this permutation in the NPerm<2>::orderedS2 array.
|
inline |
Returns the index of this permutation in the NPerm<2>::orderedS2 array.
This is a dimension-agnostic alias for orderedS2Index().
|
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 0 or 1. |
|
inlinestatic |
Returns a random permutation on two 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 and 1. In other words, if permutation q is the reverse of p, then p[i] == q[1 - i]
for all i.
|
inline |
Returns the index of this permutation in the NPerm<2>::S2 array.
|
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. |
|
inline |
Determines the sign of this permutation.
|
inline |
Returns the index of this permutation in the NPerm<2>::S2 array.
This is a dimension-agnostic alias for S2Index().
|
inline |
Returns a string representation of this permutation.
The representation will consist of two adjacent digits representing the images of 0 and 1 respectively. An example of a string representation is 10
.
|
inline |
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 2 inclusive. |
|
static |
Contains the inverses of the permutations in the array S2.
Specifically, the inverse of permutation S2[i]
is the permutation S2[ invS2[i] ]
.
This array is provided for consistency with larger permutation classes; of course, for permutations of two elements, the inverse of p is always p itself.
|
static |
A dimension-agnostic alias for NPerm<2>::invS2.
In general, for each K the class NPermK will define an alias invSn that references the list of all permutations NPermK::invSK.
|
static |
The total number of permutations on two elements.
This is the size of the array Sn.
|
static |
The total number of permutations on one element.
This is the size of the array Sn_1.
|
static |
Contains all possible permutations of two elements in lexicographical order.
This is identical to the array NPerm<2>::S2, and in fact orderedS2 and S2 are pointers to the same array in memory. Note however that for n ≥ 3, the arrays NPerm<n>::Sn and NPerm<n>::orderedSn are different: Sn alternates between even and odd permutations, and orderedSn stores permutations in lexicograpical order.
|
static |
A dimension-agnostic alias for NPerm<2>::orderedS2.
In general, for each K the class NPermK will define an alias orderedSn that references the list of all permutations NPermK::orderedSK.
|
static |
Contains all possible permutations of one element.
In each permutation, 1 maps to 1.
Of course, this array is trivial: it contains just the identity permutation. This array is provided for consistency with larger permutation classes NPerm<n>.
Note that, as an implementation detail, the arrays S1 and S2 point to the same location in memory (however, they are treated as arrays of different lengths).
|
static |
Contains all possible permutations of two elements.
The identity permutation has index 0, and the non-identity permutation has index 1. As a result, S2[i] is an even permutation if and only if i is even.
For all permutation classes (NPerm<2>, NPerm<3> and so on), the S2 array stores the same permutations in the same order (but of course using different data types).
|
static |
A dimension-agnostic alias for NPerm<2>::S2.
In general, for each K the class NPermK will define an alias Sn that references the list of all permutations NPermK::SK.
|
static |
A dimension-agnostic alias for NPerm<2>::S1.
In general, for each K the class NPermK will define an alias Sn_1 that references the list of all permutations NPermK::S(K-1).