ytCombo Class Reference

Combination related routines. More...

#include <math/ytCombo.h>

Public Member Functions
uint64_t	ytCombo_choose (int n, int k)
	Calculates the number of combinations of n things taken k at a time (binomial coefficient).
int	ytCombo_generate (int n, int k, int *ar)
	Generates the combination.
void	ytCombo_indexTable (int n, uint64_t *table)
	Generates the index table for ytCombo routines.
uint64_t	ytCombo_index (int n, int c, const int *ar, const uint64_t *table, int tn)
	Calculates the index for the given combination.
void	ytCombo_combination (int n, int k, uint64_t index, int *ar, const uint64_t *table, int tn)
	Obtain the combination corresponding to the given index.
void	ytCombo_combination2 (int n, int k, uint64_t index, int *ar, const int *a, const uint64_t *table, int tn)
	Obtain the combination corresponding to the given index.
void	ytCombo_combination3 (int n, int k, uint64_t index, int *ar, const int *a, const int *b, const uint64_t *table, int tn)
	Obtain the combination corresponding to the given index.

Detailed Description

Combination related routines.

Member Function Documentation

ytCombo_choose()

uint64_t ytCombo_choose	(	int	n,
		int	k
	)

Calculates the number of combinations of n things taken k at a time (binomial coefficient).

This is the C implementation of ACM Algorithm 160.

Parameters

n
k

Returns

number of combinations of n things taken k at a time (binomical coefficient for n and k).

Go to top

ytCombo_combination()

void ytCombo_combination	(	int	n,
		int	k,
		uint64_t	index,
		int *	ar,
		const uint64_t *	table,
		int	tn
	)

Obtain the combination corresponding to the given index.

This is the inverse function of ytCombo_index().

Parameters

tn	table size specified to ytCombo_indexTable().

Go to top

ytCombo_combination2()

void ytCombo_combination2	(	int	n,
		int	k,
		uint64_t	index,
		int *	ar,
		const int *	a,
		const uint64_t *	table,
		int	tn
	)

Obtain the combination corresponding to the given index.

This is the inverse function of ytCombo_index().

Parameters

tn	table size specified to combo_indexTable().

Go to top

ytCombo_combination3()

void ytCombo_combination3	(	int	n,
		int	k,
		uint64_t	index,
		int *	ar,
		const int *	a,
		const int *	b,
		const uint64_t *	table,
		int	tn
	)

Obtain the combination corresponding to the given index.

This is the inverse function of ytCombo_index().

Parameters

tn	table size specified to combo_indexTable().

Go to top

ytCombo_generate()

int ytCombo_generate	(	int	n,
		int	k,
		int *	ar
	)

Generates the combination.

This generates the combination of n things taken k at a time in lexicographical order from the previouly generated combination.

To generate the first combination, set -1 for the first positions of ar.

Parameters

n
k
ar

Returns

1 if the generated combination is the last one, 0 otherwise.

Go to top

ytCombo_index()

uint64_t ytCombo_index	(	int	n,
		int	c,
		const int *	ar,
		const uint64_t *	table,
		int	tn
	)

Calculates the index for the given combination.

Note that this returns the reverse order (index) of the combination. To obtain the normal index, calculate (choose(n, c) - \t id) where \t id is the reverse index returned by this function.

Parameters

ar	sorted list (combination) of values.
table	index table calculated by ytCombo_index_table().
tn	table size used to calculate table by ytCombo_index_table().

Go to top

ytCombo_indexTable()

void ytCombo_indexTable	(	int	n,
		uint64_t *	table
	)

Generates the index table for ytCombo routines.

The table has to have size sizeof(size_t) * n * n.

Parameters

n
table	pointer to room for storing the index table.

Go to top

---

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

• math/ytCombo.c