Represents a permutation of {0,1,...,n-1}. More...

#include <maths/perm.h>

Public Types
using	Index = typename IntOfMinSize<(imageBits *n+7)/8 >::type
	Denotes a native signed integer type large enough to count all permutations on n elements. More...

using	ImagePack = typename IntOfMinSize<(imageBits *n+7)/8 >::utype
	Indicates the native unsigned integer type used to store a single image pack. More...

using	Code = ImagePack
	Indicates the native unsigned integer type used to store the internal permutation code. More...

Public Member Functions
constexpr	Perm ()
	Creates the identity permutation. More...

constexpr	Perm (int a, int b)
	Creates the transposition of a and b. More...

constexpr	Perm (const std::array< int, n > &image)
	Creates a permutation mapping i to image[i] for each 0 ≤ i < n. More...

constexpr	Perm (const int *image)
	Deprecated constructor that creates a permutation mapping i to image[i] for each 0 ≤ i < n. More...

constexpr	Perm (const int a, const int b)
	Deprecated constructor that creates a permutation mapping (a[0], ..., a[n-1]) to (b[0], ..., b[n-1]) respectively. More...

constexpr	Perm (const Perm< n > &cloneMe)=default
	Creates a permutation that is a clone of the given permutation. More...

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

constexpr ImagePack	imagePack () const
	Returns the image pack that represents this permutation. More...

Perm &	operator= (const Perm &cloneMe)=default
	Sets this permutation to be equal to the given permutation. More...

constexpr Perm	operator* (const Perm &q) const
	Returns the composition of this permutation with the given permutation. More...

constexpr Perm	inverse () const
	Finds the inverse of this permutation. More...

constexpr Perm	reverse () const
	Finds the reverse of this permutation. More...

constexpr int	sign () const
	Determines the sign of this permutation. More...

constexpr int	operator[] (int source) const
	Determines the image of the given integer under this permutation. More...

constexpr int	pre (int image) const
	Determines the preimage of the given integer under this permutation. More...

constexpr int	preImageOf (int image) const
	Deprecated routine that determines the preimage of the given integer under this permutation. More...

constexpr bool	operator== (const Perm &other) const
	Determines if this is equal to the given permutation. More...

constexpr bool	operator!= (const Perm &other) const
	Determines if this differs from the given permutation. More...

constexpr int	compareWith (const Perm &other) const
	Lexicographically compares the images of (0,1,...,n-1) under this and the given permutation. More...

constexpr bool	isIdentity () const
	Determines if this is the identity permutation. More...

constexpr Index	SnIndex () const
	Returns the index of this permutation in the Perm<n>::Sn array. More...

constexpr Index	orderedSnIndex () const
	Returns the lexicographical index of this permutation. More...

constexpr Index	index () const
	Deprecated routine that 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...

template<class URBG >
Perm< n >	rand (URBG &&gen, bool even)

Static Public Member Functions
static constexpr Perm	fromPermCode (Code code)
	Creates a permutation from the given internal code. More...

static constexpr bool	isPermCode (Code newCode)
	Determines whether the given integer is a valid internal permutation code. More...

static constexpr Perm	fromImagePack (ImagePack pack)
	Creates a permutation from the given image pack. More...

static constexpr bool	isImagePack (ImagePack pack)
	Determines whether the given argument is the image pack of some n-element permutation. More...

static constexpr Perm	rot (int i)
	Returns the ith rotation. More...

static constexpr Perm	atIndex (Index i)
	Deprecated routine that returns the ith permutation on n elements, where permutations are numbered lexicographically. More...

static Perm	rand (bool even=false)
	Returns a random permutation on n elements. More...

template<class URBG >
static Perm	rand (URBG &&gen, bool even=false)
	Returns a random permutation on n elements, using the given uniform random bit generator. More...

template<int k>
static constexpr Perm	extend (Perm< k > p)
	Extends a k-element permutation to an n-element permutation, where 2 ≤ k < n. More...

template<int k>
static constexpr Perm	contract (Perm< 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 in an image pack to store the image of a single integer. More...

static constexpr ImagePack	imageMask
	A bitmask whose lowest imageBits bits are 1, and whose remaining higher order bits are all 0. More...

static constexpr PermCodeType	codeType = PERM_CODE_IMAGES
	Indicates what type of internal permutation code is used by this instance of the Perm class template. 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...

static constexpr SnLookup	Sn {}
	Gives array-like access to all possible permutations of n elements. More...

static constexpr OrderedSnLookup	orderedSn {}
	Gives array-like access to all possible permutations of n elements in lexicographical order. More...

Protected Member Functions
constexpr	Perm (Code code)
	Creates a permutation from the given internal code. More...

Protected Attributes
Code	code_
	The internal code representing this permutation. More...

Detailed Description

template<int n>
class regina::Perm< n >

Represents a permutation of {0,1,...,n-1}.

Amongst other things, such permutations are used to describe simplex gluings in (n-1)-manifold triangulations.

Perm objects are small enough to pass by value and swap with std::swap(), with no need to use references, specialised move operations or custom swap functions. The trade-off is that, for this to be possible, the Perm 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 8 ≤ n ≤ 16, the code is an image pack: essentially a packed array that holds the images of 0,...,n-1 in a single native integer type. More precisely, this is an unsigned integer of type ImagePack, whose lowest imageBits bits represent the image of 0, whose next lowest imageBits bits represent the image of 1, and so on. This scheme is consistent with the old first-generation codes for n = 4,...,7, which are still supported but no longer used internally.
For n ≤ 7, the code is an index into a hard-coded list of all possible permutations; more precisely, an index into the symmetric group Perm<n>::Sn. The ordering of Perm<n>::Sn is "almost lexicographic", in that we swap some pairs of indices (2k, 2k+1) to ensure that the even permutations are precisely those with even indices.

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. For n = 6,7, this template is again specialised and highly optimised, and it offers some extra functionality but not as much as Perm<5> and below. For n ≥ 8, this template is generic and most operations require more time (in particular, there are no harded-coded lookup tables).

Python: Python does not support templates. For each n = 2,...,16, this class is available in Python under the corresponding name Perm2, Perm3, ..., Perm16.

Template Parameters

n	the number of objects being permuted. This must be between 2 and 16 inclusive.

Member Typedef Documentation

◆ Code

template<int n>

using regina::Perm< n >::Code = ImagePack

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

This type alias is present for all values of n, though its precise size depends on how the permutation code is constructed. For n = 4,...,7, it is a deprecated type alias that refers to older (first-generation) permutation codes that are no longer used.

◆ ImagePack

template<int n>

using regina::Perm< n >::ImagePack = typename IntOfMinSize<(imageBits * n + 7) / 8>::utype

Indicates the native unsigned integer type used to store a single image pack.

See the class notes for more information on image packs, and how they are used as permutation codes for n ≥ 7.

◆ Index

template<int n>

using regina::Perm< n >::Index = typename IntOfMinSize<(imageBits * n + 7) / 8>::type

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

Note: This type is not hyper-optimised: for very small n where Index is hard-coded this is just an int, and for larger n where Index is derived it is actually large enough to hold an entire image pack. If at any stage there are plans to optimise this type, be careful of the special case of n = 8, where (8!) can be stored in an unsigned 16-bit type but not a signed 16-bit type.

Constructor & Destructor Documentation

◆ Perm() [1/7]

template<int n>

constexpr regina::Perm< n >::Perm

inlineconstexpr

Creates the identity permutation.

◆ Perm() [2/7]

template<int n>

constexpr regina::Perm< n >::Perm	(	int	a,
		int	b
	)

inlineconstexpr

Creates the transposition of a and b.

Note that a and b need not be distinct.

Precondition: 0 ≤ a,b < n.

Parameters

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

◆ Perm() [3/7]

template<int n>

constexpr regina::Perm< n >::Perm ( const std::array< int, n > & image )

inlineconstexpr

Creates a permutation mapping i to image[i] for each 0 ≤ i < n.

Precondition: The elements of image are 0,...,n-1 in some order.

Parameters

image the array of images.

◆ Perm() [4/7]

template<int n>

constexpr regina::Perm< n >::Perm ( const int * image )

inlineconstexpr

Deprecated constructor that creates a permutation mapping i to image[i] for each 0 ≤ i < n.

Deprecated:: Use the std::array constructor instead.

Precondition: The array image contains n elements, which are 0,...,n-1 in some order.

Parameters

image the array of images.

◆ Perm() [5/7]

template<int n>

constexpr regina::Perm< n >::Perm	(	const int *	a,
		const int *	b
	)

inlineconstexpr

Deprecated constructor that creates a permutation mapping (a[0], ..., a[n-1]) to (b[0], ..., b[n-1]) respectively.

Deprecated:: Use the std::array constructor instead.

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

Python: Not present; use the single-array constructor instead.

Parameters

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

◆ Perm() [6/7]

template<int n>

constexpr regina::Perm< n >::Perm ( const Perm< n > & cloneMe )

constexprdefault

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

Parameters

cloneMe the permutation to clone.

◆ Perm() [7/7]

template<int n>

constexpr regina::Perm< n >::Perm ( Code code )

inlineconstexprprotected

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 from which the new permutation will be created.

Member Function Documentation

◆ atIndex()

template<int n>

constexpr Perm< n > regina::Perm< n >::atIndex ( Index i )

inlinestaticconstexpr

Deprecated routine that returns the ith permutation on n elements, where permutations are numbered lexicographically.

Deprecated:: Use orderedSn[i] instead.

Parameters

i	the lexicographical index of the permutation; this must be between 0 and n!-1 inclusive.

Returns: the ith permutation.

◆ clear()

template<int n>

void regina::Perm< n >::clear ( unsigned from )

Resets the images of all integers from from onwards to the identity map.

Specifically, for each i in the range from,...,n-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,...,n-1 are exactly from,...,n-1, but possibly in a different order.

Parameters

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

◆ compareWith()

template<int n>

constexpr int regina::Perm< n >::compareWith ( const Perm< n > & other ) const

constexpr

Lexicographically compares the images of (0,1,...,n-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 n>

template<int k>

static constexpr Perm regina::Perm< n >::contract ( Perm< k > p )

staticconstexpr

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

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

Template Parameters

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

Parameters

p	a permutation on k elements.

Returns: the same permutation restricted to a permutation on n elements.

◆ extend()

template<int n>

template<int k>

static constexpr Perm regina::Perm< n >::extend ( Perm< k > p )

staticconstexpr

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.

Template Parameters

k	the number of elements for the input permutation; this must be at least 2, and strictly less than n.

Parameters

p	a permutation on k elements.

Returns: the same permutation expressed as a permutation on n elements.

◆ fromImagePack()

template<int n>

constexpr Perm< n > regina::Perm< n >::fromImagePack ( ImagePack pack )

inlinestaticconstexpr

Creates a permutation from the given image pack.

See the class notes for more information on image packs, and how they are used to build permutation codes.

For n ≥ 7, this routine is identical to fromPermCode().

Precondition: The argument pack is a valid image pack; see isImagePack() for details.

Parameters

pack	an image pack that describes a permutation.

Returns: the permutation represented by the given image pack.

◆ fromPermCode()

template<int n>

constexpr Perm< n > regina::Perm< n >::fromPermCode ( Code code )

inlinestaticconstexpr

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 reprsented by the given internal code.

◆ imagePack()

template<int n>

constexpr Perm< n >::ImagePack regina::Perm< n >::imagePack

inlineconstexpr

Returns the image pack that represents this permutation.

See the class notes for more information on image packs, and how they are used to build permutation codes.

For n ≥ 7, this routine is identical to permCode().

Returns: the image pack for this permutation.

◆ index()

template<int n>

constexpr Perm< n >::Index regina::Perm< n >::index

inlineconstexpr

Deprecated routine that returns the lexicographical index of this permutation.

Deprecated:: Use the equivalent routine orderedSnIndex() instead.

Returns: the lexicographical index of this permutation.

◆ inverse()

template<int n>

constexpr Perm< n > regina::Perm< n >::inverse

inlineconstexpr

Finds the inverse of this permutation.

Returns: the inverse of this permutation.

◆ isIdentity()

template<int n>

constexpr bool regina::Perm< n >::isIdentity

inlineconstexpr

Determines if this is the identity permutation.

This is true if and only if every integer 0 ≤ i < n is mapped to itself.

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

◆ isImagePack()

template<int n>

constexpr bool regina::Perm< n >::isImagePack ( ImagePack pack )

inlinestaticconstexpr

Determines whether the given argument is the image pack of some n-element permutation.

See the class notes for more information on image packs, and how they are used to build permutation codes.

For n ≥ 7, this routine is identical to isPermCode().

Parameters

pack	the candidate image pack to test.

Returns: true if and only if pack is a valid image pack.

◆ isPermCode()

template<int n>

constexpr bool regina::Perm< n >::isPermCode ( Code newCode )

staticconstexpr

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!=()

template<int n>

constexpr bool regina::Perm< n >::operator!= ( const Perm< n > & other ) const

inlineconstexpr

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.

Parameters

other the permutation with which to compare this.

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

◆ operator*()

template<int n>

constexpr Perm< n > regina::Perm< n >::operator* ( const Perm< n > & q ) const

inlineconstexpr

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

Parameters

q	the permutation to compose this with.

Returns: the composition of both permutations.

◆ operator=()

template<int n>

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

default

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

template<int n>

constexpr bool regina::Perm< n >::operator== ( const Perm< n > & other ) const

inlineconstexpr

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.

Parameters

other the permutation with which to compare this.

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

◆ operator[]()

template<int n>

constexpr int regina::Perm< n >::operator[] ( int source ) const

inlineconstexpr

Determines the image of the given integer under this permutation.

Parameters

source the integer whose image we wish to find. This should be between 0 and n-1 inclusive.

Returns: the image of source.

◆ orderedSnIndex()

template<int n>

constexpr Perm< n >::Index regina::Perm< n >::orderedSnIndex

constexpr

Returns the lexicographical index of this permutation.

This will be the index of this permutation in the Perm<n>::orderedSn array.

See orderedSn for further information on lexicographical ordering.

Returns: the lexicographical index of this permutation. This will be between 0 and n!-1 inclusive.

◆ permCode()

template<int n>

constexpr Perm< n >::Code regina::Perm< n >::permCode

inlineconstexpr

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.

◆ pre()

template<int n>

constexpr int regina::Perm< n >::pre ( int image ) const

inlineconstexpr

Determines the preimage of the given integer under this permutation.

Parameters

image the integer whose preimage we wish to find. This should be between 0 and n-1 inclusive.

Returns: the preimage of image.

◆ preImageOf()

template<int n>

constexpr int regina::Perm< n >::preImageOf ( int image ) const

inlineconstexpr

Deprecated routine that determines the preimage of the given integer under this permutation.

Deprecated:: This routine has been renamed to pre().

Parameters

image the integer whose preimage we wish to find. This should be between 0 and n-1 inclusive.

Returns: the preimage of image.

◆ rand() [1/2]

template<int n>

Perm< n > regina::Perm< n >::rand ( bool even = false )

static

Returns a random permutation on n elements.

All permutations are returned with equal probability.

This routine is thread-safe, and uses RandomEngine for its random number generation.

Warning: This routine is expensive, since it locks and unlocks the mutex protecting Regina's global uniform random bit generator. If you are calling this many times in quick succession, consider creating a single RandomEngine object yourself and then calling rand(randomEngine.engine(), even).

Parameters

even	if `true`, then the resulting permutation is guaranteed to be even (and again all even permutations are returned with equal probability).

Returns: a random permutation.

◆ rand() [2/2]

template<int n>

template<class URBG >

static Perm regina::Perm< n >::rand	(	URBG &&	gen,
		bool	even = `false`
	)

static

Returns a random permutation on n 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.

Template Parameters

URBG	A type which, once any references are removed, must adhere to the C++ UniformRandomBitGenerator concept.

Python: Not present, though the non-thread-safe variant without the gen argument is available.

Parameters

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

Returns: a random permutation.

◆ reverse()

template<int n>

constexpr Perm< n > regina::Perm< n >::reverse

inlineconstexpr

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.

◆ rot()

template<int n>

constexpr Perm< n > regina::Perm< n >::rot ( int i )

staticconstexpr

Returns the ith rotation.

This maps k to k + i (mod n) for all k.

Parameters

i	the image of 0; this must be between 0 and n-1 inclusive.

Returns: the ith rotation.

◆ setPermCode()

template<int n>

void regina::Perm< n >::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()

template<int n>

constexpr int regina::Perm< n >::sign

constexpr

Determines the sign of this permutation.

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

◆ SnIndex()

template<int n>

constexpr Perm< n >::Index regina::Perm< n >::SnIndex

constexpr

Returns the index of this permutation in the Perm<n>::Sn array.

See Sn for further information on how these permutations are indexed.

Returns: the index i for which this permutation is equal to Perm<n>::Sn[i]. This will be between 0 and n!-1 inclusive.

◆ str()

template<int n>

std::string regina::Perm< n >::str

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.

Returns: a string representation of this permutation.

◆ trunc()

template<int n>

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

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

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

Member Data Documentation

◆ code_

template<int n>

Code regina::Perm< n >::code_

protected

The internal code representing this permutation.

◆ codeType

template<int n>

constexpr PermCodeType regina::Perm< n >::codeType = PERM_CODE_IMAGES

staticconstexpr

Indicates what type of internal permutation code is used by this instance of the Perm class template.

◆ imageBits

template<int n>

constexpr int regina::Perm< n >::imageBits = regina::bitsRequired(n)

staticconstexpr

Indicates the number of bits used in an image pack to store the image of a single integer.

A full image pack combines n such images together, and so uses n * imageBits bits in total.

◆ imageMask

template<int n>

constexpr ImagePack regina::Perm< n >::imageMask

staticconstexpr

Initial value:

=

(static_cast<ImagePack>(1) << Perm<n>::imageBits) - 1

regina::Perm::ImagePack

typename IntOfMinSize<(imageBits *n+7)/8 >::utype ImagePack

Indicates the native unsigned integer type used to store a single image pack.

Definition: perm.h:203

regina::Perm::imageBits

static constexpr int imageBits

Indicates the number of bits used in an image pack to store the image of a single integer.

Definition: perm.h:181

A bitmask whose lowest imageBits bits are 1, and whose remaining higher order bits are all 0.

This may be useful when creating or analysing image packs.

◆ nPerms

template<int n>

constexpr Index regina::Perm< n >::nPerms = factorial(n)

staticconstexpr

The total number of permutations on n elements.

This is the size of the symmetric group S_n.

◆ nPerms_1

template<int n>

constexpr Index regina::Perm< n >::nPerms_1 = factorial(n-1)

staticconstexpr

The total number of permutations on n-1 elements.

This is the size of the symmetric group S_n-1.

◆ orderedSn

template<int n>

constexpr OrderedSnLookup regina::Perm< n >::orderedSn {}

staticconstexpr

Gives array-like access to all possible permutations of n elements in lexicographical order.

To access the permutation at index i, you simply use the square bracket operator: orderedSn[i]. The index i must be between 0 and n!-1 inclusive.

Lexicographical ordering treats each permutation p as the n-tuple (p[0], p[1], ..., p[n-1]).

The object that is returned is lightweight and is defined in the headers only. In particular, you cannot make a reference to it (but you can always make a copy).

This is different from Perm<n>::Sn, since this array orderedSn stores permutations in lexicographical order, whereas Sn alternates between even and odd permutations.

Warning: For n ≤ 7, the square bracket operator is a very fast constant-time routine. However, for n ≥ 8, this is not constant time; the current implementation is quadratic in n.

◆ Sn

template<int n>

constexpr SnLookup regina::Perm< n >::Sn {}

staticconstexpr

Gives array-like access to all possible permutations of n elements.

To access the permutation at index i, you simply use the square bracket operator: Sn[i]. The index i must be between 0 and n!-1 inclusive.

The object that is returned is lightweight and is defined in the headers only. In particular, you cannot make a reference to it (but you can always make a copy).

The permutations with even indices in the array are the even permutations, and those with odd indices in the array are the odd permutations.

This is different from Perm<n>::orderedSn, since this array Sn alternates between even and odd permutations, whereas orderedSn stores permutations in lexicographical order.

Warning: For n ≤ 7, the square bracket operator is a very fast constant-time routine. However, for n ≥ 8, this is not constant time; the current implementation is quadratic in n.

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

maths/perm.h

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Code

◆ ImagePack

◆ Index

Constructor & Destructor Documentation

◆ Perm() [1/7]

◆ Perm() [2/7]

◆ Perm() [3/7]

◆ Perm() [4/7]

◆ Perm() [5/7]

◆ Perm() [6/7]

◆ Perm() [7/7]

Member Function Documentation

◆ atIndex()

◆ clear()

◆ compareWith()

◆ contract()

◆ extend()

◆ fromImagePack()

◆ fromPermCode()

◆ imagePack()

◆ index()

◆ inverse()

◆ isIdentity()

◆ isImagePack()

◆ isPermCode()

◆ operator!=()

◆ operator*()

◆ operator=()

◆ operator==()

◆ operator[]()

◆ orderedSnIndex()

◆ permCode()

◆ pre()

◆ preImageOf()

◆ rand() [1/2]

◆ rand() [2/2]

◆ reverse()

◆ rot()

◆ setPermCode()

◆ sign()

◆ SnIndex()

◆ str()

◆ trunc()

Member Data Documentation

◆ code_

◆ codeType

◆ imageBits

◆ imageMask

◆ nPerms

◆ nPerms_1

◆ orderedSn

◆ Sn