regina::PermSn< n, order, codeType > Struct Template Reference

A lightweight array-like object that supports fast lookup and iteration for permutations on n objects. More...

#include <maths/permsn.h>

Classes
class	iterator
	An iterator over all permutations of n objects. More...

Public Types
using	const_iterator = iterator
	An iterator over all permutations of n objects.

Public Member Functions
constexpr Perm< n >	operator[] (Perm< n >::Index index) const
	Returns the permutation at the given index in Sn, according to the chosen ordering.
constexpr Perm< n >::Index	size () const
	Returns the total number of permutations of n objects.
constexpr iterator	begin () const
	Returns an iterator pointing to the first permutation according to the chosen ordering.
constexpr iterator	end () const
	Returns an iterator pointing beyond the last permutation.
auto	__iter__ () const
	Returns a Python iterator over all permutations of n objects.
constexpr bool	operator== (const PermSn &) const
	A trivial equality test that always returns true.

Detailed Description

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>
struct regina::PermSn< n, order, codeType >

A lightweight array-like object that supports fast lookup and iteration for permutations on n objects.

Typically you would access this object through static constants such as Perm<n>::Sn or Perm<n>::orderedSn. There should be no need for end users to refer to this type directly.

There are two main ways in which you can use this object. For the examples below, we assume that we are accessing Perm<n>::Sn.

• Array-style lookup. Here you would use accessors such as Perm<n>::Sn[i] and Perm<n>::Sn::size(). Instead of size(), you can also use the standard len() function in Python.
• Iteration. Here you would typically iterate over Perm<n>::Sn in a range-based for loop, or use begin/end pairs such as Perm<n>::Sn.begin() and Perm<n>::Sn.end().

Regarding indices and iteration:

• Indices are between 0 and (n!-1) inclusive, and permutations are indexed according to the chosen ordering, i.e., the template parameter order. In particular: Perm<n>::Sn uses sign-based ordering, beginning with the identity permutation at index 0 and alternating between even and odd permutations, whereas Perm<n>::orderedSn uses lexicographical ordering according the images of 0,...,n-1 under each permutation.
• The order of iteration is the same as the order used for indexing.
• Iterating directly over this object (e.g., iterating over Perm<n>::Sn) is typically faster than using array-like access for each index in turn (e.g., accessing Sn[0], Sn[1], etc.). This is particularly true when n is larger. See the notes on time complexity below.

Regarding time complexity:

• For n ≤ 7, iteration steps and index-based lookup are both extremely fast constant time. Iterators are random-access (and satisfy all of the expected time complexity constraints that come with this).
• For n ≥ 8, the time for a single iteration step is in linear in n, and index-based lookup is currently quadratic in n. Iterators are merely forward iterators, not random access.

Objects of this type contain no data at all, which means they are trivial to pass by value or swap with std::swap(), and all objects of this type are essentially identical.

Python

Python does not support templates. Instead this class can be accessed by appending n and order as suffixes (e.g., PermSn3_Sign, or PermSn5_Lex).

Template Parameters

n	the number of objects being permuted. This must be between 2 and 16 inclusive.
order	the way in which this class orders permutations for the purposes of indexing and iteration.
codeType	the constant Perm<n>::codeType. You should allow the compiler to deduce this and not attempt to set it yourself.

Member Typedef Documentation

const_iterator

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

using regina::PermSn< n, order, codeType >::const_iterator = iterator

An iterator over all permutations of n objects.

Both iterator and const_iterator are the same type, since PermSn only offers read-only access to its permutations. See the PermSn::iterator class for further details.

Member Function Documentation

__iter__()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

auto regina::PermSn< n, order, codeType >::__iter__

(

)

const

Returns a Python iterator over all permutations of n objects.

See the PermSn class notes for further details on how iteration works.

C++

Not present. For C++ users, PermSn provides the usual begin() and end() functions instead. In particular, you can iterate over all permutations in the usual way using a range-based for loop.

Returns

an iterator over all permutations of n objects.

begin()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

iterator regina::PermSn< n, order, codeType >::begin ( ) const

inlineconstexpr

Returns an iterator pointing to the first permutation according to the chosen ordering.

For all supported orderings, this first permutation is the identity permutation; however, as the iterator steps through from begin() to end(), the order in which subsequent permutations appear will depend upon the template parameter order.

See the PermSn class notes for further details on how iteration works over all permutations of n objects.

Python

Not present. For Python users, PermSn implements the Python iterable interface. You can iterate over all permutations in the same way that you would iterate over any native Python container.

Returns

a starting iterator for iterating over all permutations of n objects.

end()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

iterator regina::PermSn< n, order, codeType >::end ( ) const

inlineconstexpr

Returns an iterator pointing beyond the last permutation.

See the PermSn class notes for further details on how iteration works over all permutations of n objects.

Python

Not present. For Python users, PermSn implements the Python iterable interface. You can iterate over all permutations in the same way that you would iterate over any native Python container.

Returns

a past-the-end iterator for iterating over all permutations of n objects.

operator==()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

bool regina::PermSn< n, order, codeType >::operator== ( const PermSn< n, order, codeType > & ) const

inlineconstexpr

A trivial equality test that always returns true.

Since PermSn contains no data of its own, any two PermSn objects of the same type (i.e., using the same template parameters) will always describe the same sequence of permutations in the same order.

Returns

true, always.

operator[]()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

Perm< n > regina::PermSn< n, order, codeType >::operator[] ( Perm< n >::Index index ) const

inlineconstexpr

Returns the permutation at the given index in Sn, according to the chosen ordering.

See the PermSn class notes for further details on how array-like indexing works for permutations of n objects. In particular, note that which permutation corresponds to which index will depend upon the template parameter order.

For n ≤ 7, this operator is very fast constant time. However, for n ≥ 8 the current implementation is quadratic in n.

Parameters

index

an index between 0 and n!-1 inclusive.

Returns

the corresponding permutation.

size()

template<int n, PermOrder order, PermCodeType codeType = Perm<n>::codeType>

Perm< n >::Index regina::PermSn< n, order, codeType >::size ( ) const

inlineconstexpr

Returns the total number of permutations of n objects.

This is of course just n!.

Python

This is also used to implement the Python special method len().

Returns

the total number of permutations.

---

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

• maths/permsn.h