Words

This page contains details of the functionality in libsemigroups related to generating words in a given range and in a given order.

This file contains documentation for functionality for:

• generating words and strings in a given range and in a certain order:
  • WordRange
  • StringRange
  • random_word
  • random_string
  • random_strings
• counting words:
  • number_of_words
• converting to and from strings and words:
  • ToWord
  • ToString
• parsing algebraic expressions in a string:
  • literal_operator_p

Namespaces
namespace	libsemigroups::literals
	Namespace containing some custom literals for creating words.
namespace	libsemigroups::words
	Namespace containing some operators for creating words.

Classes
class	StringRange
	Class for generating strings in a given range and in a particular order. More...
class	ToString
	Class for converting word_type into std::string with specified alphabet. More...
class	ToWord< From >
	Class for converting strings to word_type with specified alphabet. More...
class	WordRange
	Class for generating words in a given range and in a particular order. More...

Functions
detail::const_wilo_iterator	cbegin_wilo (size_t n, size_t upper_bound, word_type &&first, word_type &&last)
	Returns a forward iterator pointing to the 3rd parameter first.
detail::const_wilo_iterator	cbegin_wilo (size_t n, size_t upper_bound, word_type const &first, word_type const &last)
	Returns a forward iterator pointing to the 3rd parameter first.
detail::const_wislo_iterator	cbegin_wislo (size_t n, word_type &&first, word_type &&last)
	Returns a forward iterator pointing to the 2nd parameter first.
detail::const_wislo_iterator	cbegin_wislo (size_t n, word_type const &first, word_type const &last)
	Returns a forward iterator pointing to the 2nd parameter first.
detail::const_wilo_iterator	cend_wilo (size_t n, size_t upper_bound, word_type &&first, word_type &&last)
	Returns a forward iterator pointing to one after the end of the range from first to last.
detail::const_wilo_iterator	cend_wilo (size_t n, size_t upper_bound, word_type const &first, word_type const &last)
	Returns a forward iterator pointing to one after the end of the range from first to last.
detail::const_wislo_iterator	cend_wislo (size_t n, word_type &&first, word_type &&last)
	Returns a forward iterator pointing to one after the end of the range from first to last.
detail::const_wislo_iterator	cend_wislo (size_t n, word_type const &first, word_type const &last)
	Returns a forward iterator pointing to one after the end of the range from first to last.
uint64_t	number_of_words (size_t n, size_t min, size_t max)
	Returns the number of words over an alphabet with a given number of letters with length in a specified range.
std::string	random_string (std::string const &alphabet, size_t length)
	Returns a random string.
std::string	random_string (std::string const &alphabet, size_t min, size_t max)
	Returns a random string.
auto	random_strings (std::string const &alphabet, size_t number, size_t min, size_t max)
	Returns a range object of random strings.
word_type	random_word (size_t length, size_t nr_letters)
	Returns a random word.
template<typename Word>
Word &	reverse (Word &&w)
	Reverse an object.
std::string	to_human_readable_repr (StringRange const &sr, size_t max_width=72)
	Return a human readable representation of a StringRange object.
std::string	to_human_readable_repr (ToString const &tstr)
	Return a human readable representation of a ToString object.
std::string	to_human_readable_repr (WordRange const &wr, size_t max_width=72)
	Return a human readable representation of a WordRange object.
template<typename From>
std::string	to_human_readable_repr (ToWord< From > const &twrd)
	Return a human readable representation of a ToWord object.

Function Documentation

cbegin_wilo() [1/2]

detail::const_wilo_iterator cbegin_wilo ( size_t n, size_t upper_bound, word_type && first, word_type && last )

nodiscard

Returns a forward iterator used to iterate over words in lexicographic order (wilo). If incremented, the iterator will point to the next least lexicographic word after first over an n letter alphabet with length less than upper_bound. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wilo by the same amount, or they are both obtained by any call to cend_wilo.

Parameters

n	the number of letters in the alphabet.
upper_bound	only words of length less than this value are considered.
first	the starting point for the iteration.
last	the value one past the end of the last value in the iteration.

Returns

An iterator pointing to first.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Note

The parameter upper_bound is required because lexicographical ordering is not a well-ordering, and there might be infinitely many words between a given pair of words.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wilo is significantly cheaper than postfix incrementing it++.

Iterators constructed using different parameters may not be equal, so best not to loop over them.

See also

cend_wilo

Example

std::vector<word_type>(cbegin_wilo(2, 3, {0}, {1, 1, 1}),
                       cend_wilo(2, 3, {0}, {1, 1, 1}));
// {{0}, {0, 0}, {0, 1}, {1}, {1, 0}, {1, 1}};

cbegin_wilo() [2/2]

detail::const_wilo_iterator cbegin_wilo ( size_t n, size_t upper_bound, word_type const & first, word_type const & last )

nodiscard

Returns a forward iterator pointing to the 3rd parameter first.

Returns a forward iterator used to iterate over words in lexicographic order (wilo). If incremented, the iterator will point to the next least lexicographic word after first over an n letter alphabet with length less than upper_bound. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wilo by the same amount, or they are both obtained by any call to cend_wilo.

Parameters

n	the number of letters in the alphabet.
upper_bound	only words of length less than this value are considered.
first	the starting point for the iteration.
last	the value one past the end of the last value in the iteration.

Returns

An iterator pointing to first.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Note

The parameter upper_bound is required because lexicographical ordering is not a well-ordering, and there might be infinitely many words between a given pair of words.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wilo is significantly cheaper than postfix incrementing it++.

Iterators constructed using different parameters may not be equal, so best not to loop over them.

See also

cend_wilo

Example

std::vector<word_type>(cbegin_wilo(2, 3, {0}, {1, 1, 1}),
                       cend_wilo(2, 3, {0}, {1, 1, 1}));
// {{0}, {0, 0}, {0, 1}, {1}, {1, 0}, {1, 1}};

cbegin_wislo() [1/2]

detail::const_wislo_iterator cbegin_wislo ( size_t n, word_type && first, word_type && last )

nodiscard

Returns a forward iterator used to iterate over words in short-lexicographic order (wislo). If incremented, the iterator will point to the next least short-lex word after w over an n letter alphabet. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wislo by the same amount, or they are both obtained by any call to cend_wislo.

Parameters

n	the number of letters in the alphabet.
first	the starting point for the iteration.
last	the ending point for the iteration.

Returns

An iterator pointing to first.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wislo is significantly cheaper than postfix incrementing it++.

Iterators constructed using different parameters may not be equal, so best not to loop over them.

See also

cend_wislo

Example

std::vector<word_type>(cbegin_wislo(2, {0}, {0, 0, 0}),
                       cend_wislo(2,  {0}, {0, 0, 0}));
// {{0}, {1}, {0, 0}, {0, 1}, {1, 0}, {1, 1}};

cbegin_wislo() [2/2]

detail::const_wislo_iterator cbegin_wislo ( size_t n, word_type const & first, word_type const & last )

nodiscard

Returns a forward iterator pointing to the 2nd parameter first.

Returns a forward iterator used to iterate over words in short-lexicographic order (wislo). If incremented, the iterator will point to the next least short-lex word after w over an n letter alphabet. Iterators of the type returned by this function are equal whenever they are obtained by advancing the return value of any call to cbegin_wislo by the same amount, or they are both obtained by any call to cend_wislo.

Parameters

n	the number of letters in the alphabet.
first	the starting point for the iteration.
last	the ending point for the iteration.

Returns

An iterator pointing to first.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

Copying iterators of this type is expensive. As a consequence, prefix incrementing ++it the iterator it returned by cbegin_wislo is significantly cheaper than postfix incrementing it++.

Iterators constructed using different parameters may not be equal, so best not to loop over them.

See also

cend_wislo

Example

std::vector<word_type>(cbegin_wislo(2, {0}, {0, 0, 0}),
                       cend_wislo(2,  {0}, {0, 0, 0}));
// {{0}, {1}, {0, 0}, {0, 1}, {1, 0}, {1, 1}};

cend_wilo() [1/2]

detail::const_wilo_iterator cend_wilo ( size_t n, size_t upper_bound, word_type && first, word_type && last )

nodiscard

The iterator returned by this function is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wilo

cend_wilo() [2/2]

detail::const_wilo_iterator cend_wilo ( size_t n, size_t upper_bound, word_type const & first, word_type const & last )

nodiscard

Returns a forward iterator pointing to one after the end of the range from first to last.

The iterator returned by this function is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wilo

cend_wislo() [1/2]

detail::const_wislo_iterator cend_wislo ( size_t n, word_type && first, word_type && last )

nodiscard

The iterator returned by this is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wislo

cend_wislo() [2/2]

detail::const_wislo_iterator cend_wislo ( size_t n, word_type const & first, word_type const & last )

nodiscard

Returns a forward iterator pointing to one after the end of the range from first to last.

The iterator returned by this is still dereferenceable and incrementable, but does not point to a word in the correct range.

See also

cbegin_wislo

number_of_words()

uint64_t number_of_words ( size_t n, size_t min, size_t max )

nodiscard

Returns the number of words over an alphabet with a given number of letters with length in a specified range.

Parameters

n	the number of letters in the alphabet.
min	the minimum length of a word.
max	one greater than the maximum length of a word.

Returns

A value of type uint64_t.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

If the number of words exceeds 2 ^ 64 - 1, then the return value of this function will not be correct.

random_string() [1/2]

std::string random_string	(	std::string const &	alphabet,
		size_t	length )

Returns a random string with length length over alphabet alphabet.

Parameters

alphabet	the alphabet over which the string is constructed.
length	the length of the string.

Returns

A random string, value of std::string.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

See also

random_word

random_string() [2/2]

std::string random_string	(	std::string const &	alphabet,
		size_t	min,
		size_t	max )

Returns a random string with random length in the range [min, max) over alphabet alphabet.

Parameters

alphabet	the alphabet over which the string is constructed.
min	the minimum length of the returned string.
max	one above the maximum length of the returned string.

Returns

A random string, value of std::string.

Exceptions

LibsemigroupsException

if either: min > max; or alphabet.size() == 0 and min != 0.

See also

random_word

random_strings()

auto random_strings ( std::string const & alphabet, size_t number, size_t min, size_t max )

inline

Returns a range object of random strings, each of which with random length in the range [min, max) over alphabet alphabet.

Parameters

alphabet	the alphabet over which the string is constructed.
number	the number of random strings to construct.
min	the minimum length of the returned string.
max	one above the maximum length of the returned string.

Returns

A range of random strings.

Exceptions

LibsemigroupsException

if either: min > max; or alphabet.size() == 0 and min != 0.

See also

random_word

random_word()

word_type random_word ( size_t length, size_t nr_letters )

nodiscard

Returns a random word on \(\{0, \ldots, n - 1\}\) of length length where \(n\) is nr_letters.

Parameters

length	the length of the word.
nr_letters	the size of the alphabet.

Returns

A random word, value of word_type.

Exceptions

LibsemigroupsException

if nr_letters is 0.

See also

random_string

reverse()

template<typename Word>

Word & reverse

(

Word &&

w

)

This function just calls std::reverse(w.begin(), w.end()) and is for convenience.

Template Parameters

Word.

Parameters

w	the word to reverse.

Returns

A reference to the parameter w.

to_human_readable_repr() [1/4]

std::string to_human_readable_repr ( StringRange const & sr, size_t max_width = 72 )

nodiscard

Return a human readable representation of a StringRange object.

Parameters

sr	the StringRange object.
max_width	the maximum width of the returned string (default: 72).

Exceptions

This function guarantees not to throw a LibsemigroupsException.

to_human_readable_repr() [2/4]

std::string to_human_readable_repr ( ToString const & tstr )

inlinenodiscard

Return a human readable representation of a ToString object.

Parameters

tstr	the ToString object.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

to_human_readable_repr() [3/4]

std::string to_human_readable_repr ( WordRange const & wr, size_t max_width = 72 )

nodiscard

Return a human readable representation of a WordRange object.

Parameters

wr	the WordRange object.
max_width	the maximum width of the returned string (default: 72).

Exceptions

This function guarantees not to throw a LibsemigroupsException.

to_human_readable_repr() [4/4]

template<typename From>

std::string to_human_readable_repr ( ToWord< From > const & twrd )

nodiscard

Return a human readable representation of a ToWord object.

Parameters

twrd	the ToWord object.

Exceptions

This function guarantees not to throw a LibsemigroupsException.