Permutations¶

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

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

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

class Perm¶

Instances of this class implement permutations.

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

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

Equality comparison.

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

Parameters: that (Perm) -- the permutation for comparison.
Returns: A bool.

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

Returns the image of i.

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

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

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

Right multiply self by that.

Parameters: that (Perm) -- the permutation to multiply with.
Returns: A Perm.

degree(self: Perm) → int¶

Returns the degree.

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

Parameters: None
Returns: An int.

identity(self: Perm) → int¶

Returns the identity permutation on degree() points.

Parameters: None
Returns: A Perm.

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

Construct and validate.

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

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

static make_identity(M: int) → Perm¶

Returns the identity permutation on the given number of points.

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

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

Multiply two permutations and store the product in self.

Parameters

x (Perm) -- a permutation.
y (Perm) -- a permutation.

Returns

(None)

rank(self: Perm) → int¶

Returns the number of distinct image values.

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

Parameters: None
Returns: An int.

images(self: Perm) → Iterator¶

Returns an iterator pointing at the first image value.

Parameters: None
Returns: An iterator.

inverse(self: Perm) → Perm¶

Returns the inverse.

Parameters: None
Returns: A Perm.