libsemigroups::bipartition Namespace Reference

This namespace contains helper functions for the Bipartition class.

Functions
Bipartition	one (Bipartition const &f)
	Return the identity bipartition with the same degree as the given bipartition.
void	random (Bipartition &x)
	Replace the contents of a bipartition with a random bipartition.
Bipartition	random (size_t deg)
	Returns a random bipartition of specified degree.
void	throw_if_invalid (Bipartition const &x)
	Checks a bipartition.
std::vector< std::vector< int32_t > >	underlying_partition (Bipartition const &x)
	Return the underlying partition of a Bipartition object.
void	uniform_random (Bipartition &x)
	Replace the contents of a bipartition with a random bipartition.
Bipartition	uniform_random (size_t deg)
	Returns a random bipartition of specified degree.

Function Documentation

one()

Bipartition one ( Bipartition const & f )

nodiscard

Parameters

f	the bipartition. Returns the identity bipartition of degree equal to f.degree().

The identity bipartition of degree \(n\) has blocks \(\{i, -i\}\) for all \(i\in \{0, \ldots, n - 1\}\). This member function returns a new identity bipartition of degree equal to the degree of this.

Returns

A newly constructed Bipartition.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

random() [1/2]

void random

(

Bipartition &

x

)

This function replaces the contents of the bipartition x with a random bipartition of degree equal to that of x, chosen at random from among all bipartitions of degree equal to x. If the degree of x is small enough for uniform_random(Bipartition&) to run successfully, then the distribution is uniform, otherwise, the distribution is not uniform.

Parameters

x	the bipartition.

random() [2/2]

Bipartition random

(

size_t

deg

)

This function returns a random bipartition of degree deg, chosen at random from among all bipartitions of degree equal to deg. If the degree deg is small enough for uniform_random(Bipartition&) to run successfully, then the distribution is uniform, otherwise, the distribution is not uniform.

Parameters

deg	the degree of the returned bipartition.

Returns

A random Bipartition.

throw_if_invalid()

void throw_if_invalid

(

Bipartition const &

x

)

This function checks a Bipartition object, and throws an exception if the object is not valid.

Parameters

x	the bipartition.

Exceptions

LibsemigroupsException

if x is invalid.

underlying_partition()

std::vector< std::vector< int32_t > > underlying_partition ( Bipartition const & x )

nodiscard

The underlying partition of a bipartition x is the partition of a subset \(P\) of \(\{-n, \ldots, -1\}\cup \{1, \ldots, n\}\) such that:

• \(\{|x|\mid x\in P\} = \{1, \ldots, n\}\);
• a block of the partition consists of negative numbers if and only if the corresponding block of x is a transverse block.

Parameters

x	the bipartition.

Returns

A vector of vectors of integers.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(n)\) where \(n\) is the degree().

uniform_random() [1/2]

void uniform_random

(

Bipartition &

x

)

This function replaces the contents of the bipartition x with a random bipartition chosen uniformly at random from among all bipartitions of degree equal to that of x.

Parameters

x	the bipartition.

Exceptions

LibsemigroupsException

if the degree of x is too large. The implementation depends on computing several values that can easily exceed the maximum value of any fixed precision integer or float type. When this occurs this exception is thrown.

Note

This function is based on Sage's random_element method for the SetPartitions class.

uniform_random() [2/2]

Bipartition uniform_random

(

size_t

deg

)

This function returns a random bipartition of degree deg, chosen uniformly at random from among all bipartitions of degree equal to deg.

Parameters

deg	the degree of the returned bipartition.

Returns

A random Bipartition.

Exceptions

LibsemigroupsException

if the degree of x is too large. The implementation depends on computing several values that can easily exceed the maximum value of any fixed precision integer or float type. When this occurs this exception is thrown.

Note

This function is based on Sage's random_element method for the SetPartitions