Partial perms¶

This page contains the documentation for functionality in libsemigroups_pybind11 for partial perms.

Partial perms on up to 4294967296 points are available in libsemigroups_pybind11 using the function PPerm. PPerm 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 partial perm with fewer points requiring less space per point. If libsemigroups has been compiled with HPCombi enabled, then the objects returned by PPerm use the SSE and AVX instruction sets are used for very fast manipulation.

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

class PPerm¶

Instances of this class implement partial perms.

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

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

Equality comparison.

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

Parameters: that (PPerm) -- the partial perm for comparison.
Returns: A bool.

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

Returns the image of i.

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

__lt__(self: PPerm, that: PPerm) → 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 (PPerm) -- the partial perm for comparison.
Returns: A bool.

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

Right multiply self by that.

Parameters: that (PPerm) -- the partial perm to multiply with.
Returns: A PPerm.

degree(self: PPerm) → int¶

Returns the degree.

Returns the number of points that the partial perm is defined on.

Parameters: None
Returns: An int.

identity(self: PPerm) → int¶

Returns the identity partial perm on degree() points.

Parameters: None
Returns: A PPerm.

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

Construct and validate.

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

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

static make_identity(M: int) → PPerm¶

Returns the identity partial perm on the given number of points.

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

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

Multiply two partial perms and store the product in self.

Parameters

x (PPerm) -- a partial perm.
y (PPerm) -- a partial perm.

Returns

(None)

rank(self: PPerm) → int¶

Returns the number of distinct image values.

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

Parameters: None
Returns: An int.

images(self: PPerm) → Iterator¶

Returns an iterator pointing at the first image value.

Parameters: None
Returns: An iterator.

inverse(self: PPerm) → PPerm¶

Returns the inverse.

Parameters: None
Returns: A PPerm.

static make(dom: List[int], ran: List[int], M: int) → PPerm

Construct from domain, range, and degree, and validate.

Parameters

dom (List[int]) - the domain
ran (List[int]) - the range
M (int) - the degree

Returns

A newly constructed PPerm.

inverse(self: PPerm, that: PPerm) → None

Replace contents of a partial perm with the inverse of another.

Parameters: that (PPerm) - the partial perm to invert.
Returns: (None)

left_one(self: PPerm) → PPerm¶

Returns the left one of self.

Parameters: None.
Returns: A PPerm.

right_one(self: PPerm) → PPerm¶

Returns the right one of this.

Parameters: None.
Returns: A PPerm.

undef(self: PPerm) → int¶

Returns the integer value used to represent undefined.

Parameters: None.
Returns: An int.