Functions for words and strings

This page contains the documentation of several useful functions for counting and creating words and strings. Additionally, this page also contains the documentation of the words module; a module for more specialist constructions of words, and other helpful functions.

Constructing and counting words and strings

random_word(length: int, nr_letters: int) → list[int]

Returns a random word.

Parameters:

length (int) – the length of the word.
nr_letters (int) – the size of the alphabet.

Returns:

A random word on [0, ..., nr_letters - 1] of length length.

Return type:

list[int]

Raises:

LibsemigroupsError – if nr_letters is 0.

See also

random_string().

random_string(*args, **kwargs)

Overloaded function.

random_string(alphabet: str, length: int) → str

Returns a random string.

Returns a random string with the specified length over the specified alphabet.

Parameters:

alphabet (str) – the alphabet over which the string is constructed.
length (int) – the length of the string.

Returns:

A random string.

Return type:

str

See also

random_word

random_string(alphabet: str, min: int, max: int) → str

Returns a random string.

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

Parameters:

alphabet (str) – the alphabet over which the string is constructed.
min (int) – the minimum length of the returned string.
max (int) – one above the maximum length of the returned string.

Returns:

A random string.

Return type:

str

Raises:

LibsemigroupsError – if min > max;
LibsemigroupsError – if len(alphabet) == 0 and min != 0.

See also

random_word

random_strings(alphabet: str, number: int, min: int, max: int) → collections.abc.Iterator[str]

Returns an iterator of random strings.

Returns an iterator of random strings, each of which with random length in the range [min, max) over the specified alphabet.

Parameters:

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

Returns:

An iterator of random strings.

Return type:

collections.abc.Iterator[str]

Raises:

LibsemigroupsError – if min is greater than max;
LibsemigroupsError – if len(alphabet) == 0 and min != 0.

See also

random_word

number_of_words(n: int, min: int, max: int) → int

Returns the number of words over a given alphabet in some range.

Parameters:

n (int) – the number of letters.
min (int) – the minimum length of a word.
max (int) – one greater than the maximum length of a word.

Returns:

The number words over an alphabet with n letters with length in the range [min, max).

Return type:

int

>>> from libsemigroups_pybind11 import number_of_words
>>> number_of_words(2, 0, 10)
1023

The words module

Contents

`human_readable_index`(…)	Returns the index of a character in human readable order.
`human_readable_letter`(…)	Returns a character by index in human readable order.
`parse_relations`(…)	Construct string by parsing an algebraic expression.
`pow`(…)	Returns the power of a word.
`prod`(…)	Overloaded function.

Full API

This page contains the documentation for the words subpackage, that contains helper functions related to words.

words.human_readable_index(c: str) → int

Returns the index of a character in human readable order.

This function is the inverse of words.human_readable_letter, see the documentation of that function for more details.

Parameters:: c (str) – character whose index is sought.
Returns:: The human readable index.
Return type:: int
Raises:: ValueError – if c is not exactly one character long.

See also

words.human_readable_letter

words.human_readable_letter(i: int) → str

Returns a character by index in human readable order.

This function exists to map the numbers 0 to 255 to the possible values of a one-byte char, in such a way that the first characters are a-zA-Z0-9. The ascii ranges for these characters are: \([97, 123)\), \([65, 91)\), \([48, 58)\) so the remaining range of chars that are appended to the end after these chars are \([0,48)\), \([58, 65)\), \([91, 97)\), \([123, 255]\).

This function is the inverse of words.human_readable_index.

Parameters:: i (int) – the index of the character.
Returns:: The human readable character.
Return type:: str
Raises:: LibsemigroupsError – if i exceeds 255.

words.parse_relations(w: str) → str

Construct string by parsing an algebraic expression.

This function provides a means of constructing a str from an algebraic expression, and has the following behaviour: * arbitrarily nested brackets; * spaces are ignored; * redundant matched brackets are ignored; * only the characters in "()^ " and in a-zA-Z0-9 are allowed.

Parameters:: w (str) – the expression to parse.
Returns:: The parsed expression.
Return type:: str
Raises:: LibsemigroupsError – if w cannot be parsed.

>>> from libsemigroups_pybind11.words import parse_relations
>>> parse_relations("((ab)^3cc)^2")
'abababccabababcc'
>>> parse_relations("a^0")
''

words.pow(w: list[int] | str, n: int) → list[int] | str

Returns the power of a word.

Returns the word w to the power n.

Parameters:

w (list[int] | str) – the word to power.
n (int) – the power.

Returns:

The powered word.

Return type:

list[int] | str

words.prod(*args, **kwargs)

Overloaded function.

words.prod(elts: list[int] | str, first: int, last: int, step: int = 1) → list[int] | str

Returns a product of letters.

Let elts correspond to the ordered set \(a_0, a_1, \ldots, a_{n -1}\) , first to \(f\) , last to \(l\) , and step to \(s\). If \(f \leq l\) , let \(k\) be the greatest positive integer such that \(f + ks < l\). Then this function returns the word corresponding to \(a_f a_{f + s} a_{f + 2s} \cdots a_{f + ks}\). All subscripts are taken modulo \(n\).

If there is no such \(k\) (i.e. \(s < 0\) , or \(f = l\) ), then the empty word is returned.

Where \(f > l\) , the function works analogously, where \(k\) is the greatest positive integer such that \(f + k s > l\).

Parameters:

elts (list[int] | str) – the ordered set.
first (int) – the first index.
last (int) – the last index.
step (int) – the step.

Returns:

The word produced.

Return type:

list[int] | str

Raises:

LibsemigroupsError – if step = 0;
LibsemigroupsError – if elts is empty, but the specified range is not.

>>> from libsemigroups_pybind11.words import prod
>>> w  =  "abcdef"
>>> prod(w,  0,  5,  2)
'ace'
>>> prod(w,  1,  9,  2)
'bdfb'
>>> prod(w,  4,  1,  -1)
'edc'

>>> w  =  [0, 1, 2, 3, 4, 5]
>>> prod(w,  0,  5,  2)
[0, 2, 4]
>>> prod(w,  1,  9,  2)
[1, 3, 5, 1]
>>> prod(w,  4,  1,  -1)
[4, 3, 2]

words.prod(elts: list[int] | str, last: int) → list[int] | str

Returns a product of letters or words.

Parameters:

elts (list[int] | str) – the ordered set.
last (int) – the last index.

Returns:

The word produced.

Return type:

list[int] | str

Raises:

LibsemigroupsError – if elts is empty, but the specified range is not.

Note

This returns the same as prod(elts, 0, last, 1).