Classes
struct	DL_Stack

Functions
template<typename T >
static T	factorial (T n)
	Returns the factorial of `n`. More...

bool	flip_coin ()
	Simulate flipping a coin. More...

template<typename T >
static void	permute (std::vector< T > &values, uint64_t pn, size_t sz=(size_t)(-1))
	Permute a vector according to the specified permutation number. More...

template<typename T >
void	shuffle (std::vector< T > &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1), LinearCongruentialGenerator *lcg=NULL)
	Shuffle the values of a vector. More...

template<typename T >
size_t	damerau_levenshtein_distance (const std::vector< T > &src, const std::vector< T > &tgt)
	Damerau-Levenshtein edit distance. More...

template<typename T >
size_t	levenshtein_distance (const std::vector< T > &src, const std::vector< T > &tgt)
	Levenshtein edit distance. More...


std::vector< uint8_t >	sha1_digest (const uint8_t *data, size_t size)
	Compute a SHA1 digest. More...

std::vector< uint8_t >	sha1_digest (const std::vector< uint8_t > &data)
	Compute a SHA1 digest. More...

std::vector< uint8_t >	sha1_digest (const std::string &data)
	Compute a SHA1 digest. More...


uint64_t	fnv1a64_digest (const uint8_t *data, size_t size)
	Compute the Fowler–Noll–Vo fast string hash. More...

uint64_t	fnv1a64_digest (const std::vector< uint8_t > &data)
	Compute the Fowler–Noll–Vo fast string hash. More...

uint64_t	fnv1a64_digest (const std::string &data)
	Compute the Fowler–Noll–Vo fast string hash. More...


std::string	digest_to_string (const uint8_t *data, size_t size)
	Converts a binary digest to a string of hexadecimal characters. More...

std::string	digest_to_string (const std::vector< uint8_t > &digest)
	Converts a binary digest to a string of hexadecimal characters. More...

std::string	digest_to_string (const std::string &data)
	Converts a binary digest to a string of hexadecimal characters. More...

Function Documentation

template<typename T >

static T Combinatorics::factorial ( T n)

static

Returns the factorial of n.

Definition at line 18 of file Combinatorics.h.

Referenced by permute().

bool Combinatorics::flip_coin ( )

Simulate flipping a coin.

Randomly returns true or false with equal probability. See also, LinearCongruentialGenerator::flip_coin().

template<typename T >

static void Combinatorics::permute	(	std::vector< T > &	values,
		uint64_t	pn,
		size_t	sz = `(size_t)(-1)`
	)

static

Permute a vector according to the specified permutation number.

The permutation number should be between zero (inclusive) and the factorial of the values size (exclusive). A permutation number of zero is a no-op; higher permutation numbers shuffle the values in repeatable ways. Using swap rather that erase/insert is much faster than the standard Lehmer codes, but doesn't return permutations in lexicographic order. This function can perform approx 9.6 million permutations per second on a vector of 12 64-bit integers on Robb's machine (computing all 12! permutations in about 50 seconds).

Definition at line 40 of file Combinatorics.h.

References factorial(), and swap().

template<typename T >

void Combinatorics::shuffle	(	std::vector< T > &	vector,
		size_t	nitems = `(size_t)(-1)`,
		size_t	limit = `(size_t)(-1)`,
		LinearCongruentialGenerator *	lcg = `NULL`
	)

Shuffle the values of a vector.

If nitems is supplied then only the first nitems of the vector are shuffled. If limit is specified then the algorithm returns after at least the first limit elements are sufficiently shuffled. If an lcg is specified, then it will be used to generate the random numbers, otherwise a built-in random number generator is used.

Definition at line 60 of file Combinatorics.h.

References swap().

std::vector<uint8_t> Combinatorics::sha1_digest	(	const uint8_t *	data,
		size_t	size
	)

Compute a SHA1 digest.

The returned vector will contain 20 bytes and can be converted to a string of 40 hexadecimal characters via digest_to_string(). If called when a SHA1 algorithm is not available (due to ROSE configuration) an empty vector is returned.

std::vector<uint8_t> Combinatorics::sha1_digest ( const std::vector< uint8_t > & data)

Compute a SHA1 digest.

The returned vector will contain 20 bytes and can be converted to a string of 40 hexadecimal characters via digest_to_string(). If called when a SHA1 algorithm is not available (due to ROSE configuration) an empty vector is returned.

std::vector<uint8_t> Combinatorics::sha1_digest ( const std::string & data)

Compute a SHA1 digest.

The returned vector will contain 20 bytes and can be converted to a string of 40 hexadecimal characters via digest_to_string(). If called when a SHA1 algorithm is not available (due to ROSE configuration) an empty vector is returned.

uint64_t Combinatorics::fnv1a64_digest	(	const uint8_t *	data,
		size_t	size
	)

Compute the Fowler–Noll–Vo fast string hash.

This is not a cryptographic hash. Speed is marginally slower than Murmur hash, but collision rate is slightly less.

uint64_t Combinatorics::fnv1a64_digest ( const std::vector< uint8_t > & data)

Compute the Fowler–Noll–Vo fast string hash.

This is not a cryptographic hash. Speed is marginally slower than Murmur hash, but collision rate is slightly less.

uint64_t Combinatorics::fnv1a64_digest ( const std::string & data)

Compute the Fowler–Noll–Vo fast string hash.

This is not a cryptographic hash. Speed is marginally slower than Murmur hash, but collision rate is slightly less.

std::string Combinatorics::digest_to_string	(	const uint8_t *	data,
		size_t	size
	)

Converts a binary digest to a string of hexadecimal characters.

The input can actually be any type of data and any length. The output will be twice as long as the input. If you're using this to convert binary data to a printable format you're doing it wrong–use StringUtility::encode_base64() instead.

std::string Combinatorics::digest_to_string ( const std::vector< uint8_t > & digest)

Converts a binary digest to a string of hexadecimal characters.

The input can actually be any type of data and any length. The output will be twice as long as the input. If you're using this to convert binary data to a printable format you're doing it wrong–use StringUtility::encode_base64() instead.

std::string Combinatorics::digest_to_string ( const std::string & data)

Converts a binary digest to a string of hexadecimal characters.

The input can actually be any type of data and any length. The output will be twice as long as the input. If you're using this to convert binary data to a printable format you're doing it wrong–use StringUtility::encode_base64() instead.

template<typename T >

size_t Combinatorics::damerau_levenshtein_distance	(	const std::vector< T > &	src,
		const std::vector< T > &	tgt
	)

Damerau-Levenshtein edit distance.

Returns the true Damerau-Levenshtein edit distance of vectors with adjacent transpositions.

Definition at line 128 of file Combinatorics.h.

References max, and Combinatorics::DL_Stack< T >::unique_push_zero().

template<typename T >

size_t Combinatorics::levenshtein_distance	(	const std::vector< T > &	src,
		const std::vector< T > &	tgt
	)

Levenshtein edit distance.

Returns the Levenshtein edit distance of the specified vectors.

Definition at line 177 of file Combinatorics.h.

References max, and Combinatorics::DL_Stack< T >::unique_push_zero().

Classes

Functions

Function Documentation