Base Operations

Operations for basic number generation and basic random operations. More...

Classes
struct	tgen::print
	Printer helper for standard types. More...
struct	tgen::println
	Printer helper for standard types, printing on a new line. More...
struct	tgen::print_cols< Args >
	Printer helper for printing containers or sequential generator elements as columns. More...
struct	tgen::weighted_sampler< T >
	Sampler for repeated draws from a fixed weighted distribution. More...
struct	tgen::distinct_range< T >
	Distinct generator for integral ranges. More...
struct	tgen::distinct_container< T >
	Distinct generator for containers. More...
struct	tgen::distinct< Func, Args >
	Distinct generator for discrete uniform functions. More...
struct	tgen::gen_base< Gen >
	Base class for generators (should not be instantiated). More...
struct	tgen::gen_value_base< Val >
	Base class for generator values (should not be instantiated). More...

Macros
#define	tgen_ensure(cond, ...)
	Ensures condition is true.

Functions
template<typename T>
T	tgen::next (T right)
	Returns a random number smaller than value.
template<typename T>
T	tgen::next (T left, T right)
	Returns a random number in range.
template<typename T>
T	tgen::wnext (T right, int w)
	Returns a skewed random number smaller than value.
template<typename T>
T	tgen::wnext (T left, T right, int w)
	Returns a skewed random number in range.
template<typename T>
size_t	tgen::next_by_distribution (const std::vector< T > &distribution)
	Returns random index with given probabilities.
template<typename T>
std::vector< int >	tgen::many_by_distribution (int k, const std::vector< T > &distribution)
	Returns many random indices with given probabilities.
template<typename It>
void	tgen::shuffle (It first, It last)
	Shuffles range inplace, for random_access_iterator.
template<typename C>
auto	tgen::shuffled (const C &container)
	Shuffles a container.
template<typename It>
It::value_type	tgen::pick (It first, It last)
	Chooses a random element from an iterator range.
template<typename C>
C::value_type	tgen::pick (const C &container)
	Chooses a random element from container.
template<typename C, typename T>
C::value_type	tgen::pick_by_distribution (const C &container, std::vector< T > distribution)
	Chooses a random element with given probabilities.
template<typename C>
C	tgen::choose (const C &container, int k)
	Chooses elements from container, as in a subsequence fixed length.

Detailed Description

Operations for basic number generation and basic random operations.

Examples

// Random number from 10 to 20.
int size = tgen::next(10, 20);
tgen_ensure(size <= 20);
 
// Several numbers in {5, 10, 15, 20}.
std::vector<int> v(size);
for (int& i : v) i = tgen::pick({5, 10, 15, 20});
 
// Shuffles the numbers.
tgen::shuffle(v.begin(), v.end());
 
// Chooses a subsequence of length 5.
v = tgen::choose(v, 5);

Macro Definition Documentation

tgen_ensure

#define tgen_ensure	(		cond,
			... )

Ensures condition is true.

Parameters

cond	Condition to be ensured.
...	Empty or a string with an error message.

Exceptions

std::runtime_error

if cond is not true.

Examples

int a = 2, b = 2;
// Without error message:
tgen_ensure(a == b);
// With error message:
tgen_ensure(a == b, "values must be the same");

Definition at line 111 of file tgen.h.

Function Documentation

choose()

template<typename C>

C tgen::choose	(	const C &	container,
		int	k )

Chooses elements from container, as in a subsequence fixed length.

Parameters

container	Container to choose from.
k	Number of elements to be chosen.

Also works with std::initializer_list.

Returns

A uniformly random subsequence of length k.

Complexity

O(|container|).

Examples

std::vector<int> v = {1, 2, 3, 4, 5};
v = tgen::choose(v, 3); // Chooses 3 elements from v.

Definition at line 1026 of file tgen.h.

many_by_distribution()

template<typename T>

std::vector< int > tgen::many_by_distribution	(	int	k,
		const std::vector< T > &	distribution )

Returns many random indices with given probabilities.

Parameters

k	Number of indices to be generated.
distribution	Probability distribution.

Returns

An std::vector of size k with: i in [0, distribution.size()-] with probability proportional to distribution[i].

Warning

Assumes that the sum of distribution fits in type unsigned __int128.

Internally builds a tgen::weighted_sampler and calls weighted_sampler::next k times.

Complexity

O(k + |distribution|).

Examples

// 1'000'000 values that are 0 or 1; 1000 times more likely to generate 1.
std::vector<int> values = tgen::many_by_distribution(1e6, {1, 1000});

Definition at line 930 of file tgen.h.

next() [1/2]

template<typename T>

T tgen::next	(	T	left,
		T	right )

Returns a random number in range.

Template Parameters

T	type to be generated. Should be an arithmetic type: int, double, long long, char, etc.

Parameters

left	Left endpoint of the range.
right	Right endpoint of the range.

Returns

A random number in [left, right], chosen uniformly.

Note

For floating-point types, sampling uses std::uniform_real_distribution ([left, right) in C++). This matches the documented closed interval because the right endpoint has probability zero.

Complexity

O(1).

Examples

// Random value from 1 to 10.
int value = tgen::next(1, 10);

Definition at line 706 of file tgen.h.

next() [2/2]

template<typename T>

T tgen::next

(

T

right

)

Returns a random number smaller than value.

Template Parameters

T	type to be generated. Should be an arithmetic type: int, double, long long, char, etc.

Parameters

right

Endpoint of the range.

Returns

A random number in [0, right), chosen uniformly.

Complexity

O(1).

Examples

// Random value from 0 to 9.
int value = tgen::next(10);
// Probability 1/3:
bool odds = tgen::next<double>(3) < 1.0;

Definition at line 685 of file tgen.h.

next_by_distribution()

template<typename T>

size_t tgen::next_by_distribution

(

const std::vector< T > &

distribution

)

Returns random index with given probabilities.

Parameters

distribution

Probability distribution.

Returns

i in [0, distribution.size()-] with probability proportional to distribution[i].

Warning

For integral T, assumes that the sum of distribution fits in type unsigned __int128.

If many indices are needed from the same distribution, prefer many_by_distribution, or build a tgen::weighted_sampler once and call weighted_sampler::next repeatedly.

Complexity

O(|distribution|).

Examples

// 0 or 1; 1000 times more likely to generate 1.
int value = tgen::next_by_distribution({1, 1000});

Definition at line 918 of file tgen.h.

pick() [1/2]

template<typename C>

C::value_type tgen::pick

(

const C &

container

)

Chooses a random element from container.

Parameters

container

Container to choose from.

Also works with std::initializer_list.

Returns

A uniformly random element from container.

Complexity

O(1) for random_access_iterator, O(|container|) otherwise.

Examples

std::vector<int> v = {1, 2, 3, 4, 5};
int value = tgen::pick(v);

Definition at line 988 of file tgen.h.

pick() [2/2]

template<typename It>

It::value_type tgen::pick	(	It	first,
		It	last )

Chooses a random element from an iterator range.

Parameters

first	First iterator of range.
last	First iterator outside of range.

Returns

A uniformly random element from the range [first, last).

Complexity

O(1) for random_access_iterator, O(|last - first|) otherwise.

Examples

std::set<int> st = {1, 2, 3, 4, 5};
int value = tgen::pick(st.begin(), st.end());

Definition at line 978 of file tgen.h.

pick_by_distribution()

template<typename C, typename T>

C::value_type tgen::pick_by_distribution	(	const C &	container,
		std::vector< T >	distribution )

Chooses a random element with given probabilities.

Parameters

container	Container to choose from.
distribution	Probability distribution.

Also works with std::initializer_list.

Returns

For i in [0, container.size()-1], container[i] with probability proportional to distribution[i].

Warning

For integral T, assumes that the sum of distribution fits in type unsigned __int128.

Complexity

O(1) for random_access_iterator, O(|container|) otherwise.

Examples

// Generates chars with custom odds.
char value = tgen::pick_by_distribution({'a', 'b', 'c'}, {1, 2, 3});

Definition at line 998 of file tgen.h.

shuffle()

template<typename It>

void tgen::shuffle	(	It	first,
		It	last )

Shuffles range inplace, for random_access_iterator.

Parameters

first	First iterator of range.
last	First iterator outside of range.

Shuffles [first, last) uniformly inplace. Works for std::vector, std::string, etc, but not std::set. For those, use tgen::shuffled(container).

Complexity

O(|last - first|).

Examples

std::vector<int> v = {1, 2, 3, 4, 5};
tgen::shuffle(v.begin(), v.end());

Definition at line 949 of file tgen.h.

shuffled()

template<typename C>

auto tgen::shuffled ( const C & container )

nodiscard

Shuffles a container.

Parameters

container

Container to be shuffled.

Works for containers and std::initializer_list. If container is ordered (std::set, etc) or std::initializer_list, returns a std::vector (implemented in a different function).

Returns

The shuffled container.

Complexity

O(|container|).

Examples

std::vector<int> st = {1, 2, 3, 4, 5};
st = tgen::shuffled(st);
st = tgen::shuffled({1, 2, 3});
st = tgen::shuffled(std::set<int>({1, 2, 3}));

Definition at line 959 of file tgen.h.

wnext() [1/2]

template<typename T>

T tgen::wnext	(	T	left,
		T	right,
		int	w )

Returns a skewed random number in range.

Template Parameters

T	Arithmetic type, same as for tgen::next.

Parameters

left	Left endpoint of the range.
right	Right endpoint of the range.
w	Skew parameter.

Returns

A value in [left, right] with bias controlled by w.

Note

For floating-point types, the underlying uniform sample uses std::uniform_real_distribution ([left, right) in C++), equivalent to the closed interval because the right endpoint has probability zero.

See tgen::wnext for more details.

Complexity

O(|w|).

Examples

// Uniform from 1 to 10.
int x = tgen::wnext<int>(1, 10, 0);
// Skewed toward 10.
int y = tgen::wnext<int>(1, 10, 3);

Definition at line 768 of file tgen.h.

wnext() [2/2]

template<typename T>

T tgen::wnext	(	T	right,
		int	w )

Returns a skewed random number smaller than value.

Template Parameters

T	Arithmetic type, same as for tgen::next.

Parameters

right	Right endpoint (half-open range), same convention as tgen::next(right).
w	Skew parameter.

Returns

A value in [0, right) with bias controlled by w.

• w = 0: uniform distribution.
• w > 0: returns the maximum of (w + 1) independent uniform samples. Biases the distribution toward larger values. The resulting density is proportional to f(x) = x^w. In particular:
  • w = 1: linear bias;
  • w = 2: quadratic bias;
  • w = 3: cubic bias.
• w < 0: returns the minimum of (-w + 1) independent uniform samples. Symmetric to the w > 0 case.

The continuous version corresponds to Beta distributions:

• w > 0: Beta(w + 1, 1);
• w < 0: Beta(1, -w + 1).

wnext distribution viewer

w = 0 is uniform. Positive w means taking the maximum of w uniform samples.
Negative w means taking the minimum of -w uniform samples.

w:

Note

Distribution might be slightly biased because of floating point arithmetic.

Complexity

O(|w|).

Examples

// Uniform on {0, ..., 9}, same as next(10).
int a = tgen::wnext<int>(10, 0);
// Biased toward larger integers in {0, ..., 9}.
int b = tgen::wnext<int>(10, 2);

Definition at line 743 of file tgen.h.