Combinations

Functions
M0_INTERNAL uint64_t	m0_fact (uint64_t n)
M0_INTERNAL uint32_t	m0_ncr (uint64_t n, uint64_t r)
M0_INTERNAL int	m0_combination_index (int N, int K, int *x)
M0_INTERNAL void	m0_combination_inverse (int cid, int N, int K, int *x)

Detailed Description

For a given alphabet 'A', having length 'N' containing sorted and no duplicate elements, combinations are build in lexoicographical order using Lehmer code. Then given a combination 'X' it's index can be returned. Also given a index and length of combination, combination can be returned.

For more information on this issue visit here

Function Documentation

m0_combination_index()

M0_INTERNAL int m0_combination_index	(	int	N,
		int	K,
		int *	x
	)

Returns combination index of 'x' in combinations of alphabet 'A'.

Parameters

'N'	length of alphabet 'A' ordered elements.
'K'	lenght of combination.

Precondition

0 < K <= N

m0_forall(i, K, x[i] < N)

Definition at line 52 of file combinations.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_combination_inverse()

M0_INTERNAL void m0_combination_inverse	(	int	cid,
		int	N,
		int	K,
		int *	x
	)

Returns the combination array 'x' for a given combination index.

Parameters

	cid	Combination index.
	N	Length of alphabet (total number of elements).
	K	Length of combination (# of elements in the combination).
[out]	x	Indices of elements, represented by the combination.

Note

Output array 'x' is provided by user. Its capacity must not be less than K elements.

Precondition

0 < K <= N

Definition at line 79 of file combinations.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_fact()

M0_INTERNAL uint64_t m0_fact

(

uint64_t

n

)

Factorial of n.

Definition at line 31 of file combinations.c.

Here is the call graph for this function:

Here is the caller graph for this function:

m0_ncr()

M0_INTERNAL uint32_t m0_ncr	(	uint64_t	n,
		uint64_t	r
	)

The number of possible combinations that can be obtained by taking a sub-set of ‘r’ items from a larger set of ‘n’ elements.

Precondition

n >= r

See also

http://www.calculatorsoup.com/calculators/discretemathematics/combinations.php

Definition at line 38 of file combinations.c.

Here is the call graph for this function:

Here is the caller graph for this function: