permutation — Permutations of finitely many positive integers
GitHub | PyPI | Documentation | Issues | Changelog
permutation
provides a Permutation
class for representing permutations of finitely many positive
integers in Python. Supported operations & properties include inverses, (group
theoretic) order, parity, composition/multiplication, cycle decomposition,
cycle notation, word representation, Lehmer codes, and, of course, use as a
callable on integers.
Installation
permutation
requires Python 3.8 or higher. Just use pip for Python 3 (You have pip, right?) to install:
python3 -m pip install permutation
Examples
>>> from permutation import Permutation
>>> p = Permutation(2, 1, 4, 5, 3)
>>> p(1)
2
>>> p(3)
4
>>> p(42)
42
>>> p.to_cycles()
[(1, 2), (3, 4, 5)]
>>> print(p)
(1 2)(3 4 5)
>>> print(p.inverse())
(1 2)(3 5 4)
>>> p.degree
5
>>> p.order
6
>>> p.is_even
False
>>> p.lehmer(5)
27
>>> q = Permutation.cycle(1,2,3)
>>> print(p * q)
(2 4 5 3)
>>> print(q * p)
(1 3 4 5)
>>> for p in Permutation.group(3):
... print(p)
...
1
(1 2)
(2 3)
(1 3 2)
(1 2 3)
(1 3)
API
- class permutation.Permutation(*img: int)[source]
A
Permutation
object represents a permutation of finitely many positive integers, i.e., a bijective function from some integer range \([1,n]\) to itself.Permutation
s are hashable and immutable. They can be compared for equality but not for ordering/sorting.Construction:
__init__
(*img)Construct a permutation from a word representation.
parse
(s)Parse a permutation written in cycle notation.
cycle
(*cyc)Construct a cyclic permutation.
from_cycles
(*cycles)Construct the product of cyclic permutations.
from_lehmer
(x, n)Calculate the permutation in \(S_n\) with Lehmer code
x
.Calculate the permutation with the given left Lehmer code.
group
(n)Generates all permutations in \(S_n\).
Returns the next
Permutation
in left Lehmer code orderReturns the previous
Permutation
in left Lehmer code orderOperations:
__call__
(i)Map an integer through the permutation.
__mul__
(other)Multiplication/composition of permutations.
__pow__
(n)Power/repeated composition of permutations.
permute
(xs)Returns the elements of
xs
reordered according to the permutation.Properties:
__str__
()Convert a
Permutation
to cycle notation.__bool__
()A
Permutation
is true iff it is not the identity.inverse
()Returns the inverse of the permutation.
The degree of the permutation.
The order/period of the permutation.
Whether the permutation is even.
Whether the permutation is odd, i.e., not even
The sign/signature of the permutation.
isdisjoint
(other)Tests whether the permutation is disjoint from
other
.to_image
([n])Returns the images of 1 through
n
under the permutation.Decompose the permutation into a product of disjoint cycles.
Calculate the right inversion count through degree
n
.Calculate the inversion number of the permutation.
lehmer
(n)Calculate a Lehmer code for the permutation.
Calculate the "left Lehmer code" for the permutation.
- __bool__() bool [source]
A
Permutation
is true iff it is not the identity.
- __call__(i: int) int [source]
Map an integer through the permutation. Values less than 1 are returned unchanged.
- Parameters:
i (int)
- Returns:
the image of
i
under the permutation
- __init__(*img: int) None [source]
Construct a permutation from a word representation. The arguments are the images of the integers 1 through some \(n\) under the permutation to construct.
For example,
Permutation(5, 4, 3, 6, 1, 2)
is the permutation that maps 1 to 5, 2 to 4, 3 to itself, 4 to 6, 5 to 1, and 6 to 2.Permutation()
(with no arguments) evaluates to the identity permutation (i.e., the permutation that returns all inputs unchanged).
- __mul__(other: Permutation) Permutation [source]
Multiplication/composition of permutations.
p * q
returns aPermutation
r
such thatr(x) == p(q(x))
for all integersx
.- Parameters:
other (Permutation)
- Return type:
- __pow__(n: int) Permutation [source]
Power/repeated composition of permutations.
p ** 0 == Permutation()
p ** n == p ** (n - 1) * p
p ** -n == p.inverse() ** n
- Parameters:
n (int) – exponent
- Return type:
- __str__() str [source]
Convert a
Permutation
to cycle notation. The instance is decomposed into cycles withto_cycles()
, each cycle is written as a parenthesized space-separated sequence of integers, and the cycles are concatenated.str(Permutation())
is"1"
.This is the inverse of
parse
.>>> str(Permutation(2, 5, 4, 3, 1)) '(1 2 5)(3 4)'
- classmethod cycle(*cyc: int) Permutation [source]
Construct a cyclic permutation. If
p = Permutation.cycle(*cyc)
, thenp(cyc[0]) == cyc[1]
,p(cyc[1]) == cyc[2]
, etc., andp(cyc[-1]) == cyc[0]
, withp
returning all other values unchanged.Permutation.cycle()
(with no arguments) evaluates to the identity permutation.- Parameters:
cyc – zero or more distinct positive integers
- Returns:
the permutation represented by the given cycle
- Raises:
if
cyc
contains a value less than 1if
cyc
contains the same value more than once
- property degree: int
The degree of the permutation. This is the largest integer that it permutes (does not map to itself), or 0 if there is no such integer (i.e., if the permutation is the identity).
- classmethod from_cycles(*cycles: Iterable[int]) Permutation [source]
Construct the product of cyclic permutations. Each element of
cycles
is converted to aPermutation
withcycle
, and the results (which need not be disjoint) are multiplied together.Permutation.from_cycles()
(with no arguments) evaluates to the identity permutation.This is the inverse of
to_cycles
.- Parameters:
cycles – zero or more iterables of distinct positive integers
- Returns:
the
Permutation
represented by the product of the cycles- Raises:
if any cycle contains a value less than 1
if any cycle contains the same value more than once
- classmethod from_left_lehmer(x: int) Permutation [source]
Calculate the permutation with the given left Lehmer code. This is the inverse of
left_lehmer()
.- Parameters:
x (int) – a nonnegative integer
- Returns:
the
Permutation
with left Lehmer codex
- Raises:
ValueError – if
x
is less than 0
- classmethod from_lehmer(x: int, n: int) Permutation [source]
Calculate the permutation in \(S_n\) with Lehmer code
x
. This is the permutation at indexx
(zero-based) in the list of all permutations of degree at mostn
ordered lexicographically by word representation.This is the inverse of
lehmer
.- Parameters:
- Returns:
the
Permutation
with Lehmer codex
- Raises:
ValueError – if
x
is less than 0 or greater than or equal to the factorial ofn
- classmethod group(n: int) Iterator[Permutation] [source]
Generates all permutations in \(S_n\). This is the symmetric group of degree
n
, i.e., all permutations with degree less than or equal ton
. The permutations are yielded in ascending order of their left Lehmer codes.- Parameters:
n (int) – a nonnegative integer
- Returns:
a generator of all
Permutation
s with degreen
or less- Raises:
ValueError – if
n
is less than 0
- inverse() Permutation [source]
Returns the inverse of the permutation. This is the unique permutation that, when multiplied by the invocant on either the left or the right, produces the identity.
- Return type:
- inversions() int [source]
Calculate the inversion number of the permutation. This is the number of pairs of numbers which are in the opposite order after applying the permutation. This is also the Kendall tau distance from the identity permutation. This is also the sum of the terms in the Lehmer code when in factorial base.
Added in version 0.2.0.
- Returns:
the number of inversions in the permutation
- Return type:
- property is_even: bool
Whether the permutation is even. That is, whether it can be expressed as the product of an even number of transpositions (cycles of length 2).
- isdisjoint(other: Permutation) bool [source]
Tests whether the permutation is disjoint from
other
. This returnsTrue
iff the two permutations do not permute any of the same integers.- Parameters:
other (Permutation) – a permutation to compare against
- Return type:
- left_lehmer() int [source]
Calculate the “left Lehmer code” for the permutation. This uses a modified form of Lehmer codes that uses the left inversion count instead of the right inversion count. This modified encoding establishes a degree-independent bijection between permutations and nonnegative integers, with
from_left_lehmer()
converting values in the opposite direction.- Returns:
the permutation’s left Lehmer code
- Return type:
- lehmer(n: int) int [source]
Calculate a Lehmer code for the permutation. The Lehmer code is computed with respect to all permutations of degree at most
n
and evaluates to the zero-based index of the permutation in the list of all such permutations when ordered lexicographically by word representation.This is the inverse of
from_lehmer
.- Parameters:
n (int)
- Return type:
- Raises:
ValueError – if
n
is less thandegree
- next_permutation() Permutation [source]
Returns the next
Permutation
in left Lehmer code order
- property order: int
The order/period of the permutation. This is the smallest positive integer \(n\) such that multiplying \(n\) copies of the permutation together produces the identity
- classmethod parse(s: str) Permutation [source]
Parse a permutation written in cycle notation. This is the inverse of
__str__
.- Parameters:
s (str) – a permutation written in cycle notation
- Returns:
the permutation represented by
s
- Return type:
- Raises:
ValueError – if
s
is not valid cycle notation for a permutation
- permute(xs: Iterable[T]) list[T] [source]
Returns the elements of
xs
reordered according to the permutation. Each element at indexi
is moved to indexp(i)
.Note that
p.permute(range(1, n+1)) == p.inverse().to_image(n)
for all integersn
greater than or equal todegree
.Changed in version 0.5.0: This method now accepts iterables of any element type and returns a list. (Previously, it only accepted iterables of
int
s and returned a tuple.)- Parameters:
xs – a sequence of at least
degree
elements- Returns:
a permuted sequence
- Return type:
- Raises:
ValueError – if
len(xs)
is less thandegree
- prev_permutation() Permutation [source]
Returns the previous
Permutation
in left Lehmer code order- Raises:
ValueError – if called on the identity
Permutation
(which has no predecessor)
- right_inversion_count(n: int | None = None) list[int] [source]
Calculate the right inversion count through degree
n
. The result is a list ofn
elements in which the element at indexi
corresponds to the number of right inversions fori+1
, i.e., the number of valuesx > i+1
for whichp(x) < p(i+1)
.Setting
n
larger thandegree
causes the resulting list to have trailing zeroes, which become relevant when converting to & from Lehmer codes and factorial base.Added in version 0.2.0.
- property sign: int
The sign/signature of the permutation. This is 1 if the permutation is even, -1 if it is odd.
- to_cycles() list[tuple[int, ...]] [source]
Decompose the permutation into a product of disjoint cycles.
to_cycles()
returns a list of cycles, each one represented as a tuple of integers. Each cyclec
is a sub-permutation that mapsc[0]
toc[1]
,c[1]
toc[2]
, etc., finally mappingc[-1]
back around toc[0]
. The product of these cycles is then the original permutation.Each cycle is at least two elements in length and places its smallest element first. Cycles are ordered by their first elements in increasing order. No two cycles share an element.
When the permutation is the identity,
to_cycles()
returns an empty list.This is the inverse of
from_cycles
.- Returns:
the cycle decomposition of the permutation
- to_image(n: int | None = None) tuple[int, ...] [source]
Returns the images of 1 through
n
under the permutation. Ifv = p.to_image()
, thenv[0] == p(1)
,v[1] == p(2)
, etc.When the permutation is the identity,
to_image
called without an argument returns an empty tuple.This is the inverse of the constructor.