Permutations of $\{0\dots 15\}$. More...

#include <perm16.hpp>

Inheritance diagram for HPCombi::Perm16:

Public Member Functions
	Perm16 ()=default

constexpr	Perm16 (const Perm16 &)=default

constexpr	Perm16 (const vect v)

constexpr	Perm16 (const epu8 x)

Perm16 &	operator= (const Perm16 &)=default

	Perm16 (std::initializer_list< uint8_t > il)

bool	validate (size_t k=16) const
	Return whether `*this` is a well constructed object.

Perm16	operator* (const Perm16 &p) const
	The product of two permutations.

	Perm16 (uint64_t compressed)
	Construct a permutations from its 64 bits compressed.

Perm16	inverse_ref () const
	The inverse permutation.

Perm16	inverse_arr () const
	The inverse permutation.

Perm16	inverse_sort () const
	The inverse permutation.

Perm16	inverse_find () const
	The inverse permutation.

Perm16	inverse_pow () const
	The inverse permutation.

Perm16	inverse_cycl () const
	The inverse permutation.

Perm16	inverse () const
	The inverse permutation.

epu8	lehmer_ref () const
	The Lehmer code of a permutation.

epu8	lehmer_arr () const
	The Lehmer code of a permutation.

epu8	lehmer () const
	The Lehmer code of a permutation.

uint8_t	length_ref () const
	The Coxeter length (ie: number of inversion) of a permutation.

uint8_t	length_arr () const
	The Coxeter length (ie: number of inversion) of a permutation.

uint8_t	length () const
	The Coxeter length (ie: number of inversion) of a permutation.

uint8_t	nb_descents_ref () const
	The number of descent of a permutation.

uint8_t	nb_descents () const
	The number of descent of a permutation.

epu8	cycles_partition () const
	The set partition of the cycles of a permutation.

uint8_t	nb_cycles_ref () const
	The number of cycles of a permutation.

uint8_t	nb_cycles_unroll () const
	The number of cycles of a permutation.

uint8_t	nb_cycles () const
	The number of cycles of a permutation.

bool	left_weak_leq_ref (Perm16 other) const
	Compare two permutations for the left weak order.

bool	left_weak_leq_length (Perm16 other) const
	Compare two permutations for the left weak order.

bool	left_weak_leq (Perm16 other) const
	Compare two permutations for the left weak order.

Public Member Functions inherited from HPCombi::Transf16
	Transf16 ()=default

constexpr	Transf16 (const Transf16 &v)=default

constexpr	Transf16 (const vect v)

constexpr	Transf16 (const epu8 x)

	Transf16 (std::initializer_list< uint8_t > il)

Transf16 &	operator= (const Transf16 &)=default

bool	validate (size_t k=16) const
	Return whether `*this` is a well constructed object.

Transf16	operator* (const Transf16 &p) const
	The product of two transformations.

	Transf16 (uint64_t compressed)
	Construct a transformation from its 64 bits compressed.

	operator uint64_t () const
	The 64 bit compressed form of a transformation.

Public Member Functions inherited from HPCombi::PTransf16
	PTransf16 ()=default

constexpr	PTransf16 (const vect v)

constexpr	PTransf16 (const epu8 x)

	PTransf16 (std::vector< uint8_t > dom, std::vector< uint8_t > rng, size_t=0)

	PTransf16 (std::initializer_list< uint8_t > il)

bool	validate (size_t k=16) const
	Return whether `*this` is a well constructed object.

PTransf16	operator* (const PTransf16 &p) const
	The product of two partial transformations.

epu8	image_mask_cmpestrm (bool complement=false) const
	Returns a mask for the image of `*this`.

epu8	image_mask_ref (bool complement=false) const
	Returns a mask for the image of `*this`.

epu8	image_mask (bool complement=false) const

uint32_t	image_bitset (bool complement=false) const
	Returns a bit mask for the image of `*this`.

epu8	domain_mask (bool complement=false) const
	Returns a mask for the domain of `*this`.

uint32_t	domain_bitset (bool complement=false) const
	Returns a bit mask for the domain of `*this`.

PTransf16	right_one () const
	Returns the partial right identity for `*this`.

PTransf16	left_one () const
	Returns the partial left identity for `*this`.

uint32_t	rank_ref () const
	Returns the size of the image of `*this`.

uint32_t	rank () const
	Returns the size of the image of `*this`.

uint32_t	rank_cmpestrm () const
	Returns the size of the image of `*this`.

epu8	fix_points_mask (bool complement=false) const
	Returns a mask for the fix point of `*this`.

uint32_t	fix_points_bitset (bool complement=false) const
	Returns a bit mask for the fix point of `*this`.

uint8_t	smallest_fix_point () const
	Returns the smallest fix point of `*this`.

uint8_t	smallest_moved_point () const
	Returns the smallest non fix point of `*this`.

uint8_t	largest_fix_point () const
	Returns the largest fix point of `*this`.

uint8_t	largest_moved_point () const
	Returns the largest non fix point of `*this`.

uint8_t	nb_fix_points () const
	Returns the number of fix points of `*this`.

Public Member Functions inherited from HPCombi::Vect16
	Vect16 ()=default

constexpr	Vect16 (epu8 x)

	Vect16 (std::initializer_list< uint8_t > il, uint8_t def=0)

constexpr	operator epu8 () const

array &	as_array ()

const array &	as_array () const

const uint8_t &	operator[] (uint64_t i) const

uint8_t &	operator[] (uint64_t i)

size_t	first_diff (const Vect16 &u, size_t bound=size()) const

size_t	last_diff (const Vect16 &u, size_t bound=size()) const

size_t	first_zero (size_t bound=size()) const

size_t	last_zero (size_t bound=size()) const

size_t	first_non_zero (size_t bound=size()) const

size_t	last_non_zero (size_t bound=size()) const

const_iterator	cbegin () const

const_iterator	cend () const

iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

bool	operator== (const Vect16 &b) const

bool	operator!= (const Vect16 &b) const

bool	operator< (const Vect16 &b) const

int8_t	less_partial (const Vect16 &b, int k) const

Vect16	permuted (const Vect16 &b) const

uint8_t	sum () const

Vect16	partial_sums () const

Vect16	eval16 () const

bool	is_permutation () const

bool	is_permutation (size_t k) const

Static Public Member Functions
static constexpr Perm16	one ()
	The identity partial permutation.

static Perm16	elementary_transposition (uint64_t i)
	The elementary transposition exchanging $i$ and $i+1$.

static Perm16	random (uint64_t n=16)
	A random permutation of size $n$.

static Perm16	unrankSJT (int n, int r)
	The `r` -th permutation of size `n` for the Steinhaus–Johnson–Trotter order.

Static Public Member Functions inherited from HPCombi::Transf16
static constexpr Transf16	one ()
	The identity transformation.

Static Public Member Functions inherited from HPCombi::PTransf16
static constexpr size_t	size ()

static constexpr PTransf16	one ()
	The identity partial transformation.

Static Public Member Functions inherited from HPCombi::Vect16
static constexpr size_t	size ()

Additional Inherited Members
Public Types inherited from HPCombi::PTransf16
using	vect = HPCombi::Vect16

using	array = typename decltype(Epu8)::array

Public Types inherited from HPCombi::Vect16
using	array = typename decltype(Epu8)::array

using	value_type = uint8_t

using	iterator = typename array::iterator

using	const_iterator = typename array::const_iterator

Public Attributes inherited from HPCombi::Vect16
epu8	v

Detailed Description

Permutations of $\{0\dots 15\}$.

Constructor & Destructor Documentation

◆ Perm16() [1/6]

HPCombi::Perm16::Perm16 ( )

default

◆ Perm16() [2/6]

constexpr HPCombi::Perm16::Perm16 ( const Perm16 & )

constexprdefault

◆ Perm16() [3/6]

constexpr HPCombi::Perm16::Perm16 ( const vect v )

inlineconstexpr

◆ Perm16() [4/6]

constexpr HPCombi::Perm16::Perm16 ( const epu8 x )

inlineconstexpr

◆ Perm16() [5/6]

HPCombi::Perm16::Perm16 ( std::initializer_list< uint8_t > il )

inline

◆ Perm16() [6/6]

HPCombi::Perm16::Perm16 ( uint64_t compressed )

inlineexplicit

Construct a permutations from its 64 bits compressed.

Member Function Documentation

◆ cycles_partition()

epu8 HPCombi::Perm16::cycles_partition ( ) const

inline

The set partition of the cycles of a permutation.

Returns: the a vector $v$ where $fv[i]$f contains the smallest element in the cycle of $i$ in *this

Example:

Perm16 x {1,2,3,6,0,5,4,7,8,9,10,11,12,15,14,13}

x.cycles_partition()

HPCombi::Perm16

Permutations of .

Definition perm16.hpp:208

HPCombi::Perm16::cycles_partition

epu8 cycles_partition() const

The set partition of the cycles of a permutation.

Definition perm16_impl.hpp:344

Returns

[ 0, 0, 0, 0, 0, 5, 0, 7, 8, 9,10,11,12,13,14,13]

◆ elementary_transposition()

Perm16 HPCombi::Perm16::elementary_transposition ( uint64_t i )

inlinestatic

The elementary transposition exchanging $i$ and $i+1$.

◆ inverse()

Perm16 HPCombi::Perm16::inverse ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

HPCombi::Perm16::inverse

Perm16 inverse() const

The inverse permutation.

Definition perm16.hpp:283

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Frontend method: currently aliased to inverse_cycl

◆ inverse_arr()

Perm16 HPCombi::Perm16::inverse_arr ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:: $O(n)$ algorithm using reference cast to arrays

◆ inverse_cycl()

Perm16 HPCombi::Perm16::inverse_cycl ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:: Compute power from $n/2$ to $n$, when $\sigma^k(i)=i$ then $\sigma^{-1}(i)=\sigma^{k-1}(i)$. Complexity $O(n)$

◆ inverse_find()

Perm16 HPCombi::Perm16::inverse_find ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:: $O(\log n)$ algorithm using some kind of vectorized dichotomic search.

◆ inverse_pow()

Perm16 HPCombi::Perm16::inverse_pow ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:

Raise *this to power $\text{LCM}(1, 2, ..., n) - 1$ so complexity is in $O(log (\text{LCM}(1, 2, ..., n) - 1)) = O(n)$

◆ inverse_ref()

Perm16 HPCombi::Perm16::inverse_ref ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:: Reference $O(n)$ algorithm using loop and indexed access

◆ inverse_sort()

Perm16 HPCombi::Perm16::inverse_sort ( ) const

inline

The inverse permutation.

Returns: the inverse of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.inverse()

Returns

{0,4,2,1,3,5,6,7,8,9,10,11,12,13,14,15}

Algorithm:: Insert the identity in the least significant bits and sort using a sorting network. The number of round of the optimal sorting network is open as far as I know, therefore the complexity is unknown.

◆ left_weak_leq()

bool HPCombi::Perm16::left_weak_leq ( Perm16 other ) const

inline

Compare two permutations for the left weak order.

Example:

Perm16 x{2,0,3,1}, y{3,0,2,1};

x.left_weak_leq(y)

HPCombi::Perm16::left_weak_leq

bool left_weak_leq(Perm16 other) const

Compare two permutations for the left weak order.

Definition perm16_impl.hpp:372

Returns

true

Algorithm:: $O(n)$ algorithm using length

◆ left_weak_leq_length()

bool HPCombi::Perm16::left_weak_leq_length ( Perm16 other ) const

inline

Compare two permutations for the left weak order.

Example:

Perm16 x{2,0,3,1}, y{3,0,2,1};

x.left_weak_leq(y)

Returns

true

Algorithm:: Reference $O(n)$ with vectorized test of inclusion

◆ left_weak_leq_ref()

bool HPCombi::Perm16::left_weak_leq_ref ( Perm16 other ) const

inline

Compare two permutations for the left weak order.

Example:

Perm16 x{2,0,3,1}, y{3,0,2,1};

x.left_weak_leq(y)

Returns

true

Algorithm:: Reference $O(n^2)$ testing inclusion of inversions one by one

◆ lehmer()

epu8 HPCombi::Perm16::lehmer ( ) const

inline

The Lehmer code of a permutation.

Returns: the Lehmer code of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.lehmer()

HPCombi::Perm16::lehmer

epu8 lehmer() const

The Lehmer code of a permutation.

Definition perm16_impl.hpp:290

Returns

{0,2,1,1,0,0,0,0,0,0,0,0,0,0,0,0}

Algorithm:: Fast $O(n)$ algorithm using vector comparison

◆ lehmer_arr()

epu8 HPCombi::Perm16::lehmer_arr ( ) const

inline

The Lehmer code of a permutation.

Returns: the Lehmer code of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.lehmer()

Returns

{0,2,1,1,0,0,0,0,0,0,0,0,0,0,0,0}

Algorithm:: Reference $O(n^2)$ algorithm using array, loop and indexed access

◆ lehmer_ref()

epu8 HPCombi::Perm16::lehmer_ref ( ) const

inline

The Lehmer code of a permutation.

Returns: the Lehmer code of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.lehmer()

Returns

{0,2,1,1,0,0,0,0,0,0,0,0,0,0,0,0}

Algorithm:: Reference $O(n^2)$ algorithm using loop and indexed access

◆ length()

uint8_t HPCombi::Perm16::length ( ) const

inline

The Coxeter length (ie: number of inversion) of a permutation.

Returns: the number of inversions of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.length()

HPCombi::Perm16::length

uint8_t length() const

The Coxeter length (ie: number of inversion) of a permutation.

Definition perm16_impl.hpp:318

Returns

Algorithm:: $O(n)$ using vector lehmer and fast horizontal sum

◆ length_arr()

uint8_t HPCombi::Perm16::length_arr ( ) const

inline

The Coxeter length (ie: number of inversion) of a permutation.

Returns: the number of inversions of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.length()

Returns

Algorithm:: Reference $O(n^2)$ algorithm using loop and indexed access after a cast to std::array

◆ length_ref()

uint8_t HPCombi::Perm16::length_ref ( ) const

inline

The Coxeter length (ie: number of inversion) of a permutation.

Returns: the number of inversions of *this

Example:

Perm16 x = {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.length()

Returns

Algorithm:: Reference $O(n^2)$ algorithm using loop and indexed access

◆ nb_cycles()

uint8_t HPCombi::Perm16::nb_cycles ( ) const

inline

The number of cycles of a permutation.

Returns: the number of cycles of *this

Example:

Perm16 x {1,2,3,6,0,5,4,7,8,9,10,11,12,15,14,13}

x.nb_cycles()

HPCombi::Perm16::nb_cycles

uint8_t nb_cycles() const

The number of cycles of a permutation.

Definition perm16.hpp:412

Returns

Algorithm: aliased to #nb_cycles_unroll

◆ nb_cycles_ref()

uint8_t HPCombi::Perm16::nb_cycles_ref ( ) const

inline

The number of cycles of a permutation.

Returns: the number of cycles of *this

Example:

Perm16 x {1,2,3,6,0,5,4,7,8,9,10,11,12,15,14,13}

x.nb_cycles()

Returns

Algorithm:: Reference $O(n)$ using a boolean vector

◆ nb_cycles_unroll()

uint8_t HPCombi::Perm16::nb_cycles_unroll ( ) const

inline

The number of cycles of a permutation.

Returns: the number of cycles of *this

Example:

Perm16 x {1,2,3,6,0,5,4,7,8,9,10,11,12,15,14,13}

x.nb_cycles()

Returns

Algorithm:: Reference $O(\log(n))$ using cycles_partition

◆ nb_descents()

uint8_t HPCombi::Perm16::nb_descents ( ) const

inline

The number of descent of a permutation.

Returns: the number of inversions of *this

Example:

Perm16 x {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.length()

Returns

Algorithm:: Reference $O(1)$ using vector shift and comparison

◆ nb_descents_ref()

uint8_t HPCombi::Perm16::nb_descents_ref ( ) const

inline

The number of descent of a permutation.

Returns: the number of inversions of *this

Example:

Perm16 x {0,3,2,4,1,5,6,7,8,9,10,11,12,13,14,15};

x.length()

Returns

Algorithm:: Reference $O(n)$ using a loop

◆ one()

static constexpr Perm16 HPCombi::Perm16::one ( )

inlinestaticconstexpr

The identity partial permutation.

◆ operator*()

Perm16 HPCombi::Perm16::operator* ( const Perm16 & p ) const

inline

The product of two permutations.

◆ operator=()

Perm16 & HPCombi::Perm16::operator= ( const Perm16 & )

default

◆ random()

Perm16 HPCombi::Perm16::random ( uint64_t n = 16 )

inlinestatic

A random permutation of size $n$.

◆ unrankSJT()

Perm16 HPCombi::Perm16::unrankSJT	(	int	n,
		int	r
	)

inlinestatic

The r -th permutation of size n for the Steinhaus–Johnson–Trotter order.

◆ validate()

bool HPCombi::Perm16::validate ( size_t k = 16 ) const

inline

Return whether *this is a well constructed object.

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

/Users/jdm/hpcombi/include/hpcombi/perm16.hpp
/Users/jdm/hpcombi/include/hpcombi/perm16_impl.hpp

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Perm16() [1/6]

◆ Perm16() [2/6]

◆ Perm16() [3/6]

◆ Perm16() [4/6]

◆ Perm16() [5/6]

◆ Perm16() [6/6]

Member Function Documentation

◆ cycles_partition()

◆ elementary_transposition()

◆ inverse()

◆ inverse_arr()

◆ inverse_cycl()

◆ inverse_find()

◆ inverse_pow()

◆ inverse_ref()

◆ inverse_sort()

◆ left_weak_leq()

◆ left_weak_leq_length()

◆ left_weak_leq_ref()

◆ lehmer()

◆ lehmer_arr()

◆ lehmer_ref()

◆ length()

◆ length_arr()

◆ length_ref()

◆ nb_cycles()

◆ nb_cycles_ref()

◆ nb_cycles_unroll()

◆ nb_descents()

◆ nb_descents_ref()

◆ one()

◆ operator*()

◆ operator=()

◆ random()

◆ unrankSJT()

◆ validate()