Permutation generators

Defines a set of permutations, subject to restrictions. More...

Classes
struct	tgen::permutation
	Permutation generator. More...

Functions
	tgen::permutation::permutation (int size)
	Creates permutation generator defined by size.
permutation &	tgen::permutation::set (int idx, int value)
	Restricts generator s.t. value at index is fixed.
instance	tgen::permutation::gen () const
	Generates a random instance from the set of valid permutations.
instance	tgen::permutation::gen (std::vector< int > cycle_sizes) const
	Generates a random instance from the set of valid permutations, given a list of cycle sizes.
template<typename Gen, typename Pred, typename... Args>
instance	tgen::permutation::gen_until (Pred predicate, int max_tries, Args &&... args) const
	Generates a random instance from the set of valid permutations until a condition is met.

Detailed Description

Defines a set of permutations, subject to restrictions.

A uniformly random tgen::permutation::instance (see Permutation instances) from this set of permutations (that satisfies the restrictions) can be generated with tgen::permutation::gen.

Function Documentation

gen() [1/2]

instance tgen::permutation::gen ( ) const

inline

Generates a random instance from the set of valid permutations.

Exceptions

std::runtime_error

if there is no valid permutation satisfying all added constraints.

Complexity

O(n).

Examples

// Generates and prints a random permutation of size 5.
auto inst = tgen::permutation(5).gen();
std::cout << inst << std::endl;

Definition at line 1213 of file tgen.h.

gen() [2/2]

instance tgen::permutation::gen ( std::vector< int > cycle_sizes ) const

inline

Generates a random instance from the set of valid permutations, given a list of cycle sizes.

Parameters

cycle_sizes

Sizes of cycles.

The sizes of cycles of the generated permuttion will be cycle_sizes. The permutation is generated uniformly at random among all permutations with these cycle sizes.

Exceptions

std::runtime_error

if there is no valid permutation satisfying all added constraints.

Complexity

O(n).

Examples

// Generates and prints a random permutation of size 5 with only one cycle.
auto inst = tgen::permutation(5).gen({5});
std::cout << inst << std::endl;

Definition at line 1249 of file tgen.h.

gen_until()

template<typename Gen, typename Pred, typename... Args>

instance gen_until	(	Pred	predicate,
		int	max_tries,
		Args &&...	args ) const

Generates a random instance from the set of valid permutations until a condition is met.

Template Parameters

Gen	Automatically set to tgen::permutation.
Pred	Type of predicate, deduced automatically.
Args	Empty or std::vector<int> with cycle sizes, deduced automatically.

Parameters

predicate	Condition to be checked. Should be a function that takes in a tgen::sequence::instance, and returns a bool.
max_tries	The maximum number of times the function will try to generate a valid instance satisfying predicate.
args	Arguments for the the function tgen::permutation::gen.

Calls tgen::permutation::gen(args...) until predicate is true, at most max_tries times. If predicate has probabiliyy p of returning true, then the tgen::sequence::instance will be found with probability 1 - (1-p)^max_tries.

Returns

An instance found by repeatedly choosing a uniformly random valid permutation and checking if it satisfies predicate.

Exceptions

std::runtime_error

if no valid instance satisfying predicate is found after max_tries tries.

Complexity

O((1/p) n log n) expected, O(max_tries * n log n) worst case.

Examples

// Prints a random odd permutation of size 5.
std::cout <<
    tgen::permutation(5)
        .gen_until([](const auto &perm) { return perm.parity() == -1; }, 100)
  << std::endl;
 
// Prints a random odd permutation of size 5 with one cycle.
std::cout <<
    tgen::permutation(5)
        .gen_until([](const auto &perm) { return perm.parity() == -1; }, 100, {5})
  << std::endl;

permutation()

tgen::permutation::permutation ( int size )

inline

Creates permutation generator defined by size.

Parameters

size	Size of the permutation.

Examples

// Permutations of size 10.
auto perm_gen = tgen::permutation(10);

Definition at line 1107 of file tgen.h.

set()

permutation & tgen::permutation::set ( int idx, int value )

inline

Restricts generator s.t. value at index is fixed.

Parameters

idx	Index.
value	Value.

Examples

// Permutations of size 10 that start with 1.
auto perm_gen = tgen::permutation(10).set(0, 1);

Definition at line 1112 of file tgen.h.