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())
()