Permuta – A permutation library¶

Installing¶

Permuta is not yet available on pip.

Basic¶

It can however be cloned and set up on a unix system like so:

$ git clone https://github.com/PermutaTriangle/Permuta.git
$ cd Permuta
$ ./setup install  # Perhaps with superuser priveleges

Then it can be used in a script/interactive session like so:

import permuta

One should follow the demo on the official GitHub repository, and start off like so:

from permuta import *

Advanced¶

A more advanced user might install like so:

$ ./setup develop

But how advanced is that really?

The Permuta API¶

The permuta.demo package¶

A subpackage that serves as a gateway to Permuta.

Some of the main differences:

Perms are 1-based rather than 0-based
Some of the more advanced features provided by Python and used by Permuta are obscured at the expense of performance
PermClass class replaces PermSet in an attempt to provide a familiar name
Alias Permutation for Perm
Alias Av for PermClass

Contents:

Perm¶

class permuta.demo.Perm(*args) → None¶

Bases: permuta.interfaces.Displayable.Displayable

A perm class.

That is, a perm(utation) class (in the python sense).

Its constructor attempts to interpret anything you throw at it as a perm, but it’s probably easiest for a beginner to stick to numbers or lists of numbers: e.g., Perm(1324) or Perm(1, 3, 2, 4).

Examples

>>> Perm()  # Empty perm
()
>>> Perm([])  # Another empty perm
()
>>> Perm(132)  # From number
(1, 3, 2)
>>> Perm(248)  # Attempted interpretation
(1, 2, 3)
>>> Perm("1234")  # From string
(1, 2, 3, 4)
>>> Perm("dcab")  # This is equivalent to ...
(4, 3, 1, 2)
>>> Perm(["d", "c", "a", "b"])  # ... this
(4, 3, 1, 2)
>>> Perm(0, 0, 2, 1)  # Index is tie-breaker
(1, 2, 4, 3)
>>> Perm("Ragnar", "Christian", "Henning")
(3, 1, 2)
>>> Perm.monotone_increasing(4)
(1, 2, 3, 4)
>>> Perm.monotone_decreasing(3)
(3, 2, 1)
>>> random_perm = Perm.random(7)

PermClass¶

class permuta.demo.PermClass(basis=())¶

Bases: object

A perm(utation) class object.

Pass the constructor an iterable of Perms or objects that can be interpreted as such; each non-Perm element is passed to the Perm constructor. If the constructor is passed a single int or Perm, the principal class for that Perm is constructed.

Examples

>>> PermClass()
<All perms>
>>> PermClass(123)
<Perms avoiding: (1, 2, 3)>
>>> PermClass(["1423", "1234"])
<Perms avoiding: (1, 2, 3, 4) and (1, 4, 2, 3)>
>>> PermClass([123, "321", Perm(3, 1, 2)])
<Perms avoiding: (1, 2, 3), (3, 1, 2), and (3, 2, 1)>
>>> PermClass([62, 123])
<Perms avoiding: (2, 1) and (1, 2, 3)>

of_length(length: int) → permuta.demo._PermClass._PermClassOfLength¶: Return the subset of perms of a certain length.

The permuta package¶

Contents:

Perm¶

TODO: Here we really want text that tells something about the Perm class ... maybe the class docstring will suffice

class permuta.Perm(iterable=())¶

Bases: tuple, permuta.interfaces.Patt.Patt, permuta.interfaces.Rotatable.Rotatable, permuta.interfaces.Shiftable.Shiftable, permuta.interfaces.Flippable.Flippable

A perm class.

__add__(other)¶: Return the direct sum of the perms self and other.

__call__(value)¶

Map value to its image defined by the perm.

Examples

>>> Perm((3, 1, 2, 0))(0)
3
>>> Perm((3, 1, 2, 0))(1)
1
>>> Perm((3, 1, 2, 0))(2)
2
>>> Perm((3, 1, 2, 0))(3)
0

__contains__(patt)¶

Check if self contains patt.

Parameters:	self – A perm. patt – <permuta.Patt> A classical/mesh pattern.

Returns: <bool>: True if and only if the pattern patt is contained in self.

__mul__(other)¶: Return the composition of two perms.

static __new__(iterable=())¶

Return a Perm instance.

Parameters:	cls – The class of which an instance is requested. iterable – An iterable corresponding to a legal perm. Also supports passing just a number with unique digits.
Raises:	`TypeError` – Bad argument type. `ValueError` – Bad argument, but correct type.

Examples

>>> Perm((0, 3, 1, 2))
Perm((0, 3, 1, 2))
>>> Perm(range(5, -1, -1))
Perm((5, 4, 3, 2, 1, 0))
>>> Perm(6012354)
Perm((6, 0, 1, 2, 3, 5, 4))
>>> Perm.toggle_check()
>>> Perm("abc")  # Not good
Traceback (most recent call last):
    ...
TypeError: 'a' object is not an integer

__sub__(other)¶: Return the skew sum of the perms self and other.

all_intervals(return_patterns=False)¶

Returns the list of all blocks(intervals) in the permutation that are of length at least 2. The returned list of lists contains the indices of blocks of length i in index i.

When return_patterns is set to True, a list of patterns is returned instead of list of list of indices.

Examples

>>> Perm((5, 3, 0, 1, 2, 4, 7, 6)).block_decomposition()
[[], [], [2, 3, 6], [2], [1], [1], [0], []]
>>> Perm((4, 1, 0, 5, 2, 3)).block_decomposition(True)
[Perm((0, 1)), Perm((1, 0))]

all_monotone_intervals(with_ones=False)¶

Returns the list of all monotone blocks(intervals) in the permutation. Depending on the with_ones parameter it will return the length 1 blocks. The blocks are pairs of indices, the start and end index.

Examples

>>> Perm((2, 6, 3, 7, 4, 5, 1, 0)).monotone_block_decomposition()
[(4, 5), (6, 7)]
>>> Perm((2, 6, 3, 7, 4, 5, 1, 0)).monotone_block_decomposition(True)
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 5), (6, 7)]
>>> Perm((0, 1, 2, 3, 4, 5)).monotone_block_decomposition()
[(0, 5)]

all_syms()¶: Returns all symmetries of the permutation in a PermSet, all possible combinations of revers, complement and inverse.

apply(iterable: list)¶

Permute an iterable using the perm.

Parameters:	self – A perm. iterable – An iterable of len(self) elements.
Returns:
Return type:	A tuple of the elements of the iterable in the permuted order.
Raises:	`TypeError` – Bad argument type.

Examples

>>> Perm((4, 1, 2, 0, 3)).apply((1, 2, 3, 4, 5))
(5, 2, 3, 1, 4)
>>> Perm((4, 1, 2, 0, 3)).apply("abcde")
('e', 'b', 'c', 'a', 'd')
>>> Perm((1, 2, 0, 3)).apply("abcde")
Traceback (most recent call last):
    ...
ValueError: Length mismatch

ascent_set()¶

Return the list of ascents of self.

This method is for backwards compatibility with permpy.

ascents()¶

Yield the 0-based ascent of self.

Examples

>>> tuple(Perm((0, 1, 3, 2, 4)).ascents())
(0, 1, 3)
>>> tuple(Perm((0, 4, 3, 2, 1)).ascents())
(0,)
>>> tuple(Perm((3, 2, 1, 0)).ascents())
()

avoids(*patts)¶

Check if self avoids patts.

Parameters:	self – A perm. patts – <permuta.Patt> argument list Classical/mesh patterns.

Returns: <bool>: True if and only if self avoids all patterns in patts.

Examples

>>> Perm.monotone_increasing(8).avoids(Perm((1, 0)))
True
>>> Perm((4, 2, 3, 1, 0)).avoids(Perm((1, 2, 0)))
False
>>> Perm((0, 1, 2)).avoids(Perm((1,0)))
True
>>> pattern1 = Perm((0, 1))
>>> pattern2 = Perm((2, 0, 1))
>>> pattern3 = Perm((0, 3, 1, 2))
>>> pattern4 = Perm((0, 1, 2))
>>> Perm((5, 3, 0, 4, 2, 1)).avoids(pattern1, pattern2)
False
>>> Perm((5, 3, 0, 4, 2, 1)).avoids(pattern2, pattern3)
False
>>> Perm((5, 3, 0, 4, 2, 1)).avoids(pattern3, pattern4)
True

avoids_set(patts)¶

Check if self avoids patts.

This method is for backwards compatibility with permpy.

bend_list()¶

Returns the list of indices at which the permutation changes direction. That is, the number of non-monotone consecutive triples of the permutation. A permutation p can be expressed as the concatenation of len(p.bend_list()) + 1 monotone segments.

Examples

>>> Perm((5, 3, 4, 0, 2, 1)).bend_list()
[1, 2, 3, 4]
>>> Perm((2, 0, 1)).bend_list()
[1]

bends()¶

Yield the indices at which the permutation changes direction. That is, the number of non-monotone consecutive triples of the permutation. A permutation p can be expressed as the concatenation of len(p.bends()) + 1 monotone segments.

Examples

>>> list(Perm((5, 3, 4, 0, 2, 1)).bends())
[1, 2, 3, 4]
>>> list(Perm((2, 0, 1)).bends())
[1]

block_decomposition(return_patterns=False)¶

Returns the list of all blocks(intervals) in the permutation that are of length at least 2. The returned list of lists contains the indices of blocks of length i in index i.

When return_patterns is set to True, a list of patterns is returned instead of list of list of indices.

Examples

>>> Perm((5, 3, 0, 1, 2, 4, 7, 6)).block_decomposition()
[[], [], [2, 3, 6], [2], [1], [1], [0], []]
>>> Perm((4, 1, 0, 5, 2, 3)).block_decomposition(True)
[Perm((0, 1)), Perm((1, 0))]

bonds()¶

Counts the number of bonds, that is the number of adjacent locations with adjacent values.

Examples

>>> Perm((0, 1, 2)).count_bonds()
2
>>> Perm((2, 1, 0)).count_bonds()
2
>>> Perm((4, 0, 3, 2, 1, 5)).count_bonds()
2

buildupset(height)¶: Returns height-th layer of the upset of the permutation

children()¶

Returns all patterns of length one less than the permutation. One layer of the downset, also called the shadow.

Example

>>> Perm((2, 0, 1)).children()
[Perm((0, 1)), Perm((1, 0))]
>>> Perm((4, 1, 6, 3, 0, 7, 2, 5)).children()
[Perm((3, 1, 5, 2, 0, 6, 4)), Perm((3, 0, 5, 2, 6, 1, 4)), Perm((4, 1, 6, 3, 0, 2, 5)), Perm((3, 5, 2, 0, 6, 1, 4)), Perm((4, 1, 3, 0, 6, 2, 5)), Perm((1, 5, 3, 0, 6, 2, 4)), Perm((3, 1, 5, 0, 6, 2, 4)), Perm((4, 1, 5, 3, 0, 6, 2))]

complement()¶

Return the complement of the perm self.

Examples

>>> Perm((1, 2, 3, 0, 4)).complement()
Perm((3, 2, 1, 4, 0))
>>> Perm((2, 0, 1)).complement()
Perm((0, 2, 1))

compose(*others)¶

Return the composition of two or more perms.

Parameters:	self – A perm. others – <permuta.Perm> argument list Perms.

Returns: <permuta.Perm>: The consecutive pointwise application of all the above perms in reverse order.

Raises:	`TypeError` – An object in the argument list is not a perm. `ValueError` – A perm in the argument list is of the wrong length.

Examples

>>> Perm((0, 3, 1, 2)).compose(Perm((2, 1, 0, 3)))
Perm((1, 3, 0, 2))
>>> Perm((1, 0, 2)).compose(Perm((0, 1, 2)), Perm((2, 1, 0)))
Perm((2, 0, 1))

contains(*patts)¶

Check if self contains patts.

Parameters:	self – A perm. patts – <permuta.Patt> argument list Classical/mesh patterns.

Returns: <bool>: True if and only if all patterns in patt are contained in self.

Examples

>>> Perm.monotone_decreasing(7).avoids(Perm((0, 1)))
True
>>> Perm((4, 2, 3, 1, 0)).contains(Perm((1, 2, 0)))
True
>>> Perm((0, 1, 2)).contains(Perm((1,0)))
False
>>> pattern1 = Perm((0, 1))
>>> pattern2 = Perm((2, 0, 1))
>>> pattern3 = Perm((0, 3, 1, 2))
>>> Perm((5, 3, 0, 4, 2, 1)).contains(pattern1, pattern2)
True
>>> Perm((5, 3, 0, 4, 2, 1)).contains(pattern2, pattern3)
False

contract_bonds()¶

contract_dec_bonds()¶

contract_inc_bonds()¶

count_ascents()¶

Count the number of ascents in self.

Examples

>>> Perm((0, 1, 3, 2, 4)).count_ascents()
3
>>> Perm((0, 4, 3, 2, 1)).count_ascents()
1
>>> Perm((3, 2, 1, 0)).count_ascents()
0

count_bonds()¶

Counts the number of bonds, that is the number of adjacent locations with adjacent values.

Examples

>>> Perm((0, 1, 2)).count_bonds()
2
>>> Perm((2, 1, 0)).count_bonds()
2
>>> Perm((4, 0, 3, 2, 1, 5)).count_bonds()
2

count_cycles()¶

Returns the number of cycles in the permutation.

>>> Perm((5, 3, 8, 1, 0, 4, 2, 7, 6)).count_cycles()
4

count_dec_bonds()¶

Counts the number of decreasing bonds.

Examples

>>> Perm((2, 1, 0, 3)).count_dec_bonds()
2
>>> Perm((1, 0, 3, 2, 5, 4)).count_dec_bonds()
3

count_descents()¶

Count the number of descents of self. .. rubric:: Examples

>>> Perm((0, 1, 3, 2, 4)).count_descents()
1
>>> Perm((3, 2, 1, 0)).count_descents()
3
>>> Perm((0, 1, 2)).count_descents()
0

count_fixed_points()¶

Return the number of fixed points in self.

Examples

>>> Perm((0, 1, 4, 3, 2)).count_fixed_points()
3
>>> Perm((0, 1, 2, 3, 4)).count_fixed_points()
5
>>> Perm((3, 2, 1, 0)).count_fixed_points()
0

count_inc_bonds()¶

Counts the number of increasing bonds.

Examples

>>> Perm((0, 2, 3, 1)).count_inc_bonds()
1
>>> Perm((2, 3, 4, 5, 0, 1)).count_inc_bonds()
4

count_inversions()¶

Returns the number of inversions of the permutation, i.e., the number of pairs i,j such that i < j and self(i) > self(j).

TODO: Reimplement in NlogN time.

>>> Perm(3021).count_inversions()
4
>>> Perm.monotone_decreasing(6).count_inversions() == 5*6 / 2
True
>>> Perm.monotone_increasing(7).count_inversions()
0

count_ltrmin()¶

Counts the number of left-to-right minimas.

Example

>>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
2

count_noninversions()¶

Returns the number of noninversions of the permutation, i.e., the number of pairs i,j such that i < j and self[i] < self[j].

Examples

>>> Perm((3, 0, 2, 1, 4)).count_noninversions()
6
>>> Perm.monotone_increasing(7).count_noninversions() == (6 * 7) / 2
True

count_occurrences_of(patt)¶

Count the number of occurrences of patt in self.

Parameters:	self – A perm. patt – <permuta.Patt> A classical/mesh pattern.

Returns: <int>: The number of times patt occurs in self.

Examples

>>> Perm((0, 1, 2)).count_occurrences_of(Perm((0, 1)))
3
>>> Perm((5, 3, 0, 4, 2, 1)).count_occurrences_of(Perm((2, 0, 1)))
6

count_peaks()¶

Count the number of peaks of self.

Examples

>>> Perm((5, 3, 4, 0, 2, 1)).count_peaks()
2
>>> Perm((1, 2, 0)).count_peaks()
1
>>> Perm((2, 1, 0)).count_peaks()
0

count_rtlmax_ltrmin_layers()¶: Counts the layers in the right-to-left maxima, left-to-right minima decomposition.

count_valleys()¶

Count the number of valleys of self.

Examples

>>> Perm((5, 3, 4, 0, 2, 1)).count_valleys()
2
>>> Perm((2, 0, 1)).count_valleys()
1
>>> Perm((1, 2, 0)).count_valleys()
0

coveredby()¶

Returns one layer of the upset of the permutation.

Examples

>>> Perm((0, 1)).coveredby()
[Perm((0, 2, 1)), Perm((1, 2, 0)), Perm((0, 1, 2)), Perm((2, 0, 1)), Perm((1, 0, 2))]

cycle_decomp()¶

Calculates the cycle decomposition of the permutation. Returns a list of cycles, each of which is represented as a list.

>>> Perm((4, 2, 7, 0, 3, 1, 6, 5)).cycle_decomp()
[[4, 3, 0], [6], [7, 5, 1, 2]]

cycle_notation()¶

Returns the cycle notation representation of the permutation.

Examples

>>> Perm((5, 3, 0, 1, 2, 4)).cycle_notation()
'( 3 1 ) ( 5 4 2 0 )'

cycles()¶

Returns the cycle notation representation of the permutation.

Examples

>>> Perm((5, 3, 0, 1, 2, 4)).cycle_notation()
'( 3 1 ) ( 5 4 2 0 )'

cyclic_shift(times=1)¶

Return self shifted times steps to the right.

If shift is negative, shifted to the left.

Examples

>>> Perm((0, 1, 2)).shift_right()
Perm((2, 0, 1))
>>> Perm((0, 1, 2)).shift_right(-4)
Perm((1, 2, 0))

cyclic_shift_left(times=1)¶

Return self shifted times steps to the left.

If shift is negative, shifted to the right.

Examples

>>> Perm((0, 1, 2)).shift_left()
Perm((1, 2, 0))
>>> Perm((0, 1, 2)).shift_left(-4)
Perm((2, 0, 1))

cyclic_shift_right(times=1)¶

Return self shifted times steps to the right.

If shift is negative, shifted to the left.

Examples

>>> Perm((0, 1, 2)).shift_right()
Perm((2, 0, 1))
>>> Perm((0, 1, 2)).shift_right(-4)
Perm((1, 2, 0))

dec_bonds()¶

Yields the indices of the decreasing bonds, that is the indices of the descents with adjacent values.

Examples

>>> list(Perm((1, 0, 3, 2, 5, 4)).dec_bonds())
[0, 2, 4]

decomposition(return_patterns=False)¶

Returns the list of all blocks(intervals) in the permutation that are of length at least 2. The returned list of lists contains the indices of blocks of length i in index i.

When return_patterns is set to True, a list of patterns is returned instead of list of list of indices.

Examples

>>> Perm((5, 3, 0, 1, 2, 4, 7, 6)).block_decomposition()
[[], [], [2, 3, 6], [2], [1], [1], [0], []]
>>> Perm((4, 1, 0, 5, 2, 3)).block_decomposition(True)
[Perm((0, 1)), Perm((1, 0))]

descent_set()¶

Return the list of descents of self.

This method is for backwards compatibility with permpy.

descents()¶

Yield the 0-based descents of self.

Examples

>>> tuple(Perm((0, 1, 3, 2, 4)).descents())
(2,)
>>> tuple(Perm((3, 2, 1, 0)).descents())
(0, 1, 2)
>>> tuple(Perm((0, 1, 2)).descents())
()

direct_sum(*others)¶

Return the direct sum of two or more perms.

Parameters:	self – A perm. others – <permuta.Perm> argument list Perms.

Returns: <permuta.Perm>: The direct sum of all the perms.

Examples

>>> Perm((0,)).direct_sum(Perm((1, 0)))
Perm((0, 2, 1))
>>> Perm((0,)).direct_sum(Perm((1, 0)), Perm((2, 1, 0)))
Perm((0, 2, 1, 5, 4, 3))

fixed_points()¶

Return the number of fixed points in self.

Examples

>>> Perm((0, 1, 4, 3, 2)).count_fixed_points()
3
>>> Perm((0, 1, 2, 3, 4)).count_fixed_points()
5
>>> Perm((3, 2, 1, 0)).count_fixed_points()
0

flip_antidiagonal()¶

Return self flipped along the antidiagonal..

Examples

>>> Perm((3, 2, 0, 1)).flip_antidiagonal()
Perm((3, 2, 0, 1))
>>> Perm((1, 2, 3, 0, 4)).flip_antidiagonal()
Perm((0, 2, 3, 4, 1))
>>> Perm((1, 2, 0, 3)).flip_antidiagonal()
Perm((0, 2, 3, 1))

flip_diagonal()¶

Return self flipped along the diagonal.

Examples

>>> Perm((1, 2, 5, 0, 3, 4)).flip_diagonal()
Perm((3, 0, 1, 4, 5, 2))
>>> Perm((0, 1)).flip_diagonal()
Perm((0, 1))

flip_horizontal()¶

Return self flipped horizontally.

Examples

>>> Perm((1, 2, 3, 0, 4)).flip_horizontal()
Perm((3, 2, 1, 4, 0))
>>> Perm((2, 0, 1)).flip_horizontal()
Perm((0, 2, 1))

flip_vertical()¶

Return self flipped vertically.

Examples

>>> Perm((1, 2, 5, 0, 3, 4)).flip_vertical()
Perm((4, 3, 0, 5, 2, 1))
>>> Perm((0, 1)).flip_vertical()
Perm((1, 0))

fourpats()¶

Returns a dictionary of the number of occurrences of each permutation pattern of length 4.

Examples

>>> Perm((1, 0, 3, 5, 2, 4)).fourpats()
{Perm((0, 1, 2, 3)): 0, Perm((0, 1, 3, 2)): 2, Perm((0, 2, 1, 3)): 2, Perm((0, 2, 3, 1)): 2, Perm((0, 3, 1, 2)): 2, Perm((0, 3, 2, 1)): 0, Perm((1, 0, 2, 3)): 3, Perm((1, 0, 3, 2)): 3, Perm((1, 2, 0, 3)): 0, Perm((1, 2, 3, 0)): 0, Perm((1, 3, 0, 2)): 1, Perm((1, 3, 2, 0)): 0, Perm((2, 0, 1, 3)): 0, Perm((2, 0, 3, 1)): 0, Perm((2, 1, 0, 3)): 0, Perm((2, 1, 3, 0)): 0, Perm((2, 3, 0, 1)): 0, Perm((2, 3, 1, 0)): 0, Perm((3, 0, 1, 2)): 0, Perm((3, 0, 2, 1)): 0, Perm((3, 1, 0, 2)): 0, Perm((3, 1, 2, 0)): 0, Perm((3, 2, 0, 1)): 0, Perm((3, 2, 1, 0)): 0}

classmethod from_iterable(iterable)¶

Return the perm corresponding to iterable.

Duplicate elements are allowed and become consecutive elements (see example).

The standardize alias is supplied for backwards compatibility with permpy. However, the permpy version did not allow for duplicate elements.

Examples

>>> Perm.to_standard("a2gsv3")
Perm((2, 0, 3, 4, 5, 1))
>>> Perm.to_standard("caaba")
Perm((4, 0, 1, 3, 2))

classmethod from_string(string)¶

Return the perm corresponding to the string given.

Examples

>>> Perm.from_string("203451")
Perm((2, 0, 3, 4, 5, 1))
>>> Perm.from_string("40132")
Perm((4, 0, 1, 3, 2))

classmethod identity(length)¶

Return the identity perm of the specified length.

Examples

>>> Perm.identity(0)
Perm(())
>>> Perm.identity(4)
Perm((0, 1, 2, 3))

inc_bonds()¶

Yields the indices of the increasing bonds, that is the indices of the ascents with adjacent values.

Examples

>>> list(Perm((2, 3, 4, 5, 0, 1)).inc_bonds())
[0, 1, 2, 4]

classmethod ind2perm(number, length=None)¶

Examples

>>> Perm.unrank(0)
Perm(())
>>> Perm.unrank(1)
Perm((0,))
>>> Perm.unrank(2)
Perm((0, 1))
>>> Perm.unrank(3)
Perm((1, 0))
>>> Perm.unrank(4)
Perm((0, 1, 2))
>>> Perm.unrank(5)
Perm((0, 2, 1))
>>> Perm.unrank(1, 3)
Perm((0, 2, 1))

inflate(components)¶

Inflate elements of the permutation to create a new one.

Parameters:	component – <collections.Iterable> of <permuta.Perm> This can also be a dict with keys and perms...

Returns: <permuta.Perm>

Examples

>>> Perm((0, 1)).inflate([Perm((1, 0)), Perm((2, 1, 0))])
Perm((1, 0, 4, 3, 2))
>>> Perm((1, 0, 2)).inflate([None, Perm((0, 1)), Perm((0, 1))])
Perm((2, 0, 1, 3, 4))
>>> Perm((0, 2, 1)).inflate({2: Perm((0, 1, 2))})
Perm((1, 0, 4, 3, 2))
>>> # Can also deflate points
>>> Perm((0, 1)).inflate([Perm(), Perm()])
Perm(())

insert(index=None, new_element=None)¶

Return the perm acquired by adding a new element.

Parameters:	index – <int> Where in the perm the value is to occur. If None, the value defaults to len(self)+1. new_element – <int> An integer in the range of 0 to len(self) inclusive. If None, the element defaults to len(self).

Returns: <permuta.Perm>: The perm with the added element (and other elements adjusted as needed).

Raises:	`IndexError` – Index is not valid. `ValueError` – Element passed cannot legally be added to perm. `TypeError` – Element passed is not an integer.

Examples

>>> Perm((0, 1)).insert()
Perm((0, 1, 2))
>>> Perm((0, 1)).insert(0)
Perm((2, 0, 1))
>>> Perm((2, 0, 1)).insert(2, 1)
Perm((3, 0, 1, 2))

inverse()¶

Return the inverse of the perm self.

Examples

>>> Perm((1, 2, 5, 0, 3, 4)).inverse()
Perm((3, 0, 1, 4, 5, 2))
>>> Perm((2, 0, 1)).inverse().inverse() == Perm((2, 0, 1))
True
>>> Perm((0, 1)).inverse()
Perm((0, 1))

inversions()¶

Returns the number of inversions of the permutation, i.e., the number of pairs i,j such that i < j and self(i) > self(j).

TODO: Reimplement in NlogN time.

>>> Perm(3021).count_inversions()
4
>>> Perm.monotone_decreasing(6).count_inversions() == 5*6 / 2
True
>>> Perm.monotone_increasing(7).count_inversions()
0

is_decreasing()¶: Return True if the perm is decreasing, and False otherwise.

is_identity()¶

Checks if the permutation is the identity.

>>> p = Perm.random(10)
>>> (p * p.inverse()).is_identity()
True

is_increasing()¶: Return True if the perm is increasing, and False otherwise.

is_involution()¶

Checks if the permutation is an involution, i.e., is equal to it’s own inverse.

Examples

>>> Perm((2, 1, 0)).is_involution()
True
>>> Perm((3, 0, 2, 4, 1, 5)).is_involution()
False

is_representative()¶: Checks if the permutation is representative, that is, all the symmetries of the permutation are the same.

is_simple()¶

Checks if the permutation is simple.

Example

>>> Perm((2, 0, 3, 1)).is_simple()
True
>>> Perm((2, 0, 1)).is_simple()
False

is_skew_decomposable()¶

Determines whether the permutation is expressible as the skew sum of two permutations.

>>> p = Perm.random(8).direct_sum(Perm.random(12))
>>> p.skew_decomposable()
False
>>> p.complement().skew_decomposable()
True

is_strongly_simple()¶

Checks if the permutation is strongly simple, that is if the permutation is simple and any of permutation of one less length in the downset is simple.

Example

>>> Perm((4, 1, 6, 3, 0, 7, 2, 5)).is_strongly_simple()
True

is_sum_decomposable()¶

Determines whether the permutation is expressible as the direct sum of two permutations.

>>> p = Perm.random(4).direct_sum(Perm.random(15))
>>> p.sum_decomposable()
True
>>> p.reverse().sum_decomposable()
False

length_of_longestrun()¶: Returns the length of the longest ascending run in the permutation.

length_of_longestrun_ascending()¶: Returns the length of the longest ascending run in the permutation.

length_of_longestrun_descending()¶: Returns the length of the longest descending run in the permutation.

longestruns()¶: Returns the longest ascending runs in the permutation as a pair of the length and a list of the starting indices.

longestruns_ascending()¶: Returns the longest ascending runs in the permutation as a pair of the length and a list of the starting indices.

longestruns_descending()¶: Returns the longest descending runs in the permutation as a pair of the length and a list of the starting indices.

ltrmax()¶

Returns the positions of the left-to-right maxima.

Examples

>>> Perm(204153).ltrmax()
[0, 2, 4]

ltrmin()¶

Returns the positions of the left-to-right minima.

Examples

>>> Perm(24301).ltrmin()
[0, 3]

majorindex()¶

Returns the major index of the permutation, that is the sum of the positions of the descents of the permutation.

Examples

>>> Perm((3, 1, 2, 4, 0)).majorindex()
5
>>> Perm((0, 2, 1)).majorindex()
2

maximal_interval()¶

Finds the biggest interval, and returns (i,j) is one is found, where i is the size of the interval, and j is the index of the first entry in the interval.

Returns (0,0) if no interval is found, i.e., if the permutation is simple.

Example

>>> Perm((0, 2, 1, 5, 6, 7, 4, 3)).maximum_block()
(7, 1)

maximum_block()¶

Finds the biggest interval, and returns (i,j) is one is found, where i is the size of the interval, and j is the index of the first entry in the interval.

Returns (0,0) if no interval is found, i.e., if the permutation is simple.

Example

>>> Perm((0, 2, 1, 5, 6, 7, 4, 3)).maximum_block()
(7, 1)

min_gapsize()¶

Returns the minimum gap between any two entries in the permutation (computed with the taxicab metric).

TODO: currently uses the naive algorithm — can be improved

Examples

>>> Perm(2031).min_gapsize()
3

monotone_block_decomposition(with_ones=False)¶

Returns the list of all monotone blocks(intervals) in the permutation. Depending on the with_ones parameter it will return the length 1 blocks. The blocks are pairs of indices, the start and end index.

Examples

>>> Perm((2, 6, 3, 7, 4, 5, 1, 0)).monotone_block_decomposition()
[(4, 5), (6, 7)]
>>> Perm((2, 6, 3, 7, 4, 5, 1, 0)).monotone_block_decomposition(True)
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 5), (6, 7)]
>>> Perm((0, 1, 2, 3, 4, 5)).monotone_block_decomposition()
[(0, 5)]

monotone_block_decompositon_ascending(with_ones=False)¶

monotone_block_decompositon_descending(with_ones=False)¶

classmethod monotone_decreasing(length)¶

Return a monotone decreasing perm of the specified length.

Examples

>>> Perm.monotone_decreasing(0)
Perm(())
>>> Perm.monotone_decreasing(4)
Perm((3, 2, 1, 0))

classmethod monotone_increasing(length)¶

Return a monotone increasing perm of the specified length.

Examples

>>> Perm.monotone_increasing(0)
Perm(())
>>> Perm.monotone_increasing(4)
Perm((0, 1, 2, 3))

monotone_quotient()¶

Return the permutation pattern consisting of the starting values of the monotone blocks in the permutation. Simply contracts the monotone blocks.

Examples

>>> Perm((0, 2, 1, 5, 6, 7, 4, 3)).monotone_block_decomposition(True)
[(0, 0), (1, 2), (3, 5), (6, 7)]
>>> Perm((0, 2, 1, 5, 6, 7, 4, 3)).monotone_quotient()
Perm((0, 1, 3, 2))

multiply(*others)¶

Return the composition of two or more perms.

Parameters:	self – A perm. others – <permuta.Perm> argument list Perms.

Returns: <permuta.Perm>: The consecutive pointwise application of all the above perms in reverse order.

Raises:	`TypeError` – An object in the argument list is not a perm. `ValueError` – A perm in the argument list is of the wrong length.

Examples

>>> Perm((0, 3, 1, 2)).compose(Perm((2, 1, 0, 3)))
Perm((1, 3, 0, 2))
>>> Perm((1, 0, 2)).compose(Perm((0, 1, 2)), Perm((2, 1, 0)))
Perm((2, 0, 1))

num_ascents()¶

Count the number of ascents in self.

Examples

>>> Perm((0, 1, 3, 2, 4)).count_ascents()
3
>>> Perm((0, 4, 3, 2, 1)).count_ascents()
1
>>> Perm((3, 2, 1, 0)).count_ascents()
0

num_bonds()¶

Counts the number of bonds, that is the number of adjacent locations with adjacent values.

Examples

>>> Perm((0, 1, 2)).count_bonds()
2
>>> Perm((2, 1, 0)).count_bonds()
2
>>> Perm((4, 0, 3, 2, 1, 5)).count_bonds()
2

num_cycles()¶

Returns the number of cycles in the permutation.

>>> Perm((5, 3, 8, 1, 0, 4, 2, 7, 6)).count_cycles()
4

num_dec_bonds()¶

Counts the number of decreasing bonds.

Examples

>>> Perm((2, 1, 0, 3)).count_dec_bonds()
2
>>> Perm((1, 0, 3, 2, 5, 4)).count_dec_bonds()
3

num_descents()¶

Count the number of descents of self. .. rubric:: Examples

>>> Perm((0, 1, 3, 2, 4)).count_descents()
1
>>> Perm((3, 2, 1, 0)).count_descents()
3
>>> Perm((0, 1, 2)).count_descents()
0

num_inc_bonds()¶

Counts the number of increasing bonds.

Examples

>>> Perm((0, 2, 3, 1)).count_inc_bonds()
1
>>> Perm((2, 3, 4, 5, 0, 1)).count_inc_bonds()
4

num_ltrmin()¶

Counts the number of left-to-right minimas.

Example

>>> Perm((2, 4, 3, 0, 1)).count_ltrmin()
2

num_peaks()¶

Count the number of peaks of self.

Examples

>>> Perm((5, 3, 4, 0, 2, 1)).count_peaks()
2
>>> Perm((1, 2, 0)).count_peaks()
1
>>> Perm((2, 1, 0)).count_peaks()
0

num_rtlmax_ltrmin_layers()¶: Counts the layers in the right-to-left maxima, left-to-right minima decomposition.

num_valleys()¶

Count the number of valleys of self.

Examples

>>> Perm((5, 3, 4, 0, 2, 1)).count_valleys()
2
>>> Perm((2, 0, 1)).count_valleys()
1
>>> Perm((1, 2, 0)).count_valleys()
0

occurrences(patt)¶

Count the number of occurrences of patt in self.

Parameters:	self – A perm. patt – <permuta.Patt> A classical/mesh pattern.

Returns: <int>: The number of times patt occurs in self.

Examples

>>> Perm((0, 1, 2)).count_occurrences_of(Perm((0, 1)))
3
>>> Perm((5, 3, 0, 4, 2, 1)).count_occurrences_of(Perm((2, 0, 1)))
6

occurrences_in(perm)¶

Find all indices of occurrences of self in perm.

Parameters:	self – The classical pattern whose occurrences are to be found. perm – <permuta.Perm> The perm to search for occurrences in.

Yields: <tuple> of <int>: The indices of the occurrences of self in perm. Each yielded element l is a tuple of integer indices of the perm perm such that: self == permuta.Perm.to_standard([perm[i] for i in l])

Examples

>>> list(Perm((2, 0, 1)).occurrences_in(Perm((5, 3, 0, 4, 2, 1))))
[(0, 1, 3), (0, 2, 3), (0, 2, 4), (0, 2, 5), (1, 2, 4), (1, 2, 5)]
>>> list(Perm((1, 0)).occurrences_in(Perm((1, 2, 3, 0))))
[(0, 3), (1, 3), (2, 3)]
>>> list(Perm((0,)).occurrences_in(Perm((1, 2, 3, 0))))
[(0,), (1,), (2,), (3,)]
>>> list(Perm().occurrences_in(Perm((1, 2, 3, 0))))
[()]

occurrences_of(patt)¶

Find all indices of occurrences of patt in self.

This method is complementary to permuta.Perm.occurrences_in. It just calls patt.occurrences_in(self) internally. See permuta.Perm.occurrences_in for documentation.

Parameters:	self – A perm. patt – <permuta.Patt> A classical/mesh pattern.

Yields: <tuple> of <int>: The indices of the occurrences of self in perm.

Examples

>>> list(Perm((5, 3, 0, 4, 2, 1)).occurrences_of(Perm((2, 0, 1))))
[(0, 1, 3), (0, 2, 3), (0, 2, 4), (0, 2, 5), (1, 2, 4), (1, 2, 5)]
>>> list(Perm((1, 2, 3, 0)).occurrences_of(Perm((1, 0))))
[(0, 3), (1, 3), (2, 3)]
>>> list(Perm((1, 2, 3, 0)).occurrences_of(Perm((0,))))
[(0,), (1,), (2,), (3,)]
>>> list(Perm((1, 2, 3, 0)).occurrences_of(Perm()))
[()]

classmethod one(iterable)¶

A way to enter a perm in the traditional permuta way.

Examples

>>> Perm.one_based((4, 1, 3, 2))
Perm((3, 0, 2, 1))

classmethod one_based(iterable)¶

A way to enter a perm in the traditional permuta way.

Examples

>>> Perm.one_based((4, 1, 3, 2))
Perm((3, 0, 2, 1))

order()¶

Returns the order of the permutation.

Examples

>>> Perm((4, 3, 5, 0, 2, 1)).order()
6
>>> Perm((0, 1, 2)).order()
1

peak_list()¶

Return the list of peaks of self.

This method is for backwards compatibility with permpy.

peaks()¶

Yield the indices of the peaks of self.

The i-th element of a perm is a peak if: self[i-1] < self[i] > self[i+1].

Examples

>>> tuple(Perm((5, 3, 4, 0, 2, 1)).peaks())
(2, 4)
>>> tuple(Perm((1, 2, 0)).peaks())
(1,)
>>> tuple(Perm((2, 1, 0)).peaks())
()

permute(iterable: list)¶

Permute an iterable using the perm.

Parameters:	self – A perm. iterable – An iterable of len(self) elements.
Returns:
Return type:	A tuple of the elements of the iterable in the permuted order.
Raises:	`TypeError` – Bad argument type.

Examples

>>> Perm((4, 1, 2, 0, 3)).apply((1, 2, 3, 4, 5))
(5, 2, 3, 1, 4)
>>> Perm((4, 1, 2, 0, 3)).apply("abcde")
('e', 'b', 'c', 'a', 'd')
>>> Perm((1, 2, 0, 3)).apply("abcde")
Traceback (most recent call last):
    ...
ValueError: Length mismatch

plot(show=True, ax=None, use_mpl=True, fname=None, **kwargs)¶: Draws a matplotlib plot of the permutation. Can be used for both quick visualization, or to build a larger figure. Unrecognized arguments are passed as options to the axes object to allow for customization (i.e., setting a figure title, or setting labels on the axes). Falls back to an ascii_plot if matplotlib isn’t found, or if use_mpl is set to False.

classmethod proper(iterable)¶

A way to enter a perm in the traditional permuta way.

Examples

>>> Perm.one_based((4, 1, 3, 2))
Perm((3, 0, 2, 1))

classmethod random(length)¶

Return a random perm of the specified length.

Examples

>>> perm = Perm.random(8)
>>> len(perm) == 8
True
>>> # TODO: test perm in PermSet(8)

rank_encoding()¶

Returns the ‘rank value’(?) of each index in the permutation, the number of inversions ‘caused’ by the values at each index.

Examples

>>> Perm((3, 0, 2, 1)).rank_encoding()
[3, 0, 1, 0]
>>> Perm((0, 2, 4, 3, 1)).rank_encoding()
[0, 1, 2, 1, 0]

rank_val(i)¶

Returns the ‘rank value’(?) of index i, the number of inversions with the value at i being the greater element.

Examples

>>> Perm((3, 0, 2, 1)).rank_val(0)
3
>>> Perm((0, 2, 4, 3, 1)).rank_val(1)
1

remove(index=None)¶

Return the perm acquired by removing an element at a specified index.

Parameters:	index – <int> The index of the element to be removed. If None, the greatest element of the perm is removed.

Returns: <permuta.Perm>: The perm without the element (and other elements adjusted if needed).

Raises:	`IndexError` – Index is not valid.

Examples

>>> Perm((2, 0, 1)).remove()
Perm((0, 1))
>>> Perm((3, 0, 1, 2)).remove(0)
Perm((0, 1, 2))
>>> Perm((2, 0, 1)).remove(2)
Perm((1, 0))
>>> Perm((0,)).remove(0)
Perm(())

remove_element(selected=None)¶

Return the perm acquired by removing a specific element from self.

Parameters:	selected – <int> The element selected to be removed. It is an integer in the range of 0 to len(self) inclusive. If None, it defaults to len(self) - 1.

Returns: <permuta.Perm>: The perm with the selected element removed (and other elements adjusted as needed).

Raises:	`ValueError` – Selected element does not belong to perm. `TypeError` – Element passed is not an integer.

Examples

>>> Perm((3, 0, 1, 2)).remove_element()
Perm((0, 1, 2))
>>> Perm((3, 0, 2, 1)).remove_element(0)
Perm((2, 1, 0))

reverse()¶

Return the reverse of the perm self.

Examples

>>> Perm((1, 2, 5, 0, 3, 4)).reverse()
Perm((4, 3, 0, 5, 2, 1))
>>> Perm((0, 1)).reverse()
Perm((1, 0))

reverse_complement()¶

Return the reverse complement of self.

Equivalent to two left or right rotations.

Examples

>>> Perm((1, 2, 3, 0, 4)).reverse_complement()
Perm((0, 4, 1, 2, 3))
>>> Perm((2, 0, 1)).reverse_complement()
Perm((1, 2, 0))

rtlmax()¶

Returns the positions of the right-to-left maxima.

Examples

>>> Perm(24301).rtlmax()
[1, 2, 4]

rtlmax_ltrmin_decomposition()¶

Returns the right-to-left maxima, left-to-right minima decomposition. The decomposition consists of layers, starting with the first layer which is union of the right-to-left maximas and the left-to-right minimas and the next layer is defined similarly for the permutation with the first layer removed and so on.

TODO: If this function is to be kept, then it probably should return the layers as indices in the original permutation.

rtlmin()¶

Returns the positions of the right-to-left minima.

Examples

>>> Perm(204153).rtlmin()
[1, 3, 5]

classmethod scientific(iterable)¶

A way to enter a perm in the traditional permuta way.

Examples

>>> Perm.one_based((4, 1, 3, 2))
Perm((3, 0, 2, 1))

shift(times=1)¶

Return self shifted times steps to the right.

If shift is negative, shifted to the left.

Examples

>>> Perm((0, 1, 2)).shift_right()
Perm((2, 0, 1))
>>> Perm((0, 1, 2)).shift_right(-4)
Perm((1, 2, 0))

shift_down(times=1)¶

Return self shifted times steps down.

If times is negative, shifted up.

Examples

>>> Perm((0, 1, 2, 3)).shift_down(1)
Perm((3, 0, 1, 2))
>>> Perm((0, 1, 2, 3)).shift_down(-7)
Perm((3, 0, 1, 2))
>>> Perm((0,)).shift_down(1234)
Perm((0,))

shift_left(times=1)¶

Return self shifted times steps to the left.

If shift is negative, shifted to the right.

Examples

>>> Perm((0, 1, 2)).shift_left()
Perm((1, 2, 0))
>>> Perm((0, 1, 2)).shift_left(-4)
Perm((2, 0, 1))

shift_right(times=1)¶

Return self shifted times steps to the right.

If shift is negative, shifted to the left.

Examples

>>> Perm((0, 1, 2)).shift_right()
Perm((2, 0, 1))
>>> Perm((0, 1, 2)).shift_right(-4)
Perm((1, 2, 0))

shift_up(times=1)¶

Return self shifted times steps up.

If times is negative, shifted down.

Examples

>>> Perm((0, 1, 2, 3)).shift_up(1)
Perm((1, 2, 3, 0))
>>> Perm((0, 1, 2, 3)).shift_up(-7)
Perm((1, 2, 3, 0))
>>> Perm((0,)).shift_up(1234)
Perm((0,))

shrink_by_one()¶

Returns all patterns of length one less than the permutation. One layer of the downset, also called the shadow.

Example

>>> Perm((2, 0, 1)).children()
[Perm((0, 1)), Perm((1, 0))]
>>> Perm((4, 1, 6, 3, 0, 7, 2, 5)).children()
[Perm((3, 1, 5, 2, 0, 6, 4)), Perm((3, 0, 5, 2, 6, 1, 4)), Perm((4, 1, 6, 3, 0, 2, 5)), Perm((3, 5, 2, 0, 6, 1, 4)), Perm((4, 1, 3, 0, 6, 2, 5)), Perm((1, 5, 3, 0, 6, 2, 4)), Perm((3, 1, 5, 0, 6, 2, 4)), Perm((4, 1, 5, 3, 0, 6, 2))]

simple_location()¶

Searches for an interval, and returns (i,j) if one is found, where i is the size of the interval, and j is the first index of the interval.

Returns (0,0) if no interval is found, i.e., if the permutation is simple.

Simply calls the Perm.maximum_block(), the maximum block is any block.

skew_decomposable()¶

Determines whether the permutation is expressible as the skew sum of two permutations.

>>> p = Perm.random(8).direct_sum(Perm.random(12))
>>> p.skew_decomposable()
False
>>> p.complement().skew_decomposable()
True

skew_sum(*others)¶

Return the skew sum of two or more perms.

Parameters:	self – A perm. others – <permuta.Perm> argument list Perms.

Returns: <permuta.Perm>: The skew sum of all the perms.

Examples

>>> Perm((0,)).skew_sum(Perm((0, 1)))
Perm((2, 0, 1))
>>> Perm((0,)).skew_sum(Perm((0, 1)), Perm((2, 1, 0)))
Perm((5, 3, 4, 2, 1, 0))

classmethod standardize(iterable)¶

Return the perm corresponding to iterable.

Duplicate elements are allowed and become consecutive elements (see example).

The standardize alias is supplied for backwards compatibility with permpy. However, the permpy version did not allow for duplicate elements.

Examples

>>> Perm.to_standard("a2gsv3")
Perm((2, 0, 3, 4, 5, 1))
>>> Perm.to_standard("caaba")
Perm((4, 0, 1, 3, 2))

sum_decomposable()¶

Determines whether the permutation is expressible as the direct sum of two permutations.

>>> p = Perm.random(4).direct_sum(Perm.random(15))
>>> p.sum_decomposable()
True
>>> p.reverse().sum_decomposable()
False

sum_indecomposable_sequence()¶

threepats()¶

Returns a dictionary of the number of occurrences of each permutation pattern of length 3.

Examples

>>> Perm((2, 1, 0, 3)).threepats()
{Perm((0, 1, 2)): 0, Perm((0, 2, 1)): 0, Perm((1, 0, 2)): 3, Perm((1, 2, 0)): 0, Perm((2, 0, 1)): 0, Perm((2, 1, 0)): 1}

classmethod to_standard(iterable)¶

Return the perm corresponding to iterable.

Duplicate elements are allowed and become consecutive elements (see example).

The standardize alias is supplied for backwards compatibility with permpy. However, the permpy version did not allow for duplicate elements.

Examples

>>> Perm.to_standard("a2gsv3")
Perm((2, 0, 3, 4, 5, 1))
>>> Perm.to_standard("caaba")
Perm((4, 0, 1, 3, 2))

to_tikz()¶

static toggle_check()¶

classmethod unrank(number, length=None)¶

Examples

>>> Perm.unrank(0)
Perm(())
>>> Perm.unrank(1)
Perm((0,))
>>> Perm.unrank(2)
Perm((0, 1))
>>> Perm.unrank(3)
Perm((1, 0))
>>> Perm.unrank(4)
Perm((0, 1, 2))
>>> Perm.unrank(5)
Perm((0, 2, 1))
>>> Perm.unrank(1, 3)
Perm((0, 2, 1))

valley_list()¶

Return the list of valleys of self.

This method is for backwards compatibility with permpy.

valleys()¶

Yield the indices of the valleys of self.

The i-th element of a perm is a valley if: self[i-1] > self[i] < self[i+1].

Examples

>>> tuple(Perm((5, 3, 4, 0, 2, 1)).valleys())
(1, 3)
>>> tuple(Perm((2, 0, 1)).valleys())
(1,)
>>> tuple(Perm((1, 2, 0)).valleys())
()

MeshPatt¶

class permuta.MeshPatt(pattern=Perm(()), shading=frozenset())¶

Bases: permuta.MeshPatt.MeshPatternBase, permuta.interfaces.Patt.Patt, permuta.interfaces.Rotatable.Rotatable, permuta.interfaces.Shiftable.Shiftable, permuta.interfaces.Flippable.Flippable

A mesh pattern class.

pattern¶: <permuta.Perm> The underlying classical pattern.

shading¶: frozenset The shading as a immutable set of coordinates, with lower-left as origin.

static __new__(pattern=Perm(()), shading=frozenset())¶

Return a MeshPatt instance.

Parameters:	cls – The class of which an instance is requested. pattern – <permuta.Perm> or <collections.Iterable> An perm or an iterable corresponding to a legal perm. shading – <collections.Iterable> An iterable of 2-tuples.
Raises:	`TypeError` – Bad argument type. `ValueError` – Bad argument, but correct type.

add_decrease(pos)¶

Adds an decreasing pattern (1, 0) into the given coordinate.

Parameters:	pos – tuple The coordinate of the position to insert (1, 0) into.

Returns: <permuta.MeshPatt>: The new pattern with the decreasing pattern inserted into pos.

Examples

>>> MeshPatt((0,)).add_decrease((0, 0))
MeshPatt(Perm((1, 0, 2)), frozenset())
>>> MeshPatt((0, 1, 2), [(1, 0), (2, 1), (3, 2)]).add_decrease((2, 0))
MeshPatt(Perm((2, 3, 1, 0, 4)), frozenset({(1, 2), (5, 4), (3, 3), (2, 3), (4, 3), (1, 0), (1, 1)}))

add_increase(pos)¶

Adds an increasing pattern (0, 1) into the given coordinate.

Parameters:	pos – tuple The coordinate of the position to insert (0, 1) into.

Returns: <permuta.MeshPatt>: The new pattern with the increased pattern inserted into pos.

Examples

>>> MeshPatt((0,)).add_increase((0, 0))
MeshPatt(Perm((0, 1, 2)), frozenset())
>>> MeshPatt((0, 1, 2), [(1, 0), (2, 1), (3, 2)]).add_increase((2, 0))
MeshPatt(Perm((2, 3, 0, 1, 4)), frozenset({(1, 2), (5, 4), (3, 3), (2, 3), (4, 3), (1, 0), (1, 1)}))

add_point(pos, shade_dir=-1, safe=True)¶

Returns a mesh pattern with a point added in the box at position pos. If shade_dir is specified adds shading in that direction.

Parameters:	pos – tuple Coordinates corresponding to a box in the pattern. shade_dir – int The direction which to shade within the box. safe – bool, optional True to check if box must not be shaded.
Raises:	`ValueError` – Bad box argument, if it is already shaded. `TypeError` – Bad argument type.

Returns: <permuta.MeshPatt>: The mesh pattern with a point added in pos.

all_symmetries()¶

Return the set of all symmetries of the mesh pattern.

Returns: <set>: All the symmetries of a mesh pattern.

can_shade(pos)¶

Returns whether it is possible to shade the box at position pos according to the Shading Lemma. Every direction is checked and the list of the values of the adjacent points to the box that can be used is returned.

Parameters:	pos – tuple The position of the box to check.

Returns: list: The values of the points in the permutation adjacent to the box at pos that can be used to shade the box.

Examples

>>> MeshPatt((0,),[(0, 0)]).can_shade((1, 1))
[]
>>> MeshPatt((1, 2, 0), [(2,2),(3,0),(3,2),(3,3)]).can_shade((1, 2))
[1, 2]

can_shade2(pos1, pos2)¶

Returns whether it is possible to shade the boxes at positions pos1, pos2 according to the Shading Lemma. Every direction is checked and the list of the values of the adjacent points to the box that can be used is returned.

Parameters:	pos1 – tuple The position of the first box to check. pos2 – tuple The position of the second box to check.

Returns: list: The values of the points in the permutation adjacent to the boxes at pos1 and pos2 that can be used to shade the box.

Examples:

can_simul_shade(pos1, pos2)¶

Returns whether it is possible to shade the boxes at positions pos1, pos2 according to the Shading Lemma. Every direction is checked and the list of the values of the adjacent points to the box that can be used is returned.

Parameters:	pos1 – tuple The position of the first box to check. pos2 – tuple The position of the second box to check.

Returns: list: The values of the points in the permutation adjacent to the boxes at pos1 and pos2 that can be used to shade the box.

Examples:

complement()¶

Returns the complement of the mesh pattern, which has the complement of the underlying pattern and every shading flipped across the horizontal axis.

Returns: <permuta.MeshPatt>: The complement of the meshpatt.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).complement()
MeshPatt(Perm((0,)), frozenset({(0, 0)}))
>>> MeshPatt(Perm((0, 2, 1)), frozenset({(0, 1), (0, 0), (1, 0), (0, 2), (0, 3)})).complement()
MeshPatt(Perm((2, 0, 1)), frozenset({(0, 1), (1, 3), (0, 0), (0, 3), (0, 2)}))

flip_diagonal()¶

Return self flipped along the diagonal which is equivalent to the ‘inverse’ of the pattern.

Returns: <permuta.MeshPatt>: The ‘inverse’ of the meshpatt.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).inverse()
MeshPatt(Perm((0,)), frozenset({(1, 0)}))

flip_horizontal()¶

Return self flipped horizontally which is equivalent to the complement.

Returns: <permuta.MeshPatt>: The complement of the meshpatt.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).flip_horizontal()
MeshPatt(Perm((0,)), frozenset({(0, 0)}))
>>> MeshPatt(Perm((0, 2, 1)), frozenset({(0, 1), (0, 0), (1, 0), (0, 2), (0, 3)})).flip_horizontal()
MeshPatt(Perm((2, 0, 1)), frozenset({(0, 1), (1, 3), (0, 0), (0, 3), (0, 2)}))

flip_vertical()¶

Return self flipped vertically which is equivalent to the meshpatt reversed.

Returns: <permuta.MeshPatt>: The meshpatt reversed.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).flip_vertical()
MeshPatt(Perm((0,)), frozenset({(1, 1)}))
>>> MeshPatt(Perm((2, 1, 0)), frozenset({(3, 2), (3, 3), (0, 2), (2, 2), (1, 1)})).flip_vertical()
MeshPatt(Perm((0, 1, 2)), frozenset({(1, 2), (3, 2), (2, 1), (0, 3), (0, 2)}))

has_anchored_point()¶

Checks if the mesh pattern has any point anchored to the boundary. Returns a tuple (right, top, left, bottom) where each value represent whether the point is anchored to the corresponding direction.

Returns: tuple: Each boolean in the tuple tells whether the mesh pattern is anchored to the corresponding direction.

Examples

>>> MeshPatt(Perm((0, 1)), frozenset({(0, 0), (1, 0), (2, 0), (1, 1)})).has_anchored_point()
(False, False, False, True)

inverse()¶

Returns the inverse of the meshpatt, that is the meshpatt with the underlying classical pattern as the inverse and the shadings hold the same relation between the points. This is equivalent to flipping the pattern over the diagonal.

Returns: <permuta.MeshPatt>: The ‘inverse’ of the meshpatt.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).inverse()
MeshPatt(Perm((0,)), frozenset({(1, 0)}))

is_pointfree(lower_left, upper_right)¶

Check if a region in the grid has no points.

Parameters:	self – A mesh pattern. lower_left – (int, int) A point coordinate of self. upper_right – (int, int) A point coordinate of self.
Raises:	`ValueError` – Bad argument, but correct type.

Returns: bool: True if and only if all points self[x] for x in the range lower_left[0] + 1 to upper_right[0] - 1 (inclusive) have values less than lower_left[1] or greater than or equal to upper_right[1].

is_shaded(lower_left, upper_right=None)¶

Check if a region of the grid is shaded.

Parameters:	self – A mesh pattern. lower_left – (int, int) A shading coordinate of self. upper_right – (int, int) A shading coordinate of self.
Raises:	`ValueError` – Bad argument, but correct type.

Returns: bool: If upper_right is None, then True if and only if lower_left is shaded; otherwise, True if and only if all regions (x, y) for x in the range lower_left[0] to upper_right[0] (inclusive) and for y in the range lower_left[1] to upper_right[1] (inclusive) are shaded.

latex(scale=0.3)¶

Returns the LaTeX code for the TikZ figure of the mesh pattern. The LaTeX code requires the TikZ library ‘patterns’.

Parameters:	scale – <numbers.Real> The scale of the image.

Returns: str: The LaTeX code for the TikZ figure of the pattern.

non_pointless_boxes()¶

Returns the coordinates of the boxes that have a point on their boundaries in one of their four corners.

Returns: set: The set of boxes with points in one of the corners.

Examples

>>> MeshPatt(Perm((0, 1)), frozenset({(0, 1), (2, 0), (0, 2)})).non_pointless_boxes()
{(0, 1), (1, 2), (0, 0), (2, 1), (2, 2), (1, 0), (1, 1)}
>>> MeshPatt(Perm((1, 0, 2)), frozenset({(1, 3), (3, 0), (0, 3), (0, 1), (1, 2), (3, 1), (2, 0), (1, 1)})).non_pointless_boxes()
{(1, 2), (0, 1), (3, 2), (3, 3), (0, 2), (2, 1), (2, 0), (2, 3), (2, 2), (1, 0), (1, 1)}

occurrences_in(perm)¶

Find all indices of occurrences of self in perm.

Parameters:	self – The mesh pattern whose occurrences are to be found. perm – <permuta.Perm> The permutation to search for occurrences in.

Yields: numbers.Integral: The indices of the occurrences of self in perm. Each yielded element l is a list of integer indices of the permutation perm such that self.pattern == permuta.Perm.to_standard([perm[i] for i in l]) and that no element not in the occurrence falls within self.shading.

static random(length)¶

Return a random mesh pattern of the specified length.

Parameters:	length – <numbers.Integral> The length of the random pattern.

Examples

>>> MeshPatt.random(1) in set(MeshPatt.unrank(Perm((0)), i) for i in range(0, 16))
True
>>> len(MeshPatt.random(4))
4

rank()¶

Computes the rank of the mesh pattern, the bit string of the shadings interpreted as an integer.

Returns: numbers.Integral: The rank of the mesh pattern.

Examples

>>> rank = MeshPatt(Perm((1, 0, 2)), frozenset({(0, 0), (3, 0), (0, 2), (2, 1), (2, 3), (1, 2), (3, 3), (3, 1), (1, 1)})).rank()
>>> rank
47717
>>> bin(rank)
'0b1011101001100101'

reverse()¶

Returns the reversed mesh patterns, which has the underlying pattern reversed and every shading flipped across the vertical axis.

Returns: <permuta.MeshPatt>: The meshpatt reversed.

Examples

>>> MeshPatt(Perm((0,)), frozenset({(0, 1)})).reverse()
MeshPatt(Perm((0,)), frozenset({(1, 1)}))
>>> MeshPatt(Perm((2, 1, 0)), frozenset({(3, 2), (3, 3), (0, 2), (2, 2), (1, 1)})).reverse()
MeshPatt(Perm((0, 1, 2)), frozenset({(1, 2), (3, 2), (2, 1), (0, 3), (0, 2)}))

shadable_boxes()¶

Returns a dictionary of all tuples of shadable boxes with the shading lemma, with the keys as the points used to shade the tuples of boxes.

Returns: dict: Dictionary with keys as points and values as tuples of boxes.

Examples: >>> dict(MeshPatt(Perm((0, 3, 1, 2)), frozenset({(3, 2), (3, 0), (4, 2), (1, 0), (0, 3), (1, 2), (2, 0), (0, 4), (0, 2)})).shadable_boxes()) {0: [((0, 0),)], 3: [((1, 3),), ((1, 3), (1, 4)), ((1, 4),)], 1: [((2, 2),)]}

shade(positions)¶

Returns the mesh pattern with the added shadings given by positions.

Parameters:	positions – tuple or <collections.Iterable> The shading given as a single coordinate or as an iterable of coordinates.
Raises:	`ValueError` – Bad argument, but correct type.

Returns: <permuta.MeshPatt>: The new meshpatt with the added shadings.

sub_mesh_pattern(indices)¶

Return the mesh pattern induced by indices.

Parameters:	indices – <collections.Iterable> of <numbers.Integral> A list of unique indices of elements in self.

Returns: <permuta.MeshPattern>

A mesh pattern where the pattern is the permutation induced by the indices and a region is shaded if and only if the corresponding region of self is fully shaded.

Exampes:

>>> shading = frozenset({(3, 2), (1, 3), (4, 2), (0, 3), (1, 2), (4, 3), (3, 4), (4, 1)})
>>> MeshPatt(Perm((3, 2, 1, 0)), shading).sub_mesh_pattern((0, 1, 3))
MeshPatt(Perm((2, 1, 0)), frozenset({(1, 2), (3, 2), (3, 1), (0, 2)}))
>>> MeshPatt(Perm((2, 3, 1, 0)), shading).sub_mesh_pattern((1, 2, 3))
MeshPatt(Perm((2, 1, 0)), frozenset({(3, 2), (3, 1), (2, 3)}))

static unrank(pattern, number)¶

Return the number-th shading of pattern.

Parameters:	pattern – <permuta.Perm> or <collections.Iterable> An perm or an iterable corresponding to a legal perm. number – <numbers.Integral> An integer of which binary representation corresponds to a legal shading.
Raises:	`TypeError` – Bad argument type. `ValueError` – Bad argument, but correct type.

Examples

>>> bin(22563)
'0b101100000100011'
>>> MeshPatt.unrank((0, 1, 2), 22563)
MeshPatt(Perm((0, 1, 2)), frozenset({(0, 1), (3, 2), (0, 0), (3, 0), (2, 3), (1, 1)}))

descriptors¶

Submodules¶

permuta.descriptors.Basis module¶

class permuta.descriptors.Basis.Basis¶

Bases: permuta.descriptors.Descriptor.Descriptor, tuple

A basis class.

A PermSet can be built with a Basis instance by using the basis provided to it to see if a perm should be in the PermSet or not. Additionally, various fast methods exist to build a PermSet defined by a basis.

is_polynomial()¶

union(perms)¶

permuta.descriptors.Descriptor module¶

class permuta.descriptors.Descriptor.Descriptor¶: Bases: object

permuta.descriptors.Predicate module¶

class permuta.descriptors.Predicate.Predicate(predicate)¶

Bases: permuta.descriptors.Descriptor.Descriptor

A predicate class.

A PermSet can be built with a Predicate instance by using the predicate provided to it to see if a perm should be in the PermSet or not.

Module contents¶

interfaces¶

Submodules¶

permuta.interfaces.Displayable module¶

class permuta.interfaces.Displayable.Displayable¶

Bases: object

display()¶: Display on screen.

export()¶: Export to file.

plot()¶

Plot a la matplotlib.

Returns a matplotlib Axes object or None.

permuta.interfaces.Flippable module¶

class permuta.interfaces.Flippable.Flippable¶

Bases: abc.ABC

flip_antidiagonal()¶: Return self flipped along the antidiagonal.

flip_diagonal()¶: Return self flipped along the diagonal.

flip_horizontal()¶: Return self flipped horizontally.

flip_vertical()¶: Return self flipped vertically.

permuta.interfaces.Patt module¶

class permuta.interfaces.Patt.Patt¶

Bases: abc.ABC

avoided_by(*perms)¶

Check if self is avoided by perms.

Parameters:	self – A classical/mesh pattern. perms – [permuta.Permutation] A list of permutations.

Returns: bool: True if and only if every permutation in perms avoids self.

contained_in(*perms)¶

Check if self is a pattern of perms.

Parameters:	self – A classical/mesh pattern. perms – [permuta.Permutation] A list of permutations.

Returns: bool: True if and only if self is a pattern of all permutations in perms.

count_occurrences_in(perm)¶

Count the number of occurrences of self in perm.

Parameters:	self – A classical/mesh pattern. perm – permuta.Permutation A permutation.

Returns: int: The number of times self occurs in perm.

occurrences_in(perm)¶: Find all indices of occurrences of self in perm.

permuta.interfaces.Rotatable module¶

class permuta.interfaces.Rotatable.Rotatable¶

Bases: abc.ABC

rotate(times=1)¶: Return self rotated 90 degrees to the right.

rotate_left(times=1)¶: Return self rotated 90 degrees to the left.

rotate_right(times=1)¶: Return self rotated 90 degrees to the right.

permuta.interfaces.Shiftable module¶

class permuta.interfaces.Shiftable.Shiftable¶

Bases: abc.ABC

shift_down(times=1)¶

Return self shifted times steps down.

If times is negative, shifted up.

shift_left(times=1)¶

Return self shifted times steps to the left.

If times is negative, shifted to the right.

shift_right(times=1)¶

Return self shifted times steps to the right.

If shift is negative, shifted to the left.

shift_up(times=1)¶

Return self shifted times steps up.

If times is negative, shifted down.

Module contents¶

misc¶

Submodules¶

permuta.misc.algorithm_x module¶

class permuta.misc.algorithm_x.AlgorithmX(rows, cols, solution_callback)¶

Bases: object

search(k=0, at_most=None)¶

set_value(row, col, val=True)¶

setup()¶

class permuta.misc.algorithm_x.Node(row, col)¶: Bases: object

permuta.misc.algorithm_x.cover(c)¶

permuta.misc.algorithm_x.uncover(c)¶

permuta.misc.checking module¶

permuta.misc.checking.index(obj, maximum=None)¶

Check if an object is an index and raise exceptions if it isn’t.

Parameters:	obj – <object> The object to be checked. maximum – <numbers.Integral> The number the object is not to exceed if it is a number.
Raises:	`TypeError` – Object is not an integral number. `ValueError` – Object is an integral number, but not a valid index.

Examples

>>> index(4)
>>> index(0)
>>> index(-3)
Traceback (most recent call last):
    ...
ValueError: -3 is not a valid index
>>> index(21, 30)
>>> index(0.3)
Traceback (most recent call last):
    ...
TypeError: '0.3' object is not a valid index
>>> index(333, 30)
Traceback (most recent call last):
    ...
ValueError: 333 is not a valid index

permuta.misc.counting module¶

permuta.misc.counting.binomial(n, k)¶

permuta.misc.counting.catalan(n)¶

permuta.misc.counting.factorial(n)¶

permuta.misc.dancing_links module¶

class permuta.misc.dancing_links.DancingLinks(lst=None)¶

Bases: object

append(value)¶

erase(node)¶

restore(node)¶

class permuta.misc.dancing_links.Node(value, prev=None, next=None)¶: Bases: object

permuta.misc.exact_cover module¶

permuta.misc.exact_cover.exact_cover(bss, validcnt, max_cnt, ignore_first, allow_overlap_in_first)¶

permuta.misc.exact_cover.exact_cover_smallest(bss, validcnt, max_cnt, ignore_first, allow_overlap_in_first)¶

permuta.misc.iterable_floor_and_ceiling module¶

class permuta.misc.iterable_floor_and_ceiling.FloorAndCeiling(floor, ceiling)¶

Bases: tuple

__getnewargs__()¶: Return self as a plain tuple. Used by copy and pickle.

static __new__(_cls, floor, ceiling)¶: Create new instance of FloorAndCeiling(floor, ceiling)

__repr__()¶: Return a nicely formatted representation string

ceiling¶: Alias for field number 1

floor¶: Alias for field number 0

permuta.misc.iterable_floor_and_ceiling.left_floor_and_ceiling(iterable, default_floor=None, default_ceiling=None)¶

Find the left floor and ceiling indices of iterable.

Define left_floor of an element in a sequence to be the index of the greatest smaller element to the left of said element, or default_floor if there is none. Similarly define default_ceiling. This function yields a tuple (left_floor, left_ceiling) for each element of iterable.

Parameters:	iterable – <iterable> An iterable of totally ordered unique elements. default_floor – <object> default_ceiling – <object>

Yields: (int, int): The i-th yielded tuple is the left floor and ceiling indices of the i-th element of the iterable. The tuples are named tuples with floor and ceiling attributes.

permuta.misc.iterable_floor_and_ceiling.right_floor_and_ceiling(iterable, default_floor=None, default_ceiling=None)¶: The right counterpart of left_floor_and_ceiling.

permuta.misc.misc module¶

permuta.misc.misc.binary_search(a, x)¶

permuta.misc.misc.choose(l, k)¶

permuta.misc.misc.flatten(lst)¶

permuta.misc.misc.subsets(elems)¶

permuta.misc.ordered_set_partitions module¶

permuta.misc.ordered_set_partitions.helper(lst, parts)¶

permuta.misc.ordered_set_partitions.ordered_set_partitions(lst, parts, CACHE={})¶

permuta.misc.progressbar module¶

class permuta.misc.progressbar.ProgressBar¶

Bases: object

static clear()¶

static create(mx, mn=0)¶

static draw(fin=False)¶

static finish()¶

static progress(prg=None, fin=False)¶

permuta.misc.ranges module¶

permuta.misc.ranges.cyclic_range(start, end, restart)¶: Yields start,...,end-1,restart,...,start-1.

permuta.misc.ranges.modulo_range(start, modulo)¶: Yields start,...,modulo-1,0,...,start-1.

permuta.misc.triemap module¶

class permuta.misc.triemap.TrieMap¶

Bases: object

height()¶

class permuta.misc.triemap.TrieNode¶

Bases: object

child(k)¶

height()¶

permuta.misc.union_find module¶

class permuta.misc.union_find.UnionFind(n=0)¶

Bases: object

A collection of distjoint sets.

__init__(n=0)¶: Creates a collection of n disjoint unit sets.

add()¶: Add a unit set containing a new element to the collection, and return the identifier of the new element.

find(x)¶: Return the identifier of a representative element for the set containing the element with identifier x.

size(x)¶: Return the number of elements in the set containing the element with identifier x.

unite(x, y)¶: Unite the two sets containing the elements with identifiers x and y, respectively.

Module contents¶

permuta.misc.signum(n)¶

permutils¶

Submodules¶

permuta.permutils.finite module¶

permuta.permutils.finite.is_finite(basis)¶

permuta.permutils.insertion_encodable module¶

permuta.permutils.insertion_encodable.insertion_encodable_properties(perm)¶

permuta.permutils.insertion_encodable.is_decr_next_decr(perm)¶

permuta.permutils.insertion_encodable.is_decr_next_incr(perm)¶

permuta.permutils.insertion_encodable.is_incr_next_decr(perm)¶

permuta.permutils.insertion_encodable.is_incr_next_incr(perm)¶

permuta.permutils.insertion_encodable.is_insertion_encodable(basis)¶

permuta.permutils.insertion_encodable.is_insertion_encodable_maximum(basis)¶

permuta.permutils.insertion_encodable.is_insertion_encodable_rightmost(basis)¶

permuta.permutils.polynomial module¶

permuta.permutils.polynomial.in_L2(L)¶

permuta.permutils.polynomial.is_decr(L)¶

permuta.permutils.polynomial.is_incr(L)¶

permuta.permutils.polynomial.is_non_polynomial(basis)¶

permuta.permutils.polynomial.is_polynomial(basis)¶

permuta.permutils.polynomial.types(perm)¶

permuta.permutils.symmetry module¶

permuta.permutils.symmetry.all_symmetry_sets(input_perms)¶

permuta.permutils.symmetry.antidiagonal_set(perms)¶

permuta.permutils.symmetry.complement_set(perms)¶

permuta.permutils.symmetry.inverse_set(perms)¶

permuta.permutils.symmetry.lex_min(perms)¶

permuta.permutils.symmetry.reduced_set(input_perms)¶

permuta.permutils.symmetry.reverse_set(perms)¶

permuta.permutils.symmetry.rotate_180_clockwise_set(perms)¶

permuta.permutils.symmetry.rotate_270_clockwise_set(perms)¶

permuta.permutils.symmetry.rotate_90_clockwise_set(perms)¶

permuta.permutils.symmetry.rotate_set(perms)¶

Permuta – A permutation library¶

Installing¶

Basic¶

Advanced¶

The Permuta API¶

The permuta.demo package¶

Perm¶

PermClass¶

The permuta package¶

Perm¶

MeshPatt¶

descriptors¶

Submodules¶

permuta.descriptors.Basis module¶

permuta.descriptors.Descriptor module¶

permuta.descriptors.Predicate module¶

Module contents¶

interfaces¶

Submodules¶

permuta.interfaces.Displayable module¶

permuta.interfaces.Flippable module¶

permuta.interfaces.Patt module¶

permuta.interfaces.Rotatable module¶

permuta.interfaces.Shiftable module¶

Module contents¶

misc¶

Submodules¶

permuta.misc.algorithm_x module¶

permuta.misc.checking module¶

permuta.misc.counting module¶

permuta.misc.dancing_links module¶

permuta.misc.exact_cover module¶

permuta.misc.iterable_floor_and_ceiling module¶

permuta.misc.misc module¶

permuta.misc.ordered_set_partitions module¶

permuta.misc.progressbar module¶

permuta.misc.ranges module¶

permuta.misc.triemap module¶

permuta.misc.union_find module¶

Module contents¶

permutils¶

Submodules¶

permuta.permutils.finite module¶

permuta.permutils.insertion_encodable module¶

permuta.permutils.polynomial module¶

permuta.permutils.symmetry module¶

Module contents¶

Indices and tables¶