tgen::distinct< Func, Args >

Distinct generator for discrete uniform functions. More...

Public Member Functions
	distinct (Func func, Args... args)
	Generates a distinct generator of a discrete uniform function.
auto	gen ()
	Generates a distinct value.
auto	gen_list (int size)
	Generates a list of several distinct values.
bool	empty ()
	Checks if there is nothing left to generate.
auto	gen_all ()
	Generates all distinct values left to generate.

Detailed Description

template<typename Func, typename... Args>
struct tgen::distinct< Func, Args >

Distinct generator for discrete uniform functions.

Examples

// Prints 10 random distinct strings.
std::cout << tgen::str("[a-z]{5}").distinct().gen_list(10) << std::endl;
 
// Prints all primes in [1, 10], in order.
std::cout << tgen::distinct(tgen::math::gen_prime, 1, 10).gen_all().sort() << std::endl;
 
// Prints some random parenthesis lists.
std::cout << tgen::distinct(tgen::misc::gen_parenthesis, 6).gen_list(5) << std::endl;
 
// Prints 5 random square numbers in [1, 1e4].
std::cout << tgen::distinct(
    [&]() {
        int x = tgen::next(1, 100);
        return x * x;
    }).gen_list(5) << std::endl;

Definition at line 235 of file tgen.h.

Constructor & Destructor Documentation

distinct()

template<typename Func, typename... Args>

tgen::distinct< Func, Args >::distinct ( Func func, Args... args )

inline

Generates a distinct generator of a discrete uniform function.

Template Parameters

Func	Automatically set to the function type.

Parameters

func	The function.
args	Arguments for the function.

Precondition

Return type of func must have less-than operator overload (operator<).
The function must be uniform on its image (every value in the function's image must have the same probability of being returned).

Examples

// Generates distinct square numbers in [1, 1e4].
auto squares = tgen::distinct(
    [&](int l, int r) {
        int x = tgen::next(l, r);
        return x * x;
    }, 1, 1e2);
// Generates distinct generator for prime numbers in [1, 100].
auto primes = tgen::distinct(gen_prime, 1, 100);

Definition at line 241 of file tgen.h.

Member Function Documentation

empty()

template<typename Func, typename... Args>

bool tgen::distinct< Func, Args >::empty ( )

inline

Checks if there is nothing left to generate.

Returns

If there is probably (with probability at least 1 - 10^(-18)) no value that has not been generated yet.

Complexity

The same as a call to distinct::gen.

Examples

// Prints all primes in [1, 10].
auto g = tgen::distinct(tgen::math::gen_prime, 1, 10);
while (!g.empty()) std::cout << g.gen() << std::endl;

Definition at line 299 of file tgen.h.

gen()

template<typename Func, typename... Args>

auto tgen::distinct< Func, Args >::gen ( )

inline

Generates a distinct value.

Template Parameters

Func	Automatically set to the function type.

Returns

A new value that has not been generated before, uniformly at random.

Exceptions

std::runtime_error

if there are probably (with probability at least 1 - 10^(-18)) no more distinct values to generate.

Complexity

O(T * log k + log^2 k) amortized expected, if the function runs in O(T) time and k distinct values have been generated.

Reference:

• Lorenz, William Andrew, and Yann Ponty. "Non-redundant random generation algorithms for weighted context-free grammars." Theoretical Computer Science 502 (2013): 177-194: Theorem 3.2.

Examples

// Prints some random distinct strings.
auto g = tgen::str("[a-z]{10}").distinct();
for (int i = 0; i < 10; ++i)
    std::cout << g.gen() << std::endl;
 
// Generates some random distinct primes in [1, 100].
g = tgen::distinct(gen_prime, 1, 100);
for (int i = 0; i < 10; ++i)
    std::cout << g.gen() << std::endl;

Definition at line 276 of file tgen.h.

gen_all()

template<typename Func, typename... Args>

auto tgen::distinct< Func, Args >::gen_all ( )

inline

Generates all distinct values left to generate.

Returns

A uniformly random tgen::list::value with all distinct values from the function with the given arguments that have not been generated yet.

Complexity

The same as calling distinct::gen until there are no more distinct values.

Examples

// Prints all primes in [1, 10].
std::cout << tgen::distinct(tgen::math::gen_prime, 1, 10).gen_all() << std::endl;

Definition at line 302 of file tgen.h.

gen_list()

template<typename Func, typename... Args>

auto tgen::distinct< Func, Args >::gen_list ( int size )

inline

Generates a list of several distinct values.

Parameters

size	Size of the list to be generated.

Returns

A uniformly random tgen::list::value with size distinct values from the function with the given arguments.

Exceptions

std::runtime_error

if there are not enough values to generate.

Complexity

The same as size calls to distinct::gen.

Examples

// Prints 10 random distinct strings.
std::cout << tgen::str("[a-z]{5}").distinct().gen_list(10) << std::endl;

Definition at line 288 of file tgen.h.

---

The documentation for this struct was generated from the following files:

• /home/runner/work/tgen/tgen/single_include/tgen.h
• base.dox