Transformations¶

This page contains the documentation for functionality in libsemigroups_pybind11 for transformations.

Transformations on up to 4294967296 points are available in libsemigroups_pybind11 using the function Transf. Transf is a function that returns an instance of one of a number of internal classes. These internal types are optimised for the number of points in the image of the specified transformation with fewer points requiring less space per point. If libsemigroups has been compiled with HPCombi enabled, then the objects returned by Transf use the SSE and AVX instruction sets are used for very fast manipulation.

While Transf is not a class the objects returned by Transf have identical methods, and so we document Transf as if it was a class.

class Transf¶

Instances of this class implement transformations.

A transformation \(f\) is just a function defined on the whole of \(\{0,1,\ldots,n−1\}\) for some positive integer \(n\) called the degree of \(f\). A transformation is stored as an array of the images \(\{(0)f,(1)f,\ldots,(n−1)f\}\).

__eq__(self: Transf, that: Transf) → bool¶

Equality comparison.

Returns True if self equals that by comparing their image values.

Parameters: that (Transf) -- the transformation for comparison.
Returns: A bool.

__getitem__(self: Transf, i: int) → int¶

Returns the image of i.

Parameters: i (int) -- the value whose image is sought.
Returns: An int.

__lt__(self: Transf, that: Transf) → bool¶

Less than comparison.

Returns True if the list of images of self is lexicographically less than the list of images of that.

Parameters: that (Transf) -- the transformation for comparison.
Returns: A bool.

__mul__(self: Transf, that: Transf) → Transf¶

Right multiply self by that.

Parameters: that (Transf) -- the transformation to multiply with.
Returns: A Transf.

degree(self: Transf) → int¶

Returns the degree.

Returns the number of points that the transformation is defined on.

Parameters: None
Returns: An int.

identity(self: Transf) → int¶

Returns the identity transformation on degree() points.

Parameters: None
Returns: A Transf.

static make(l: List[int]) → Transf¶

Construct and validate.

Constructs a transformation initialized using list l as follows: the image of the point i under the transformation is l[i].

Parameters: l (List[int]) -- the list of images.
Returns: A newly constructed transformation.
Return type: Transf
Raises: RuntimeError -- if any value in l exceeds len(l).

static make_identity(M: int) → Transf¶

Returns the identity transformation on the given number of points.

Parameters: M (int) - the degree.
Returns: A value of type Transf.

product_inplace(self: Transf, x: Transf, y: Transf) → None¶

Multiply two transformations and store the product in self.

Parameters

x (Transf) -- a transformation.
y (Transf) -- a transformation.

Returns

(None)

rank(self: Transf) → int¶

Returns the number of distinct image values.

The rank of a transformation is the number of its distinct image values.

Parameters: None
Returns: An int.

images(self: Transf) → Iterator¶

Returns an iterator pointing at the first image value.

Parameters: None
Returns: An iterator.