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
is written in pure Python with no dependencies. Just use pip (You have pip, right?) to install:
python3 m pip install permutation
Examples¶
>>> from permutation import Permutation
>>> p = Permutation(2, 1, 4, 5, 3)
>>> 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.The arguments to the constructor are the elements of the permutation’s word representation, i.e., the images of the integers 1 through some \(n\) under the permutation. 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).Permutation
s are hashable and immutable. They can be compared for equality but not for ordering/sorting.
__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

__mul__
(other: permutation.Permutation) → 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

__str__
() → str[source]¶ Convert a
Permutation
to cycle notation. The instance is decomposed into cycles withto_cycles()
, each cycle is written as a parenthesized spaceseparated 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.Permutation[source]¶ Construct a cyclic permutation from a sequence of unique positive integers. 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 unique 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
¶ The degree of the permutation, i.e., 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.Permutation[source]¶ Construct a
Permutation
from zero or more cyclic permutations. Each element ofcycles
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 unique 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.Permutation[source]¶ Returns 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.Permutation[source]¶ Calculate the permutation in \(S_n\) with Lehmer code
x
. This is the permutation at indexx
(zerobased) 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.Permutation][source]¶ Generates all permutations in \(S_n\), 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.Permutation[source]¶ Returns the inverse of the permutation, i.e., the unique permutation that, when multiplied by the invocant on either the left or the right, produces the identity
 Return type

inversions
() → int[source]¶ New in version 0.2.0.
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.
 Returns
the number of inversions in the permutation
 Return type

property
is_even
¶ Whether the permutation is even, i.e., can be expressed as the product of an even number of transpositions (cycles of length 2)

property
is_odd
¶ Whether the permutation is odd, i.e., not even

isdisjoint
(other: permutation.Permutation) → bool[source]¶ Returns
True
iff the permutation andother
are disjoint, i.e., iff they do not permute any of the same integers Parameters
other (Permutation) – a permutation to compare against
 Return type

left_lehmer
() → int[source]¶ Encode the permutation as a nonnegative integer using a modified form of Lehmer codes that uses the left inversion count instead of the right inversion count. This modified encoding establishes a degreeindependent 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 the Lehmer code of the permutation with respect to all permutations of degree at most
n
. This is the (zerobased) index of the permutation in the list of all permutations of degree at mostn
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.Permutation[source]¶ Returns the next
Permutation
in left Lehmer code order

property
order
¶ The order (a.k.a. period) of the permutation, i.e., the smallest positive integer \(n\) such that multiplying \(n\) copies of the permutation together produces the identity

classmethod
parse
(s: str) → permutation.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[int]) → Tuple[int, …][source]¶ Reorder the elements of a sequence according to the permutation; each element at index
i
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
. Parameters
xs – a sequence of at least
degree
elements Returns
a permuted sequence
 Return type
Tuple[int, ..]
 Raises
ValueError – if
len(xs)
is less thandegree

prev_permutation
() → 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: Optional[int] = None) → List[int][source]¶ New in version 0.2.0.
Calculate the right inversion count or right inversion vector of the permutation through degree
n
, or throughdegree
ifn
is unspecified. 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. Parameters
 Return type
List[int]
 Raises
ValueError – if
n
is less thandegree

property
sign
¶ The sign (a.k.a. signature) of the permutation: 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 in which each cycle is a tuple of integers. Each cyclec
is a subpermutation that mapsc[0]
toc[1]
,c[1]
toc[2]
, etc., finally mappingc[1]
back around toc[0]
. The permutation is then the product of these cycles.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: Optional[int] = None) → Tuple[int, …][source]¶ Returns a tuple of the results of applying the permutation to the integers 1 through
n
, or throughdegree
ifn
is unspecified. 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.
 Parameters
n (int) – the length of the image to return; defaults to
degree
 Returns
the image of 1 through
n
under the permutation Return type
Tuple[int, ..]
 Raises
ValueError – if
n
is less thandegree
