The PPerm class

Class for representing partial permutations on up to 2 ** 32 points.

A partial permutation \(f\) is just an injective partial transformation, which is stored as a list of the images of \(\{0, 1, \ldots, n - 1\}\), i.e. \(((0)f, (1)f, \ldots, (n - 1)f)\) where the value UNDEFINED is used to indicate that \((i)f\) is undefined (i.e. not among the points where \(f\) is defined).

These partial permutations are optimised for the number of points in the image with fewer points requiring less space per point.

>>> from libsemigroups_pybind11.transf import PPerm, one, inverse, right_one, left_one, domain, image
>>> from libsemigroups_pybind11 import UNDEFINED
>>> x = PPerm([1, 0, 2], [0, 1, 2], 4)
>>> x.degree()
4
>>> x[0]
1
>>> x[3] == UNDEFINED
True
>>> x * x
PPerm([0, 1, 2], [0, 1, 2], 4)
>>> x * x == x
False
>>> x < x * x
False
>>> y = x.copy()
>>> x.product_inplace(y, y)
>>> x
PPerm([0, 1, 2], [0, 1, 2], 4)
>>> list(x.images())
[0, 1, 2, UNDEFINED]
>>> x.rank()
3
>>> one(x)
PPerm([0, 1, 2, 3], [0, 1, 2, 3], 4)
>>> x = PPerm.one(8)
>>> x
PPerm([0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7], 8)
>>> x.degree()
8
>>> x.swap(y)
>>> x, y
(PPerm([0, 1, 2], [1, 0, 2], 4), PPerm([0, 1, 2, 3, 4, 5, 6, 7], [0, 1, 2, 3, 4, 5, 6, 7], 8))
>>> y = x.copy()
>>> {x, y}
{PPerm([0, 1, 2], [1, 0, 2], 4)}
>>> x = PPerm([255, 3, 255, 0])
>>> x
PPerm([1, 3], [3, 0], 4)
>>> x * inverse(x) * x == x and inverse(x) * x * inverse(x) == inverse(x)
True
>>> x * right_one(x) == x
True
>>> left_one(x) * x == x
True
>>> domain(left_one(x) * right_one(x)) == list(set(domain(x)) & set(image(x)))
True

Contents

`PPerm`	Class for representing partial permutations on up to `2 ** 32` points.
`PPerm.copy`(…)	Copy a partial perm.
`PPerm.images`(…)	Returns an iterator to the images of a partial perm.
`PPerm.increase_degree_by`(…)	Increases the degree of self in-place, leaving existing values unaltered.
`PPerm.one`(…)	Returns the identity partial perm on N points.
`PPerm.product_inplace`(…)	Replaces the contents of self by the product of x and y.
`PPerm.rank`(…)	Returns the number of distinct image values in a partial perm.
`PPerm.swap`(…)	Swap with another partial perm of the same type.

Full API

class PPerm

__init__(*args, **kwargs)

Overloaded function.

__init__(self: PPerm, imgs: list[int | Undefined]) → None

A partial perm can be constructed from a list of images, as follows: the image of the point i under the {1} is imgs[i].

Parameters:

imgs (list[int | Undefined]) – the list of images.

Raises:

LibsemigroupsError – if there are repeated values in imgs that do not equal UNDEFINED.
LibsemigroupsError – if any integer value in imgs exceeds len(imgs).

Complexity:

Linear in degree().

__init__(self: PPerm, dom: list[int], im: list[int], n: int) → None

Construct from domain, image, and degree.

Constructs a partial perm of degree n such that (dom[i])f = im[i] for all i and which is UNDEFINED on every other value in the range \([0, n)\).

Parameters:

dom (list[int]) – the domain.
im (list[int]) – the image.
n (int) – the degree.

Raises:

LibsemigroupsError – the value n is not compatible with the type.
LibsemigroupsError – dom and im do not have the same size.
LibsemigroupsError – any value in dom or im is greater than n.
LibsemigroupsError – there are repeated entries in dom or im.

copy(self: PPerm) → PPerm

Copy a partial perm.

Returns:: A copy of the argument.
Return type:: PPerm

degree(self: PPerm) → int

Returns the degree of a partial perm.

The degree of a partial perm is the number of points used in its definition, which is equal to the size of PPerm.images.

Returns:: The degree.
Return type:: int

images(self: PPerm) → collections.abc.Iterator[int]

Returns an iterator to the images of a partial perm.

A partial perm is stored as a list of the images of \(\{0, 1, \ldots, n - 1\}\), i.e. \([(0)f, (1)f, \ldots, (n - 1)f]\), and this function returns an iterator yielding these values.

Returns:: An iterator to the image values.
Return type:: collections.abc.Iterator[int]

increase_degree_by(self: PPerm, m: int) → PPerm

Increases the degree of self in-place, leaving existing values unaltered.

Parameters:: m (int) – the number of points to add.
Returns:: self
Return type:: PPerm
Complexity:: At worst linear in the sum of the parameter m and degree().

static one(N: int) → PPerm

Returns the identity partial perm on N points. This function returns a newly constructed partial perm with degree equal to N that fixes every value from 0 to N.

Parameters:: N (int) – the degree.
Returns:: The identity partial perm.
Return type:: PPerm

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

Replaces the contents of self by the product of x and y.

Parameters:

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

Complexity:

Linear in degree().

rank(self: PPerm) → int

Returns the number of distinct image values in a partial perm.

The rank of a partial perm is the number of its distinct image values, not including UNDEFINED.

Returns:: The number of distinct image values.
Return type:: int
Complexity:: Linear in degree().

swap(self: PPerm, other: PPerm) → None

Swap with another partial perm of the same type.

Parameters:: other (PPerm) – the partial perm to swap with.