The Perm class

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

A permutation \(f\) is an injective transformation defined on the whole of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) called the degree of \(f\). A permutation is stored as a list of the images of \((0, 1, \ldots, n - 1)\), i.e. \(((0)f, (1)f, \ldots, (n - 1)f)\).

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

>>> from libsemigroups_pybind11.transf import Perm, one, inverse
>>> x = Perm([0, 2, 1, 3, 4, 5])
>>> x.degree()
6
>>> x[0]
0
>>> x[5]
5
>>> x
Perm([0, 2, 1, 3, 4, 5])
>>> x * x
Perm([0, 1, 2, 3, 4, 5])
>>> x < x * x
False
>>> y = Perm([ 5, 2, 0, 1, 3, 4, 6 ])
>>> x = one(y)
>>> x.product_inplace(y, y)
>>> x
Perm([4, 0, 5, 2, 1, 3, 6])
>>> x == y * y
True
>>> list(x.images())
[4, 0, 5, 2, 1, 3, 6]
>>> x.rank()
7
>>> one(x)
Perm([0, 1, 2, 3, 4, 5, 6])
>>> x = Perm.one(8)
>>> x
Perm([0, 1, 2, 3, 4, 5, 6, 7])
>>> x.degree()
8
>>> x.swap(y)
>>> x, y
(Perm([5, 2, 0, 1, 3, 4, 6]), Perm([0, 1, 2, 3, 4, 5, 6, 7]))
>>> x = Perm([1, 0, 2])
>>> y = x.copy()
>>> x is y
False
>>> x == y
True
>>> {x, y}
{Perm([1, 0, 2])}

Contents

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

Full API

class Perm

__init__(self: Perm, imgs: list[int]) → None

A permutation can be constructed from a list of images, as follows: the image of the point i under the permutation is imgs[i].

Parameters:

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

Raises:

LibsemigroupsError – if any value in imgs exceeds len(imgs).
LibsemigroupsError – if there are repeated values in imgs.

Complexity:

Linear in degree().

copy(self: Perm) → Perm

Copy a permutation.

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

degree(self: Perm) → int

Returns the degree of a permutation.

The degree of a permutation is the number of points used in its definition, which is equal to the size of Perm.images.

Returns:: The degree.
Return type:: int

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

Returns an iterator to the images of a permutation.

A permutation 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: Perm, m: int) → Perm

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

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

static one(N: int) → Perm

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

Parameters:: N (int) – the degree.
Returns:: The identity permutation.
Return type:: Perm

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

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

Parameters:

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

Complexity:

Linear in degree().

rank(self: Perm) → int

Returns the number of distinct image values in a permutation.

The rank of a permutation 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: Perm, other: Perm) → None

Swap with another permutation of the same type.

Parameters:: other (Perm) – the permutation to swap with.