regina::Perm< 2 > Class Template Reference
Mathematical Support

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...

## Detailed Description

### template<>
class regina::Perm< 2 >

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.

Warning
  Every permutation class Perm<n> provides a transposition (i.e., pair swap) constructor `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.

Python:
  Since Python does not support templates, this class is made available under the name Perm2.

## Member Typedef Documentation

## Code

typedef uint8_t regina::Perm< 2 >::Code

Indicates the native unsigned integer type used to store the internal permutation code.

## Index

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!).

## Constructor & Destructor Documentation

## Perm() [1/5]

regina::Perm< 2 >::Perm | ( |  | ) |

inline

Creates the identity permutation.

## Perm() [2/5]

regina::Perm< 2 >::Perm | ( | int | a,
|  | int | b
| ) |  |

inline

Creates the transposition of a and b.

Note that a and b need not be distinct.

Precondition
  a and b are in {0,1}.

Parameters

  a | the element to switch with b.
  b | the element to switch with a.

## Perm() [3/5]

regina::Perm< 2 >::Perm | ( | const int * | image | ) |

inline

Creates a permutation mapping i to image[i] for each i = 0,1.

Precondition
  The array image contains two elements, which are 0 and 1 in some order.

Python:
  Not present.

Parameters

  image | the array of images.

## Perm() [4/5]

regina::Perm< 2 >::Perm | ( | const int * | a,
|  | const int * | b
| ) |  |

inline

Creates a permutation mapping (a[0], a[1]) to (b[0], b[1]) respectively.

Precondition
  Both arrays a and b contain two elements, which are 0 and 1 in some order.

Python:
  Not present.

Parameters

  a | the array of preimages; this must have length 2.
  b | the corresponding array of images; this must also have length 2.

## Perm() [5/5]

regina::Perm< 2 >::Perm | ( | const Perm< 2 > & | cloneMe | ) |

inline

Creates a permutation that is a clone of the given permutation.

Parameters

  cloneMe | the permutation to clone.

## Member Function Documentation

## atIndex()

Perm< 2 > regina::Perm< 2 >::atIndex | ( | Index | i | ) |

inline static

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].

Parameters

  i | the lexicographical index of the permutation; this must be 0 or 1.

Returns
  the ith permutation.

## clear()

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.

Precondition
  The images of from,...,1 are exactly from,...,1, but possibly in a different order.

Parameters

  from | the first integer whose image should be reset. This must be between 0 and 2 inclusive.

## compareWith()

int regina::Perm< 2 >::compareWith | ( | const Perm< 2 > & | other | ) | const

inline

Lexicographically compares the images of (0,1) under this and the given permutation.

Parameters

  other | the permutation with which to compare this.

Returns
  -1 if this permutation produces a smaller image, 0 if the permutations are equal and 1 if this permutation produces a greater image.

## contract()

template<int k>

static Perm<2> regina::Perm< 2 >::contract | ( | Perm< k > | p | ) |

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].

Precondition
  The given permutation maps 0,1 to 0,1 in some order.

Template Parameters

  k | the number of elements for the input permutation; this must be strictly greater than 2.

Parameters

  p | a permutation on k elements.

Returns
  the same permutation restricted to a permutation on 2 elements.

## fromPermCode()

Perm< 2 > regina::Perm< 2 >::fromPermCode | ( | Code | code | ) |

inline static

Creates a permutation from the given internal code.

Precondition
  the given code is a valid permutation code; see isPermCode() for details.

Parameters

  code | the internal code for the new permutation.

Returns
  the permutation represented by the given internal code.

## index()

Perm< 2 >::Index regina::Perm< 2 >::index | ( |  | ) | const

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().

Returns
  the index of this permutation, which will be 0 or 1.

## inverse()

Perm< 2 > regina::Perm< 2 >::inverse | ( |  | ) | const

inline

Finds the inverse of this permutation.

Returns
  the inverse of this permutation.

## isIdentity()

bool regina::Perm< 2 >::isIdentity | ( |  | ) | const

inline

Determines if this is the identity permutation.

This is true if and only if each of 0 and 1 is mapped to itself.

Returns
  `true` if and only if this is the identity permutation.

## isPermCode()

bool regina::Perm< 2 >::isPermCode | ( | Code | code | ) |

inline 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().

Returns
  `true` if and only if the given code is a valid internal permutation code.

## operator!=()

bool regina::Perm< 2 >::operator!= | ( | const Perm< 2 > & | other | ) | const

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.

Parameters

  other | the permutation with which to compare this.

Returns
  `true` if and only if this and the given permutation differ.

## operator*()

Perm< 2 > regina::Perm< 2 >::operator* | ( | const Perm< 2 > & | q | ) | const

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]]`.

Parameters

  q | the permutation with which to compose this.

Returns
  the composition of both permutations.

## operator=()

Perm< 2 > & regina::Perm< 2 >::operator= | ( | const Perm< 2 > & | cloneMe | ) |

inline

Sets this permutation to be equal to the given permutation.

Parameters

  cloneMe | the permutation whose value will be assigned to this permutation.

Returns
  a reference to this permutation.

## operator==()

bool regina::Perm< 2 >::operator== | ( | const Perm< 2 > & | other | ) | const

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.

Parameters

  other | the permutation with which to compare this.

Returns
  `true` if and only if this and the given permutation are equal.

## operator[]()

int regina::Perm< 2 >::operator[] | ( | int | source | ) | const

inline

Determines the image of the given integer under this permutation.

Parameters

  source | the integer whose image we wish to find. This should be 0 or 1.

Returns
  the image of source.

## orderedS2Index()

int regina::Perm< 2 >::orderedS2Index | ( |  | ) | const

inline

Returns the index of this permutation in the Perm<2>::orderedS2 array.

Returns
  the index i for which this permutation is equal to Perm<2>::orderedS2[i]. This will be 0 or 1.

## orderedSnIndex()

int regina::Perm< 2 >::orderedSnIndex | ( |  | ) | const

inline

Returns the index of this permutation in the Perm<2>::orderedS2 array.

This is a dimension-agnostic alias for orderedS2Index().

Returns
  the index i for which this permutation is equal to Perm<2>::orderedS2[i]. This will be 0 or 1.

## permCode()

Perm< 2 >::Code regina::Perm< 2 >::permCode | ( |  | ) | const

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().

Returns
  the internal code.

## preImageOf()

int regina::Perm< 2 >::preImageOf | ( | int | image | ) | const

inline

Determines the preimage of the given integer under this permutation.

Parameters

  image | the integer whose preimage we wish to find. This should be 0 or 1.

Returns
  the preimage of image.

## rand()

Perm< 2 > regina::Perm< 2 >::rand | ( |  | ) |

inline static

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.

Returns
  a random permutation.

## reverse()

Perm< 2 > regina::Perm< 2 >::reverse | ( |  | ) | const

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.

## S2Index()

int regina::Perm< 2 >::S2Index | ( |  | ) | const

inline

Returns the index of this permutation in the Perm<2>::S2 array.

Returns
  the index i for which this permutation is equal to Perm<2>::S2[i]. This will be 0 or 1.

## setPermCode()

void regina::Perm< 2 >::setPermCode | ( | Code | code | ) |

inline

Sets this permutation to that represented by the given internal code.

Precondition
  the given code is a valid permutation code; see isPermCode() for details.

Parameters

  code | the internal code that will determine the new value of this permutation.

## sign()

int regina::Perm< 2 >::sign | ( |  | ) | const

inline

Determines the sign of this permutation.

Returns
  1 if this permutation is even, or -1 if this permutation is odd.

## SnIndex()

int regina::Perm< 2 >::SnIndex | ( |  | ) | const

inline

Returns the index of this permutation in the Perm<2>::S2 array.

This is a dimension-agnostic alias for S2Index().

Returns
  the index i for which this permutation is equal to Perm<2>::S2[i]. This will be 0 or 1.

## str()

std::string regina::Perm< 2 >::str | ( |  | ) | const

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`.

Returns
  a string representation of this permutation.

## trunc()

std::string regina::Perm< 2 >::trunc | ( | unsigned | len | ) | const

inline

Returns a prefix of the string representation of this permutation, containing only the images of the first len integers.

Parameters

  len | the length of the prefix required; this must be between 0 and 2 inclusive.

Returns
  the corresponding prefix of the string representation of this permutation.

## Member Data Documentation

## invS2

const unsigned regina::Perm< 2 >::invS2[2]

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.

## invSn

const unsigned* regina::Perm< 2 >::invSn

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.

## nPerms

const Index regina::Perm< 2 >::nPerms = 2

static

The total number of permutations on two elements.

This is the size of the array Sn.

## nPerms_1

const Index regina::Perm< 2 >::nPerms_1 = 1

static

The total number of permutations on one element.

This is the size of the array Sn_1.

## orderedS2

const Perm<2>* regina::Perm< 2 >::orderedS2

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.

## orderedSn

const Perm<2>* regina::Perm< 2 >::orderedSn

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.

## S1

const Perm<2>* regina::Perm< 2 >::S1

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).

## S2

const Perm<2> regina::Perm< 2 >::S2[2]

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).

## Sn

const Perm<2>* regina::Perm< 2 >::Sn

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.

## Sn_1

const Perm<2>* regina::Perm< 2 >::Sn_1

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).

The documentation for this class was generated from the following file:

- maths/spec/perm2.h

Copyright © 1999-2016, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).