Regina Calculation Engine
|
Represents a permutation of {0,1}. More...
#include <maths/spec/perm2.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 | |
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 i = 0,1. More... | |
Perm (const int *a, const int *b) | |
Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively. More... | |
Perm (const Perm< 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... | |
void | setPermCode (Code code) |
Sets this permutation to that represented by the given internal code. More... | |
Perm< 2 > & | operator= (const Perm< 2 > &cloneMe) |
Sets this permutation to be equal to the given permutation. More... | |
Perm< 2 > | operator* (const Perm< 2 > &q) const |
Returns the composition of this permutation with the given permutation. More... | |
Perm< 2 > | inverse () const |
Finds the inverse of this permutation. More... | |
Perm< 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 Perm< 2 > &other) const |
Determines if this is equal to the given permutation. More... | |
bool | operator!= (const Perm< 2 > &other) const |
Determines if this differs from the given permutation. More... | |
int | compareWith (const Perm< 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... | |
void | clear (unsigned from) |
Resets the images of all integers from from onwards to the identity map. More... | |
int | S2Index () const |
Returns the index of this permutation in the Perm<2>::S2 array. More... | |
int | SnIndex () const |
Returns the index of this permutation in the Perm<2>::S2 array. More... | |
int | orderedS2Index () const |
Returns the index of this permutation in the Perm<2>::orderedS2 array. More... | |
int | orderedSnIndex () const |
Returns the index of this permutation in the Perm<2>::orderedS2 array. More... | |
Static Public Member Functions | |
static Perm< 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 Perm | atIndex (Index i) |
Returns the ith permutation on two elements, where permutations are numbered lexicographically beginning at 0. More... | |
static Perm | rand () |
Returns a random permutation on two elements. More... | |
template<int k> | |
static Perm< 2 > | contract (Perm< 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 Perm< 2 > | S2 [2] |
Contains all possible permutations of two elements. More... | |
static const Perm< 2 > * | Sn |
A dimension-agnostic alias for Perm<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 Perm<2>::invS2. More... | |
static const Perm< 2 > * | orderedS2 |
Contains all possible permutations of two elements in lexicographical order. More... | |
static const Perm< 2 > * | orderedSn |
A dimension-agnostic alias for Perm<2>::orderedS2. More... | |
static const Perm< 2 > * | S1 |
Contains all possible permutations of one element. More... | |
static const Perm< 2 > * | Sn_1 |
A dimension-agnostic alias for Perm<2>::S1. More... | |
Represents a permutation of {0,1}.
This is a specialisation of the generic Perm template: it is highly optimised, but also somewhat trivial (since there are only two possible permutations). It is provided simply to optimise the general Perm<n> template for this trivial case.
As with all Perm template classes, these objects are small enough to pass about by value instead of by reference. Moreover, Perm<2> 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 Perm<2>, the internal code is 0 for the identity permutation, or 1 for the (unique) non-identity permutation.
To use this class, simply include the main permutation header maths/perm.h.
Perm<n>(a,b).
In addition, the specialised classes Perm<3>, Perm<4> and Perm<5> provide "list of images" constructors Perm<3>(a,b,c)
, Perm<4>(a,b,c,d)
and Perm<5>(a,b,c,d,e)
. For Perm<2>, these two constructors would be indistinguishable (since both would take two integer arguments). Here Perm<2> takes an approach that is consistent with the generic Perm<n> class: Perm<2>(a,b)
is interpreted as the transposition of a and b. In particular, Perm(0,1)
is not the identity permutation.typedef uint8_t regina::Perm< 2 >::Code |
Indicates the native unsigned integer type used to store the internal permutation code.
typedef int regina::Perm< 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. |
void regina::Perm< 2 >::clear | ( | unsigned | from | ) |
Resets the images of all integers from from onwards to the identity map.
Specifically, for each i in the range from,...,1, 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 2 inclusive. |
|
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 |
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 Perm<2>::orderedS2 array.
|
inline |
Returns the index of this permutation in the Perm<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 Perm<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 Perm<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 Perm<2>::invS2.
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 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 Perm<2>::S2, and in fact orderedS2 and S2 are pointers to the same array in memory. Note however that for n ≥ 3, the arrays Perm<n>::Sn and Perm<n>::orderedSn are different: Sn alternates between even and odd permutations, and orderedSn stores permutations in lexicograpical order.
|
static |
A dimension-agnostic alias for Perm<2>::orderedS2.
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 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 Perm<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 (Perm<2>, Perm<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 Perm<2>::S2.
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<2>::S1.
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).