combinatorics.h File Reference

Go to the source code of this file.

Functions
bool	get_next_combo (std::vector< unsigned > &combo, unsigned k, unsigned n, bool first_combo=false)
template<class T >
void	randomly_reorder (std::vector< T > &vec)
void	get_rand_permutation (std::vector< unsigned > &perm, unsigned size)
uint64_t	get_64_bit_factorial (unsigned n)
uint64_t	get64BitnUpperk (unsigned n, unsigned k)
bool	read_in_permutations (std::string file_name, std::vector< std::vector< unsigned > > &perms)

Detailed Description

A set of combinatorial functions.

Todo:

Figure out proper way to get random numbers.

Add something that checks to make sure read permutations are proper permutations.

Function Documentation

uint64_t get64BitnUpperk	(	unsigned	n,
		unsigned	k
	)

Returns the value of n!/k! for the given integers.

No guarantees on what happens if there is an overflow.

Todo:

Figure out what should happen when an overflow happens.

Parameters

n	The denominator of the n!/k! term.
k	The numerator of the n!/k! term.

Returns

The value of n!/k! for the given integers.

uint64_t get_64_bit_factorial

(

unsigned

n

)

Returns n! for the given value of n.

If n is too large, it just returns the highest value stored in 64 bits.

Parameters

n	The value to take the factorial of.

Returns

The factorial value of the given value.

bool get_next_combo	(	std::vector< unsigned > &	combo,
		unsigned	k,
		unsigned	n,
		bool	first_combo = false
	)

Given a set (or combination) of natural numbers, generates the next combination in the lexicographic ordering.

This function allows the user to iterate through all combinations of sets of k natural numbers. Given such a combination as a vector of sorted numbers, it generates the next combination if one exists and returns true. The combination is also returned as a sorted vector. If no such combination exists, it returns false and does not change the combination.

Note that the first vector in the ordering is [0, 1, ..., k - 1] and the last is [n - k, n - 2, n - 1].

The first vector in the ordering is generated if the given combination does not have the correct number of elements or the optional flag is set to true. Otherwise, the functions assumes it is given a sorted vector representing a valid combination of k of the first n natural numbers.

Parameters

combo	The last combination generated.
k	The size of each combination.
n	The size of the set of natural numbers to select from.
first_combo	Whether to generate the first combination.

Returns

If a new combination has been generated, or if it has run out of combinations.

void get_rand_permutation	(	std::vector< unsigned > &	perm,
		unsigned	size
	)

Returns a random permutation of a subset of the natural numbers.

The given vector is reset before the permutation is stored there.

Parameters

perm	The vector to store the random permutation in.
size	The size of the permutation.

template<class T >

void randomly_reorder

(

std::vector< T > &

vec

)

Randomly reorders the elements in the given vector.

Parameters

vec	The vector to randomly reorder.

bool read_in_permutations	(	std::string	file_name,
		std::vector< std::vector< unsigned > > &	perms
	)

Reads in the list of permutations from the given file.

Parameters

file_name	The file name to read the states in from.
perms	The list that the read permutations are appended to.

Returns

If the file reading succeeded or not.