Combinatorics group

Detailed Description

Some usefull combinatorial functionalities.

Functions
template<typename Z >
Z	binomial (const Z n, const Z r)
	Computes the binomial expansion coefficient binomial(n,r) More...
template<unsigned n, unsigned r>
unsigned	binomial ()
	Returns binomial(n,r) as a compile time constant. More...
void	binomial_into (unsigned n, gsVector< unsigned > &v)
	Returns a vector containing all the binomials (n,r) with n fixed. More...
template<typename Z , int d>
void	cubeIsometry (const gsVector< bool, d > &flip, const gsVector< index_t, d > &perm, gsVector< Z > &result)
	Computes the isometry of the unit d-cube implied by a permutation perm of the cube directions plus a relocation flip of the cube vertices. More...
template<int d>
void	cubeIsometryMatrix (const gsVector< bool, d > &flip, const gsVector< index_t, d > &perm, gsMatrix< int, d, d > &result)
	Computes the rotation matrix implied by a permutation perm of the cube directions plus a relocation flip. More...
template<class Vec >
index_t	dimCubeElement (const Vec &cur)
	Returns the dimension of an element (face) of the d-cube [0,1]^d. The element is expected to contain 0,1 (corresponding to cube extrema) and the special value 2 at the position of "free" coordinates.
unsigned	factorial (unsigned n)
	Returns the factorial of n i.e. n! Remember that factorial grow too fast and only n! with n<=13 can be stored in a 32bit that is an unsigned.
template<class Vec >
void	firstCombination (const unsigned n, const unsigned r, Vec &res)
	Computes the first r-combination of {0,..,n-1}.
template<class Vec >
void	firstComposition (typename Vec::Scalar sum, index_t dim, Vec &res)
	Construct first composition of sum into dim integers.
template<class Vec >
void	firstCubeElement (Vec &cur, const index_t k=0)
	Updates cur to contain the lexicographically first element (face) of the cube [0,1]^d of dimension k. For k==d the face (2..2) is returned, corresponding to the cube itself.
template<class Vec , class Mat >
void	firstMultiComposition (const Vec &a, index_t k, Mat &res)
	Constructs first multi-composition of a = (a_1,..,a_d) into k integers.
template<class Vec >
void	firstPermutation (Vec &current)
	changes current to the first permutation of 0 ... size(current)-1 note that you must resize the vector to specify the number of elements
template<class Vec >
bool	nextCombination (Vec &v, const unsigned n)
	Computes the next r-combination of {0,..,n-1}, where r = v.size(). The input v is expected to be a valid combination.
template<class Vec >
bool	nextComposition (Vec &v)
	Returns (inplace) the next composition in lexicographic order.
template<class Vec >
bool	nextCubeBoundary (Vec &cur, const Vec &start, const Vec &end)
	Iterates in lex-order through the boundary points of the cube [start,end]. Updates cur with the current point and returns true if another point is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeBoundaryOffset (Vec &cur, const Vec &start, const Vec &end, Vec &offset)
	Iterates in lex-order through the boundary points of the cube [start,end], with an \ offset to the interior. Updates cur with the current point and returns true if another point is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeBoundaryOffset (Vec &cur, const Vec &start, const Vec &end, Vec &loffset, Vec &uoffset)
	Iterates in lex-order through the boundary points of the cube [start,end], with offset loffset from \ start and roffset .from the end. Updates cur with the current point and returns true if another point is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeElement (Vec &cur, const index_t k)
	Iterates in lexicographic order through the elements (faces) of dimension k of the cube [0,1]^d. Updates cur with the current element (face) and returns true if another element (face) of dimension k is available. Coordinates with value 2 indicate free/not-fixed dimensions.
template<class Vec >
bool	nextCubePoint (Vec &cur, const Vec &end)
	Iterate in lexigographic order through the points of the integer lattice contained in the cube [0,end]. Updates cur with the current point and returns true if another point is available. Cube may be degenerate.
template<class Vec >
bool	nextCubePoint (Vec &cur, const Vec &start, const Vec &end)
	Iterates in lexigographic order through the points of the integer lattice contained in the cube [start,end]. Updates cur with the current point and returns true if another point is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeVertex (Vec &cur, const Vec &start, const Vec &end)
	Iterate in lexicographic order through the vertices of the cube [start,end]. Updates cur with the current vertex and returns true if another vertex is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeVertex (Vec &cur, const Vec &end)
	Iterate in lexicographic order through the vertices of the cube [0,end]. Updates cur with the current vertex and returns true if another vertex is available. Cube may be degenerate.
template<class Vec >
bool	nextCubeVertex (Vec &cur)
	Iterate in lexigographic order through the vertices of the unit cube. Updates cur with the lexicographically next vertex and returns true if another point is available. This is equivalent to iterating over all possible binary sequences of length cur.size(). The input cur is expected to contain only zeros and ones (or true/false).
template<class Vec >
bool	nextLexicographic (Vec &cur, const Vec &size)
	Iterates through a tensor lattice with the given size. Updates cur and returns true if another entry was available End values (size) are not included in the enumerated points, as with iterators.
template<class Vec >
bool	nextLexicographic (Vec &cur, const Vec &start, const Vec &end)
	Iterate through a tensor lattice with the given start and end points. end coordinates are not included in the enumerated points, as with iterators. Updates cur and returns true if another entry was available.
template<class Mat >
bool	nextMultiComposition (Mat &m)
	Returns (inplace) the next multi-composition in lexicographic order. More...
template<class Vec >
bool	nextPermutation (Vec &current)
	Changes current to the next lexicographically ordered permutation. More...
unsigned	numCompositions (int sum, short_t dim)
	Number of compositions of sum into dim integers.
index_t	numCubeElements (const index_t k, const index_t d)
	Returns the number of elements (faces) of dimension k of a d-cube.
template<class Vec >
unsigned	numMultiCompositions (const Vec &a, index_t k)
	Number of multi-composition of a = (a_1,..,a_d) into k integers.

Function Documentation

Z gismo::binomial ( const Z  n, const Z  r  )

inline

Computes the binomial expansion coefficient binomial(n,r)

The binomial coefficient indexed by n and k is is the coefficient of the $x^k$ term in the polynomial expansion of the binomial power $(1 + x)^n$.

This functions computes a single binomial coefficient, if many binomial coefficients with fixed n are needed then it is probably faster use the function binomial_into. This function uses a loop implementation.

Parameters

n	binomial power
r	term of the binomial expansion

unsigned gismo::binomial ( )

inline

Returns binomial(n,r) as a compile time constant.

This is done using template recursion and can be accessed either by b=binomialT<n,r>::value; or b=binomial<n,r>(); The second form relies on the compiler optimizations to avoid function call.

void gismo::binomial_into ( unsigned  n, gsVector< unsigned > &  v  )

inline

Returns a vector containing all the binomials (n,r) with n fixed.

This functions compute all the binomial coefficients with fixed n and store them in the supplied vector v. Uses the Pacal triangle rule.

Parameters

[in]	n
[out]	v	a vector with n+1 components each equal to

void gismo::cubeIsometry	(	const gsVector< bool, d > &	flip,
		const gsVector< index_t, d > &	perm,
		gsVector< Z > &	result
	)

Computes the isometry of the unit d-cube implied by a permutation perm of the cube directions plus a relocation flip of the cube vertices.

Parameters

[in]	flip	the relocation of the cube vertices flip[k]==true : the coordinate k of the vertex is not relocated flip[k]==false : the coordinate k of the vertex is relocated
[in]	perm	the permutation of the cube directions (0,..,d-1)
[out]	result	A permutation of the vertices (0,..,2^d-1)

void gismo::cubeIsometryMatrix	(	const gsVector< bool, d > &	flip,
		const gsVector< index_t, d > &	perm,
		gsMatrix< int, d, d > &	result
	)

Computes the rotation matrix implied by a permutation perm of the cube directions plus a relocation flip.

Parameters

[in]	flip	the relocation of the cube vertices flip[k]==true : the coordinate k is not relocated flip[k]==false : the coordinate k is relocated
[in]	perm	the permutation of the directions (0,..,d-1)
[out]	result	A rotation matrix

bool gismo::nextMultiComposition ( Mat &  m )

inline

Returns (inplace) the next multi-composition in lexicographic order.

\( m \in \mathbb N^{k\times d} \)

bool gismo::nextPermutation

(

Vec &

current

)

Changes current to the next lexicographically ordered permutation.

Returns

false when the lexicographically last permutation is given