Permutations

The Permutations module. Use Permutation? to get information about the Permutation class, and Permutations? to get information about the combinatorial class of permutations.

Warning

This file defined Permutation which depends upon CombinatorialElement despite it being deprecated (see Issue #13742). This is dangerous. In particular, the Permutation._left_to_right_multiply_on_right() method (which can be called through multiplication) disables the input checks (see Permutation()). This should not happen. Do not trust the results.

What does this file define ?

The main part of this file consists in the definition of permutation objects, i.e. the Permutation() method and the Permutation class. Global options for elements of the permutation class can be set through the Permutations.options() object.

Below are listed all methods and classes defined in this file.

Methods of Permutations objects

left_action_product()	Return the product of self with another permutation, in which the other permutation is applied first.
right_action_product()	Return the product of self with another permutation, in which self is applied first.
size()	Return the size of the permutation self.
cycle_string()	Return the disjoint-cycles representation of self as string.
next()	Return the permutation that follows self in lexicographic order (in the same symmetric group as self).
prev()	Return the permutation that comes directly before self in lexicographic order (in the same symmetric group as self).
to_tableau_by_shape()	Return a tableau of shape shape with the entries in self.
to_cycles()	Return the permutation self as a list of disjoint cycles.
forget_cycles()	Return self under the forget cycle map.
to_permutation_group_element()	Return a PermutationGroupElement equal to self.
signature()	Return the signature of the permutation sef.
is_even()	Return True if the permutation self is even, and False otherwise.
to_matrix()	Return a matrix representing the permutation self.
rank()	Return the rank of self in lexicographic ordering (on the symmetric group containing self).
to_inversion_vector()	Return the inversion vector of a permutation self.
inversions()	Return a list of the inversions of permutation self.
stack_sort()	Return the permutation obtained by sorting self through one stack.
to_digraph()	Return a digraph representation of self.
show()	Display the permutation as a drawing.
number_of_inversions()	Return the number of inversions in the permutation self.
noninversions()	Return the k-noninversions in the permutation self.
number_of_noninversions()	Return the number of k-noninversions in the permutation self.
length()	Return the Coxeter length of a permutation self.
inverse()	Return the inverse of a permutation self.
ishift()	Return the i-shift of self.
iswitch()	Return the i-switch of self.
runs()	Return a list of the runs in the permutation self.
longest_increasing_subsequence_length()	Return the length of the longest increasing subsequences of self.
longest_increasing_subsequences()	Return the list of the longest increasing subsequences of self.
longest_increasing_subsequences_number()	Return the number of longest increasing subsequences
cycle_type()	Return the cycle type of self as a partition of len(self).
foata_bijection()	Return the image of the permutation self under the Foata bijection \(\phi\).
foata_bijection_inverse()	Return the image of the permutation self under the inverse of the Foata bijection \(\phi\).
fundamental_transformation()	Return the image of the permutation self under the Renyi-Foata-Schuetzenberger fundamental transformation.
fundamental_transformation_inverse()	Return the image of the permutation self under the inverse of the Renyi-Foata-Schuetzenberger fundamental transformation.
destandardize()	Return destandardization of self with respect to weight and ordered_alphabet.
to_lehmer_code()	Return the Lehmer code of the permutation self.
to_lehmer_cocode()	Return the Lehmer cocode of self.
reduced_word()	Return the reduced word of the permutation self.
reduced_words()	Return a list of the reduced words of the permutation self.
reduced_words_iterator()	An iterator for the reduced words of the permutation self.
reduced_word_lexmin()	Return a lexicographically minimal reduced word of a permutation self.
fixed_points()	Return a list of the fixed points of the permutation self.
is_derangement()	Return True if the permutation self is a derangement, and False otherwise.
is_simple()	Return True if the permutation self is simple, and False otherwise.
number_of_fixed_points()	Return the number of fixed points of the permutation self.
recoils()	Return the list of the positions of the recoils of the permutation self.
number_of_recoils()	Return the number of recoils of the permutation self.
recoils_composition()	Return the composition corresponding to the recoils of self.
descents()	Return the list of the descents of the permutation self.
idescents()	Return a list of the idescents of self.
idescents_signature()	Return the list obtained by mapping each position in self to \(-1\) if it is an idescent and \(1\) if it is not an idescent.
number_of_descents()	Return the number of descents of the permutation self.
number_of_idescents()	Return the number of idescents of the permutation self.
descents_composition()	Return the composition corresponding to the descents of self.
descent_polynomial()	Return the descent polynomial of the permutation self.
major_index()	Return the major index of the permutation self.
imajor_index()	Return the inverse major index of the permutation self.
to_major_code()	Return the major code of the permutation self.
peaks()	Return a list of the peaks of the permutation self.
number_of_peaks()	Return the number of peaks of the permutation self.
saliances()	Return a list of the saliances of the permutation self.
number_of_saliances()	Return the number of saliances of the permutation self.
bruhat_lequal()	Return True if self is less or equal to p2 in the Bruhat order.
weak_excedences()	Return all the numbers self[i] such that self[i] >= i+1.
bruhat_inversions()	Return the list of inversions of self such that the application of this inversion to self decrements its number of inversions.
bruhat_inversions_iterator()	Return an iterator over Bruhat inversions of self.
bruhat_succ()	Return a list of the permutations covering self in the Bruhat order.
bruhat_succ_iterator()	An iterator for the permutations covering self in the Bruhat order.
bruhat_pred()	Return a list of the permutations covered by self in the Bruhat order.
bruhat_pred_iterator()	An iterator for the permutations covered by self in the Bruhat order.
bruhat_smaller()	Return the combinatorial class of permutations smaller than or equal to self in the Bruhat order.
bruhat_greater()	Return the combinatorial class of permutations greater than or equal to self in the Bruhat order.
permutohedron_lequal()	Return True if self is less or equal to p2 in the permutohedron order.
permutohedron_succ()	Return a list of the permutations covering self in the permutohedron order.
permutohedron_pred()	Return a list of the permutations covered by self in the permutohedron order.
permutohedron_smaller()	Return a list of permutations smaller than or equal to self in the permutohedron order.
permutohedron_greater()	Return a list of permutations greater than or equal to self in the permutohedron order.
right_permutohedron_interval_iterator()	Return an iterator over permutations in an interval of the permutohedron order.
right_permutohedron_interval()	Return a list of permutations in an interval of the permutohedron order.
has_pattern()	Test whether the permutation self matches the pattern.
avoids()	Test whether the permutation self avoids the pattern.
pattern_positions()	Return the list of positions where the pattern patt appears in self.
reverse()	Return the permutation obtained by reversing the 1-line notation of self.
complement()	Return the complement of the permutation which is obtained by replacing each value \(x\) in the 1-line notation of self with \(n - x + 1\).
permutation_poset()	Return the permutation poset of self.
dict()	Return a dictionary corresponding to the permutation self.
action()	Return the action of the permutation self on a list.
robinson_schensted()	Return the pair of standard tableaux obtained by running the Robinson-Schensted Algorithm on self.
left_tableau()	Return the left standard tableau after performing the RSK algorithm.
right_tableau()	Return the right standard tableau after performing the RSK algorithm.
increasing_tree()	Return the increasing tree of self.
increasing_tree_shape()	Return the shape of the increasing tree of self.
binary_search_tree()	Return the binary search tree of self.
sylvester_class()	Iterate over the equivalence class of self under sylvester congruence
RS_partition()	Return the shape of the tableaux obtained by the RSK algorithm.
remove_extra_fixed_points()	Return the permutation obtained by removing any fixed points at the end of self.
retract_plain()	Return the plain retract of self to a smaller symmetric group \(S_m\).
retract_direct_product()	Return the direct-product retract of self to a smaller symmetric group \(S_m\).
retract_okounkov_vershik()	Return the Okounkov-Vershik retract of self to a smaller symmetric group \(S_m\).
hyperoctahedral_double_coset_type()	Return the coset-type of self as a partition.
binary_search_tree_shape()	Return the shape of the binary search tree of self (a non labelled binary tree).
shifted_concatenation()	Return the right (or left) shifted concatenation of self with a permutation other.
shifted_shuffle()	Return the shifted shuffle of self with a permutation other.

Other classes defined in this file

Permutations
Permutations_nk
Permutations_mset
Permutations_set
Permutations_msetk
Permutations_setk
Arrangements
Arrangements_msetk
Arrangements_setk
StandardPermutations_all
StandardPermutations_n_abstract
StandardPermutations_n
StandardPermutations_descents
StandardPermutations_recoilsfiner
StandardPermutations_recoilsfatter
StandardPermutations_recoils
StandardPermutations_bruhat_smaller
StandardPermutations_bruhat_greater
CyclicPermutations
CyclicPermutationsOfPartition
StandardPermutations_avoiding_12
StandardPermutations_avoiding_21
StandardPermutations_avoiding_132
StandardPermutations_avoiding_123
StandardPermutations_avoiding_321
StandardPermutations_avoiding_231
StandardPermutations_avoiding_312
StandardPermutations_avoiding_213
StandardPermutations_avoiding_generic
PatternAvoider

Functions defined in this file

from_major_code()	Return the permutation corresponding to major code mc.
from_permutation_group_element()	Return a Permutation give a PermutationGroupElement pge.
from_rank()	Return the permutation with the specified lexicographic rank.
from_inversion_vector()	Return the permutation corresponding to inversion vector iv.
from_cycles()	Return the permutation with given disjoint-cycle representation cycles.
from_lehmer_code()	Return the permutation with Lehmer code lehmer.
from_reduced_word()	Return the permutation corresponding to the reduced word rw.
bistochastic_as_sum_of_permutations()	Return a given bistochastic matrix as a nonnegative linear combination of permutations.
bounded_affine_permutation()	Return a partial permutation representing the bounded affine permutation of a matrix.
descents_composition_list()	Return a list of all the permutations in a given descent class (i. e., having a given descents composition).
descents_composition_first()	Return the smallest element of a descent class.
descents_composition_last()	Return the largest element of a descent class.
bruhat_lequal()	Return True if p1 is less or equal to p2 in the Bruhat order.
permutohedron_lequal()	Return True if p1 is less or equal to p2 in the permutohedron order.
to_standard()	Return a standard permutation corresponding to the permutation self.

AUTHORS:

• Mike Hansen

• Dan Drake (2008-04-07): allow Permutation() to take lists of tuples

• Sébastien Labbé (2009-03-17): added robinson_schensted_inverse

• Travis Scrimshaw:

  • (2012-08-16): to_standard() no longer modifies input

  • (2013-01-19): Removed RSK implementation and moved to rsk.

  • (2013-07-13): Removed CombinatorialClass and moved permutations to the category framework.

• Darij Grinberg (2013-09-07): added methods; ameliorated Issue #14885 by exposing and documenting methods for global-independent multiplication.

• Travis Scrimshaw (2014-02-05): Made StandardPermutations_n a finite Weyl group to make it more uniform with SymmetricGroup. Added ability to compute the conjugacy classes.

• Trevor K. Karn (2022-08-05): Add Permutation.n_reduced_words()

• Amrutha P, Shriya M, Divya Aggarwal (2022-08-16): Added Multimajor Index.

Classes and methods

class sage.combinat.permutation.Arrangements

Bases: Permutations

An arrangement of a multiset mset is an ordered selection without repetitions. It is represented by a list that contains only elements from mset, but maybe in a different order.

Arrangements returns the combinatorial class of arrangements of the multiset mset that contain k elements.

EXAMPLES:

Sage

sage: mset = [1,1,2,3,4,4,5]
sage: Arrangements(mset, 2).list()                                              # needs sage.libs.gap
[[1, 1],
 [1, 2],
 [1, 3],
 [1, 4],
 [1, 5],
 [2, 1],
 [2, 3],
 [2, 4],
 [2, 5],
 [3, 1],
 [3, 2],
 [3, 4],
 [3, 5],
 [4, 1],
 [4, 2],
 [4, 3],
 [4, 4],
 [4, 5],
 [5, 1],
 [5, 2],
 [5, 3],
 [5, 4]]
 sage: Arrangements(mset, 2).cardinality()                                      # needs sage.libs.gap
 22
 sage: Arrangements( ["c","a","t"], 2 ).list()
 [['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
 sage: Arrangements( ["c","a","t"], 3 ).list()
 [['c', 'a', 't'],
  ['c', 't', 'a'],
  ['a', 'c', 't'],
  ['a', 't', 'c'],
  ['t', 'c', 'a'],
  ['t', 'a', 'c']]

Python

>>> from sage.all import *
>>> mset = [Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(4),Integer(5)]
>>> Arrangements(mset, Integer(2)).list()                                              # needs sage.libs.gap
[[1, 1],
 [1, 2],
 [1, 3],
 [1, 4],
 [1, 5],
 [2, 1],
 [2, 3],
 [2, 4],
 [2, 5],
 [3, 1],
 [3, 2],
 [3, 4],
 [3, 5],
 [4, 1],
 [4, 2],
 [4, 3],
 [4, 4],
 [4, 5],
 [5, 1],
 [5, 2],
 [5, 3],
 [5, 4]]
>>> Arrangements(mset, Integer(2)).cardinality()                                      # needs sage.libs.gap
 22
>>> Arrangements( ["c","a","t"], Integer(2) ).list()
 [['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
>>> Arrangements( ["c","a","t"], Integer(3) ).list()
 [['c', 'a', 't'],
  ['c', 't', 'a'],
  ['a', 'c', 't'],
  ['a', 't', 'c'],
  ['t', 'c', 'a'],
  ['t', 'a', 'c']]

cardinality()

Return the cardinality of self.

EXAMPLES:

Sage

sage: A = Arrangements([1,1,2,3,4,4,5], 2)
sage: A.cardinality()                                                       # needs sage.libs.gap
22

Python

>>> from sage.all import *
>>> A = Arrangements([Integer(1),Integer(1),Integer(2),Integer(3),Integer(4),Integer(4),Integer(5)], Integer(2))
>>> A.cardinality()                                                       # needs sage.libs.gap
22

class sage.combinat.permutation.Arrangements_msetk(mset, k)

Bases: Arrangements, Permutations_msetk

Arrangements of length \(k\) of a multiset \(M\).

class sage.combinat.permutation.Arrangements_setk(s, k)

Bases: Arrangements, Permutations_setk

Arrangements of length \(k\) of a set \(S\).

class sage.combinat.permutation.CyclicPermutations(mset)

Bases: Permutations_mset

Return the class of all cyclic permutations of mset in cycle notation. These are the same as necklaces.

INPUT:

• mset – a multiset

EXAMPLES:

Sage

sage: CyclicPermutations(range(4)).list()                                       # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
sage: CyclicPermutations([1,1,1]).list()                                        # needs sage.combinat
[[1, 1, 1]]

Python

>>> from sage.all import *
>>> CyclicPermutations(range(Integer(4))).list()                                       # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
>>> CyclicPermutations([Integer(1),Integer(1),Integer(1)]).list()                                        # needs sage.combinat
[[1, 1, 1]]

iterator(distinct=False)

EXAMPLES:

Sage

sage: CyclicPermutations(range(4)).list()  # indirect doctest               # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
 sage: CyclicPermutations([1,1,1]).list()                                   # needs sage.combinat
 [[1, 1, 1]]
 sage: CyclicPermutations([1,1,1]).list(distinct=True)                      # needs sage.combinat
 [[1, 1, 1], [1, 1, 1]]

Python

>>> from sage.all import *
>>> CyclicPermutations(range(Integer(4))).list()  # indirect doctest               # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
>>> CyclicPermutations([Integer(1),Integer(1),Integer(1)]).list()                                   # needs sage.combinat
 [[1, 1, 1]]
>>> CyclicPermutations([Integer(1),Integer(1),Integer(1)]).list(distinct=True)                      # needs sage.combinat
 [[1, 1, 1], [1, 1, 1]]

list(distinct=False)

EXAMPLES:

Sage

sage: CyclicPermutations(range(4)).list()                                   # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]

Python

>>> from sage.all import *
>>> CyclicPermutations(range(Integer(4))).list()                                   # needs sage.combinat
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]

class sage.combinat.permutation.CyclicPermutationsOfPartition(partition)

Bases: Permutations

Combinations of cyclic permutations of each cell of a given partition.

This is the same as a Cartesian product of necklaces.

EXAMPLES:

Sage

sage: CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]).list()                 # needs sage.combinat
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3),Integer(4)],[Integer(5),Integer(6),Integer(7)]]).list()                 # needs sage.combinat
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3,4],[4,4,4]]).list()                 # needs sage.combinat
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3),Integer(4)],[Integer(4),Integer(4),Integer(4)]]).list()                 # needs sage.combinat
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()                   # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list()                   # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)      # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list(distinct=True)      # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

class Element

Bases: ClonableArray

A cyclic permutation of a partition.

check()

Check that self is a valid element.

EXAMPLES:

Sage

sage: CP = CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]])
sage: elt = CP[0]                                                       # needs sage.combinat
sage: elt.check()                                                       # needs sage.combinat

Python

>>> from sage.all import *
>>> CP = CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3),Integer(4)],[Integer(5),Integer(6),Integer(7)]])
>>> elt = CP[Integer(0)]                                                       # needs sage.combinat
>>> elt.check()                                                       # needs sage.combinat

iterator(distinct=False)

AUTHORS:

• Robert Miller

EXAMPLES:

Sage

sage: CyclicPermutationsOfPartition([[1,2,3,4],        # indirect doctest   # needs sage.combinat
....:                                [5,6,7]]).list()
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3),Integer(4)],        # indirect doctest   # needs sage.combinat
...                                [Integer(5),Integer(6),Integer(7)]]).list()
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3,4],[4,4,4]]).list()             # needs sage.combinat
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3),Integer(4)],[Integer(4),Integer(4),Integer(4)]]).list()             # needs sage.combinat
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()               # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list()               # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]

Sage

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)  # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list(distinct=True)  # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

list(distinct=False)

EXAMPLES:

Sage

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()               # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)  # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

Python

>>> from sage.all import *
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list()               # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
>>> CyclicPermutationsOfPartition([[Integer(1),Integer(2),Integer(3)],[Integer(4),Integer(4),Integer(4)]]).list(distinct=True)  # needs sage.combinat
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]

class sage.combinat.permutation.PatternAvoider(parent, patterns)

Bases: GenericBacktracker

EXAMPLES:

Sage

sage: from sage.combinat.permutation import PatternAvoider
sage: P = Permutations(4)
sage: p = PatternAvoider(P, [[1,2,3]])
sage: loads(dumps(p))
<sage.combinat.permutation.PatternAvoider object at 0x...>

Python

>>> from sage.all import *
>>> from sage.combinat.permutation import PatternAvoider
>>> P = Permutations(Integer(4))
>>> p = PatternAvoider(P, [[Integer(1),Integer(2),Integer(3)]])
>>> loads(dumps(p))
<sage.combinat.permutation.PatternAvoider object at 0x...>

class sage.combinat.permutation.Permutation(parent, l, algorithm='lex', sjt=None, check=True)

Bases: CombinatorialElement

A permutation.

Converts l to a permutation on \(\{1, 2, \ldots, n\}\).

INPUT:

• l – can be any one of the following:

  • an instance of Permutation,

  • list of integers, viewed as one-line permutation notation. The construction checks that you give an acceptable entry. To avoid the check, use the check option.

  • string, expressing the permutation in cycle notation.

  • list of tuples of integers, expressing the permutation in cycle notation.

  • a PermutationGroupElement

  • a pair of two standard tableaux of the same shape. This yields the permutation obtained from the pair using the inverse of the Robinson-Schensted algorithm.

• check – boolean (default: True); whether to check that input is correct; slows the function down, but ensures that nothing bad happens

• algorithm – string (default: 'lex'); the algorithm used to generate the permutations. Supported algorithms are:

  • 'lex': lexicographic order generation, this is the default algorithm

  • 'sjt': Steinhaus-Johnson-Trotter algorithm to generate permutations using only transposition of two elements in the list. It is highly recommended to set check=True (default value).

• sjt – SJT (default: None); the SJT object holding the permutation internal state. This should only be specified when initializing with non-identity permutation.

Warning

Since Issue #13742 the input is checked for correctness : it is not accepted unless it actually is a permutation on \(\{1, \ldots, n\}\). It means that some Permutation() objects cannot be created anymore without setting check=False, as there is no certainty that its functions can handle them, and this should be fixed in a much better way ASAP (the functions should be rewritten to handle those cases, and new tests be added).

Warning

There are two possible conventions for multiplying permutations, and the one currently enabled in Sage by default is the one which has \((pq)(i) = q(p(i))\) for any permutations \(p \in S_n\) and \(q \in S_n\) and any \(1 \leq i \leq n\). (This equation looks less strange when the action of permutations on numbers is written from the right: then it takes the form \(i^{pq} = (i^p)^q\), which is an associativity law). There is an alternative convention, which has \((pq)(i) = p(q(i))\) instead. The conventions can be switched at runtime using sage.combinat.permutation.Permutations.options(). It is best for code not to rely on this setting being set to a particular standard, but rather use the methods left_action_product() and right_action_product() for multiplying permutations (these methods don’t depend on the setting). See Issue #14885 for more details.

Note

The bruhat* methods refer to the strong Bruhat order. To use the weak Bruhat order, look under permutohedron*.

EXAMPLES:

Sage

sage: Permutation([2,1])
[2, 1]
sage: Permutation([2, 1, 4, 5, 3])
[2, 1, 4, 5, 3]
sage: Permutation('(1,2)')
[2, 1]
sage: Permutation('(1,2)(3,4,5)')
[2, 1, 4, 5, 3]
sage: Permutation( ((1,2),(3,4,5)) )
[2, 1, 4, 5, 3]
sage: Permutation( [(1,2),(3,4,5)] )
[2, 1, 4, 5, 3]
sage: Permutation( ((1,2)) )
[2, 1]
sage: Permutation( (1,2) )
[2, 1]
sage: Permutation( ((1,2),) )
[2, 1]
sage: Permutation( ((1,),) )
[1]
sage: Permutation( (1,) )
[1]
sage: Permutation( () )
[]
sage: Permutation( ((),) )
[]
sage: p = Permutation((1, 2, 5)); p
[2, 5, 3, 4, 1]
sage: type(p)
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1)])
[2, 1]
>>> Permutation([Integer(2), Integer(1), Integer(4), Integer(5), Integer(3)])
[2, 1, 4, 5, 3]
>>> Permutation('(1,2)')
[2, 1]
>>> Permutation('(1,2)(3,4,5)')
[2, 1, 4, 5, 3]
>>> Permutation( ((Integer(1),Integer(2)),(Integer(3),Integer(4),Integer(5))) )
[2, 1, 4, 5, 3]
>>> Permutation( [(Integer(1),Integer(2)),(Integer(3),Integer(4),Integer(5))] )
[2, 1, 4, 5, 3]
>>> Permutation( ((Integer(1),Integer(2))) )
[2, 1]
>>> Permutation( (Integer(1),Integer(2)) )
[2, 1]
>>> Permutation( ((Integer(1),Integer(2)),) )
[2, 1]
>>> Permutation( ((Integer(1),),) )
[1]
>>> Permutation( (Integer(1),) )
[1]
>>> Permutation( () )
[]
>>> Permutation( ((),) )
[]
>>> p = Permutation((Integer(1), Integer(2), Integer(5))); p
[2, 5, 3, 4, 1]
>>> type(p)
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

Generate permutations using the Steinhaus-Johnson Trotter algorithm. The output is not in lexicographic order:

Sage

sage: p = Permutation([1, 2, 3, 4], algorithm='sjt'); p
[1, 2, 3, 4]
sage: p = p.next(); p
[1, 2, 4, 3]
sage: p = p.next(); p
[1, 4, 2, 3]
sage: p = Permutation([1, 2, 3], algorithm='sjt')
sage: for _ in range(6):
....:     p = p.next()
sage: p
False

sage: Permutation([1, 3, 2, 4], algorithm='sjt')
Traceback (most recent call last):
...
ValueError: no internal state directions were given for non-identity
starting permutation for Steinhaus-Johnson-Trotter algorithm

Python

>>> from sage.all import *
>>> p = Permutation([Integer(1), Integer(2), Integer(3), Integer(4)], algorithm='sjt'); p
[1, 2, 3, 4]
>>> p = p.next(); p
[1, 2, 4, 3]
>>> p = p.next(); p
[1, 4, 2, 3]
>>> p = Permutation([Integer(1), Integer(2), Integer(3)], algorithm='sjt')
>>> for _ in range(Integer(6)):
...     p = p.next()
>>> p
False

>>> Permutation([Integer(1), Integer(3), Integer(2), Integer(4)], algorithm='sjt')
Traceback (most recent call last):
...
ValueError: no internal state directions were given for non-identity
starting permutation for Steinhaus-Johnson-Trotter algorithm

Construction from a string in cycle notation:

Sage

sage: p = Permutation( '(4,5)' ); p
[1, 2, 3, 5, 4]

Python

>>> from sage.all import *
>>> p = Permutation( '(4,5)' ); p
[1, 2, 3, 5, 4]

The size of the permutation is the maximum integer appearing; add a 1-cycle to increase this:

Sage

sage: p2 = Permutation( '(4,5)(10)' ); p2
[1, 2, 3, 5, 4, 6, 7, 8, 9, 10]
sage: len(p); len(p2)
5
10

Python

>>> from sage.all import *
>>> p2 = Permutation( '(4,5)(10)' ); p2
[1, 2, 3, 5, 4, 6, 7, 8, 9, 10]
>>> len(p); len(p2)
5
10

We construct a Permutation from a PermutationGroupElement:

Sage

sage: g = PermutationGroupElement([2,1,3])                                      # needs sage.groups
sage: Permutation(g)                                                            # needs sage.groups
[2, 1, 3]

Python

>>> from sage.all import *
>>> g = PermutationGroupElement([Integer(2),Integer(1),Integer(3)])                                      # needs sage.groups
>>> Permutation(g)                                                            # needs sage.groups
[2, 1, 3]

From a pair of tableaux of the same shape. This uses the inverse of the Robinson-Schensted algorithm:

Sage

sage: # needs sage.combinat
sage: p = [[1, 4, 7], [2, 5], [3], [6]]
sage: q = [[1, 2, 5], [3, 6], [4], [7]]
sage: P = Tableau(p)
sage: Q = Tableau(q)
sage: Permutation( (p, q) )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( [p, q] )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( (P, Q) )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( [P, Q] )
[3, 6, 5, 2, 7, 4, 1]

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> p = [[Integer(1), Integer(4), Integer(7)], [Integer(2), Integer(5)], [Integer(3)], [Integer(6)]]
>>> q = [[Integer(1), Integer(2), Integer(5)], [Integer(3), Integer(6)], [Integer(4)], [Integer(7)]]
>>> P = Tableau(p)
>>> Q = Tableau(q)
>>> Permutation( (p, q) )
[3, 6, 5, 2, 7, 4, 1]
>>> Permutation( [p, q] )
[3, 6, 5, 2, 7, 4, 1]
>>> Permutation( (P, Q) )
[3, 6, 5, 2, 7, 4, 1]
>>> Permutation( [P, Q] )
[3, 6, 5, 2, 7, 4, 1]

RS_partition()

Return the shape of the tableaux obtained by applying the RSK algorithm to self.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).RS_partition()                                 # needs sage.combinat
[2, 1, 1]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).RS_partition()                                 # needs sage.combinat
[2, 1, 1]

absolute_length()

Return the absolute length of self

The absolute length is the length of the shortest expression of the element as a product of reflections.

For permutations in the symmetric groups, the absolute length is the size minus the number of its disjoint cycles.

EXAMPLES:

Sage

sage: Permutation([4,2,3,1]).absolute_length()                              # needs sage.combinat
1

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(2),Integer(3),Integer(1)]).absolute_length()                              # needs sage.combinat
1

action(a)

Return the action of the permutation self on a list a.

The action of a permutation \(p \in S_n\) on an \(n\)-element list \((a_1, a_2, \ldots, a_n)\) is defined to be \((a_{p(1)}, a_{p(2)}, \ldots, a_{p(n)})\).

EXAMPLES:

Sage

sage: p = Permutation([2,1,3])
sage: a = list(range(3))
sage: p.action(a)
[1, 0, 2]
sage: b = [1,2,3,4]
sage: p.action(b)
Traceback (most recent call last):
...
ValueError: len(a) must equal len(self)

sage: q = Permutation([2,3,1])
sage: a = list(range(3))
sage: q.action(a)
[1, 2, 0]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2),Integer(1),Integer(3)])
>>> a = list(range(Integer(3)))
>>> p.action(a)
[1, 0, 2]
>>> b = [Integer(1),Integer(2),Integer(3),Integer(4)]
>>> p.action(b)
Traceback (most recent call last):
...
ValueError: len(a) must equal len(self)

>>> q = Permutation([Integer(2),Integer(3),Integer(1)])
>>> a = list(range(Integer(3)))
>>> q.action(a)
[1, 2, 0]

avoids(patt)

Test whether the permutation self avoids the pattern patt.

EXAMPLES:

Sage

sage: Permutation([6,2,5,4,3,1]).avoids([4,2,3,1])                          # needs sage.combinat
False
sage: Permutation([6,1,2,5,4,3]).avoids([4,2,3,1])                          # needs sage.combinat
True
sage: Permutation([6,1,2,5,4,3]).avoids([3,4,1,2])                          # needs sage.combinat
True

Python

>>> from sage.all import *
>>> Permutation([Integer(6),Integer(2),Integer(5),Integer(4),Integer(3),Integer(1)]).avoids([Integer(4),Integer(2),Integer(3),Integer(1)])                          # needs sage.combinat
False
>>> Permutation([Integer(6),Integer(1),Integer(2),Integer(5),Integer(4),Integer(3)]).avoids([Integer(4),Integer(2),Integer(3),Integer(1)])                          # needs sage.combinat
True
>>> Permutation([Integer(6),Integer(1),Integer(2),Integer(5),Integer(4),Integer(3)]).avoids([Integer(3),Integer(4),Integer(1),Integer(2)])                          # needs sage.combinat
True

binary_search_tree(left_to_right=True)

Return the binary search tree associated to self.

If \(w\) is a word, then the binary search tree associated to \(w\) is defined as the result of starting with an empty binary tree, and then inserting the letters of \(w\) one by one into this tree. Here, the insertion is being done according to the method binary_search_insert(), and the word \(w\) is being traversed from left to right.

A permutation is regarded as a word (using one-line notation), and thus a binary search tree associated to a permutation is defined.

If the optional keyword variable left_to_right is set to False, the word \(w\) is being traversed from right to left instead.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).binary_search_tree()                           # needs sage.graphs
1[., 4[3[2[., .], .], .]]
sage: Permutation([4,1,3,2]).binary_search_tree()                           # needs sage.graphs
4[1[., 3[2[., .], .]], .]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).binary_search_tree()                           # needs sage.graphs
1[., 4[3[2[., .], .], .]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).binary_search_tree()                           # needs sage.graphs
4[1[., 3[2[., .], .]], .]

By passing the option left_to_right=False one can have the insertion going from right to left:

Sage

sage: Permutation([1,4,3,2]).binary_search_tree(False)                      # needs sage.graphs
2[1[., .], 3[., 4[., .]]]
sage: Permutation([4,1,3,2]).binary_search_tree(False)                      # needs sage.graphs
2[1[., .], 3[., 4[., .]]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).binary_search_tree(False)                      # needs sage.graphs
2[1[., .], 3[., 4[., .]]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).binary_search_tree(False)                      # needs sage.graphs
2[1[., .], 3[., 4[., .]]]

binary_search_tree_shape(left_to_right=True)

Return the shape of the binary search tree of the permutation (a non labelled binary tree).

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).binary_search_tree_shape()                     # needs sage.graphs
[., [[[., .], .], .]]
sage: Permutation([4,1,3,2]).binary_search_tree_shape()                     # needs sage.graphs
[[., [[., .], .]], .]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).binary_search_tree_shape()                     # needs sage.graphs
[., [[[., .], .], .]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).binary_search_tree_shape()                     # needs sage.graphs
[[., [[., .], .]], .]

By passing the option left_to_right=False one can have the insertion going from right to left:

Sage

sage: Permutation([1,4,3,2]).binary_search_tree_shape(False)                # needs sage.graphs
[[., .], [., [., .]]]
sage: Permutation([4,1,3,2]).binary_search_tree_shape(False)                # needs sage.graphs
[[., .], [., [., .]]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).binary_search_tree_shape(False)                # needs sage.graphs
[[., .], [., [., .]]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).binary_search_tree_shape(False)                # needs sage.graphs
[[., .], [., [., .]]]

bruhat_greater()

Return the combinatorial class of permutations greater than or equal to self in the Bruhat order (on the symmetric group containing self).

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: Permutation([4,1,2,3]).bruhat_greater().list()
[[4, 1, 2, 3],
 [4, 1, 3, 2],
 [4, 2, 1, 3],
 [4, 2, 3, 1],
 [4, 3, 1, 2],
 [4, 3, 2, 1]]

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3)]).bruhat_greater().list()
[[4, 1, 2, 3],
 [4, 1, 3, 2],
 [4, 2, 1, 3],
 [4, 2, 3, 1],
 [4, 3, 1, 2],
 [4, 3, 2, 1]]

bruhat_inversions()

Return the list of inversions of self such that the application of this inversion to self decreases its number of inversions by exactly 1.

Equivalently, it returns the list of pairs \((i,j)\) such that \(i < j\), such that \(p(i) > p(j)\) and such that there exists no \(k\) (strictly) between \(i\) and \(j\) satisfying \(p(i) > p(k) > p(j)\).

EXAMPLES:

Sage

sage: Permutation([5,2,3,4,1]).bruhat_inversions()
[[0, 1], [0, 2], [0, 3], [1, 4], [2, 4], [3, 4]]
sage: Permutation([6,1,4,5,2,3]).bruhat_inversions()
[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 4], [3, 5]]

Python

>>> from sage.all import *
>>> Permutation([Integer(5),Integer(2),Integer(3),Integer(4),Integer(1)]).bruhat_inversions()
[[0, 1], [0, 2], [0, 3], [1, 4], [2, 4], [3, 4]]
>>> Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_inversions()
[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 4], [3, 5]]

bruhat_inversions_iterator()

Return the iterator for the inversions of self such that the application of this inversion to self decreases its number of inversions by exactly 1.

EXAMPLES:

Sage

sage: list(Permutation([5,2,3,4,1]).bruhat_inversions_iterator())
[[0, 1], [0, 2], [0, 3], [1, 4], [2, 4], [3, 4]]
sage: list(Permutation([6,1,4,5,2,3]).bruhat_inversions_iterator())
[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 4], [3, 5]]

Python

>>> from sage.all import *
>>> list(Permutation([Integer(5),Integer(2),Integer(3),Integer(4),Integer(1)]).bruhat_inversions_iterator())
[[0, 1], [0, 2], [0, 3], [1, 4], [2, 4], [3, 4]]
>>> list(Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_inversions_iterator())
[[0, 1], [0, 2], [0, 3], [2, 4], [2, 5], [3, 4], [3, 5]]

bruhat_lequal(p2)

Return True if self is less or equal to p2 in the Bruhat order.

The Bruhat order (also called strong Bruhat order or Chevalley order) on the symmetric group \(S_n\) is the partial order on \(S_n\) determined by the following condition: If \(p\) is a permutation, and \(i\) and \(j\) are two indices satisfying \(p(i) > p(j)\) and \(i < j\) (that is, \((i, j)\) is an inversion of \(p\) with \(i < j\)), then \(p \circ (i, j)\) (the permutation obtained by first switching \(i\) with \(j\) and then applying \(p\)) is smaller than \(p\) in the Bruhat order.

One can show that a permutation \(p \in S_n\) is less or equal to a permutation \(q \in S_n\) in the Bruhat order if and only if for every \(i \in \{ 0, 1, \cdots , n \}\) and \(j \in \{ 1, 2, \cdots , n \}\), the number of the elements among \(p(1), p(2), \cdots, p(j)\) that are greater than \(i\) is \(\leq\) to the number of the elements among \(q(1), q(2), \cdots, q(j)\) that are greater than \(i\).

This method assumes that self and p2 are permutations of the same integer \(n\).

EXAMPLES:

Sage

sage: Permutation([2,4,3,1]).bruhat_lequal(Permutation([3,4,2,1]))
True

sage: Permutation([2,1,3]).bruhat_lequal(Permutation([2,3,1]))
True
sage: Permutation([2,1,3]).bruhat_lequal(Permutation([3,1,2]))
True
sage: Permutation([2,1,3]).bruhat_lequal(Permutation([1,2,3]))
False
sage: Permutation([1,3,2]).bruhat_lequal(Permutation([2,1,3]))
False
sage: Permutation([1,3,2]).bruhat_lequal(Permutation([2,3,1]))
True
sage: Permutation([2,3,1]).bruhat_lequal(Permutation([1,3,2]))
False
sage: sorted( [len([b for b in Permutations(3) if a.bruhat_lequal(b)])
....:          for a in Permutations(3)] )
[1, 2, 2, 4, 4, 6]

sage: Permutation([]).bruhat_lequal(Permutation([]))
True

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(4),Integer(3),Integer(1)]).bruhat_lequal(Permutation([Integer(3),Integer(4),Integer(2),Integer(1)]))
True

>>> Permutation([Integer(2),Integer(1),Integer(3)]).bruhat_lequal(Permutation([Integer(2),Integer(3),Integer(1)]))
True
>>> Permutation([Integer(2),Integer(1),Integer(3)]).bruhat_lequal(Permutation([Integer(3),Integer(1),Integer(2)]))
True
>>> Permutation([Integer(2),Integer(1),Integer(3)]).bruhat_lequal(Permutation([Integer(1),Integer(2),Integer(3)]))
False
>>> Permutation([Integer(1),Integer(3),Integer(2)]).bruhat_lequal(Permutation([Integer(2),Integer(1),Integer(3)]))
False
>>> Permutation([Integer(1),Integer(3),Integer(2)]).bruhat_lequal(Permutation([Integer(2),Integer(3),Integer(1)]))
True
>>> Permutation([Integer(2),Integer(3),Integer(1)]).bruhat_lequal(Permutation([Integer(1),Integer(3),Integer(2)]))
False
>>> sorted( [len([b for b in Permutations(Integer(3)) if a.bruhat_lequal(b)])
...          for a in Permutations(Integer(3))] )
[1, 2, 2, 4, 4, 6]

>>> Permutation([]).bruhat_lequal(Permutation([]))
True

bruhat_pred()

Return a list of the permutations strictly smaller than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: Permutation([6,1,4,5,2,3]).bruhat_pred()
[[1, 6, 4, 5, 2, 3],
 [4, 1, 6, 5, 2, 3],
 [5, 1, 4, 6, 2, 3],
 [6, 1, 2, 5, 4, 3],
 [6, 1, 3, 5, 2, 4],
 [6, 1, 4, 2, 5, 3],
 [6, 1, 4, 3, 2, 5]]

Python

>>> from sage.all import *
>>> Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_pred()
[[1, 6, 4, 5, 2, 3],
 [4, 1, 6, 5, 2, 3],
 [5, 1, 4, 6, 2, 3],
 [6, 1, 2, 5, 4, 3],
 [6, 1, 3, 5, 2, 4],
 [6, 1, 4, 2, 5, 3],
 [6, 1, 4, 3, 2, 5]]

bruhat_pred_iterator()

An iterator for the permutations strictly smaller than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: [x for x in Permutation([6,1,4,5,2,3]).bruhat_pred_iterator()]
[[1, 6, 4, 5, 2, 3],
 [4, 1, 6, 5, 2, 3],
 [5, 1, 4, 6, 2, 3],
 [6, 1, 2, 5, 4, 3],
 [6, 1, 3, 5, 2, 4],
 [6, 1, 4, 2, 5, 3],
 [6, 1, 4, 3, 2, 5]]

Python

>>> from sage.all import *
>>> [x for x in Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_pred_iterator()]
[[1, 6, 4, 5, 2, 3],
 [4, 1, 6, 5, 2, 3],
 [5, 1, 4, 6, 2, 3],
 [6, 1, 2, 5, 4, 3],
 [6, 1, 3, 5, 2, 4],
 [6, 1, 4, 2, 5, 3],
 [6, 1, 4, 3, 2, 5]]

bruhat_smaller()

Return the combinatorial class of permutations smaller than or equal to self in the Bruhat order (on the symmetric group containing self).

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: Permutation([4,1,2,3]).bruhat_smaller().list()
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 2, 4],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [3, 1, 2, 4],
 [4, 1, 2, 3]]

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3)]).bruhat_smaller().list()
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 3, 2, 4],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [3, 1, 2, 4],
 [4, 1, 2, 3]]

bruhat_succ()

Return a list of the permutations strictly greater than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: Permutation([6,1,4,5,2,3]).bruhat_succ()
[[6, 4, 1, 5, 2, 3],
 [6, 2, 4, 5, 1, 3],
 [6, 1, 5, 4, 2, 3],
 [6, 1, 4, 5, 3, 2]]

Python

>>> from sage.all import *
>>> Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_succ()
[[6, 4, 1, 5, 2, 3],
 [6, 2, 4, 5, 1, 3],
 [6, 1, 5, 4, 2, 3],
 [6, 1, 4, 5, 3, 2]]

bruhat_succ_iterator()

An iterator for the permutations that are strictly greater than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.

See bruhat_lequal() for the definition of the Bruhat order.

EXAMPLES:

Sage

sage: [x for x in Permutation([6,1,4,5,2,3]).bruhat_succ_iterator()]
[[6, 4, 1, 5, 2, 3],
 [6, 2, 4, 5, 1, 3],
 [6, 1, 5, 4, 2, 3],
 [6, 1, 4, 5, 3, 2]]

Python

>>> from sage.all import *
>>> [x for x in Permutation([Integer(6),Integer(1),Integer(4),Integer(5),Integer(2),Integer(3)]).bruhat_succ_iterator()]
[[6, 4, 1, 5, 2, 3],
 [6, 2, 4, 5, 1, 3],
 [6, 1, 5, 4, 2, 3],
 [6, 1, 4, 5, 3, 2]]

complement()

Return the complement of the permutation self.

The complement of a permutation \(w \in S_n\) is defined as the permutation in \(S_n\) sending each \(i\) to \(n + 1 - w(i)\).

EXAMPLES:

Sage

sage: Permutation([1,2,3]).complement()
[3, 2, 1]
sage: Permutation([1, 3, 2]).complement()
[3, 1, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).complement()
[3, 2, 1]
>>> Permutation([Integer(1), Integer(3), Integer(2)]).complement()
[3, 1, 2]

cycle_string(singletons=False)

Return a string of the permutation in cycle notation.

If singletons=True, it includes 1-cycles in the string.

EXAMPLES:

Sage

sage: Permutation([1,2,3]).cycle_string()
'()'
sage: Permutation([2,1,3]).cycle_string()
'(1,2)'
sage: Permutation([2,3,1]).cycle_string()
'(1,2,3)'
sage: Permutation([2,1,3]).cycle_string(singletons=True)
'(1,2)(3)'

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).cycle_string()
'()'
>>> Permutation([Integer(2),Integer(1),Integer(3)]).cycle_string()
'(1,2)'
>>> Permutation([Integer(2),Integer(3),Integer(1)]).cycle_string()
'(1,2,3)'
>>> Permutation([Integer(2),Integer(1),Integer(3)]).cycle_string(singletons=True)
'(1,2)(3)'

cycle_tuples(singletons=True, use_min=True)

Return the permutation self as a list of disjoint cycles.

The cycles are returned in the order of increasing smallest elements, and each cycle is returned as a tuple which starts with its smallest element.

If singletons=False is given, the list does not contain the singleton cycles.

If use_min=False is given, the cycles are returned in the order of increasing largest (not smallest) elements, and each cycle starts with its largest element.

EXAMPLES:

Sage

sage: Permutation([2,1,3,4]).to_cycles()
[(1, 2), (3,), (4,)]
sage: Permutation([2,1,3,4]).to_cycles(singletons=False)
[(1, 2)]
sage: Permutation([2,1,3,4]).to_cycles(use_min=True)
[(1, 2), (3,), (4,)]
sage: Permutation([2,1,3,4]).to_cycles(use_min=False)
[(4,), (3,), (2, 1)]
sage: Permutation([2,1,3,4]).to_cycles(singletons=False, use_min=False)
[(2, 1)]

sage: Permutation([4,1,5,2,6,3]).to_cycles()
[(1, 4, 2), (3, 5, 6)]
sage: Permutation([4,1,5,2,6,3]).to_cycles(use_min=False)
[(6, 3, 5), (4, 2, 1)]

sage: Permutation([6, 4, 5, 2, 3, 1]).to_cycles()
[(1, 6), (2, 4), (3, 5)]
sage: Permutation([6, 4, 5, 2, 3, 1]).to_cycles(use_min=False)
[(6, 1), (5, 3), (4, 2)]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles()
[(1, 2), (3,), (4,)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(singletons=False)
[(1, 2)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(use_min=True)
[(1, 2), (3,), (4,)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(use_min=False)
[(4,), (3,), (2, 1)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(singletons=False, use_min=False)
[(2, 1)]

>>> Permutation([Integer(4),Integer(1),Integer(5),Integer(2),Integer(6),Integer(3)]).to_cycles()
[(1, 4, 2), (3, 5, 6)]
>>> Permutation([Integer(4),Integer(1),Integer(5),Integer(2),Integer(6),Integer(3)]).to_cycles(use_min=False)
[(6, 3, 5), (4, 2, 1)]

>>> Permutation([Integer(6), Integer(4), Integer(5), Integer(2), Integer(3), Integer(1)]).to_cycles()
[(1, 6), (2, 4), (3, 5)]
>>> Permutation([Integer(6), Integer(4), Integer(5), Integer(2), Integer(3), Integer(1)]).to_cycles(use_min=False)
[(6, 1), (5, 3), (4, 2)]

The algorithm is of complexity \(O(n)\) where \(n\) is the size of the given permutation.

cycle_type()

Return a partition of len(self) corresponding to the cycle type of self.

This is a non-increasing sequence of the cycle lengths of self.

EXAMPLES:

Sage

sage: Permutation([3,1,2,4]).cycle_type()                                   # needs sage.combinat
[3, 1]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(1),Integer(2),Integer(4)]).cycle_type()                                   # needs sage.combinat
[3, 1]

decreasing_runs(as_tuple=False)

Decreasing runs of the permutation.

INPUT:

• as_tuple – boolean (default: False); choice of output format

OUTPUT: list of lists or a tuple of tuples

See also

runs()

EXAMPLES:

Sage

sage: s = Permutation([2,8,3,9,6,4,5,1,7])
sage: s.decreasing_runs()
[[2], [8, 3], [9, 6, 4], [5, 1], [7]]
sage: s.decreasing_runs(as_tuple=True)
((2,), (8, 3), (9, 6, 4), (5, 1), (7,))

Python

>>> from sage.all import *
>>> s = Permutation([Integer(2),Integer(8),Integer(3),Integer(9),Integer(6),Integer(4),Integer(5),Integer(1),Integer(7)])
>>> s.decreasing_runs()
[[2], [8, 3], [9, 6, 4], [5, 1], [7]]
>>> s.decreasing_runs(as_tuple=True)
((2,), (8, 3), (9, 6, 4), (5, 1), (7,))

descent_polynomial()

Return the descent polynomial of the permutation self.

The descent polynomial of a permutation \(p\) is the product of all the z[p(i)] where i ranges over the descents of p.

A descent of a permutation p is an integer i such that p(i) > p(i+1).

REFERENCES:

• [GS1984]

EXAMPLES:

Sage

sage: Permutation([2,1,3]).descent_polynomial()
z2
sage: Permutation([4,3,2,1]).descent_polynomial()
z2*z3*z4

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).descent_polynomial()
z2
>>> Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).descent_polynomial()
z2*z3*z4

Todo

This docstring needs to be fixed. This is not defined in [GS1984] (the descent monomial in their (7.23) is different).

descents(final_descent=False, side='right', positive=False, from_zero=False, index_set=None)

Return the list of the descents of self.

A descent of a permutation \(p\) is an integer \(i\) such that \(p(i) > p(i+1)\).

Warning

By default, the descents are returned as elements in the index set, i.e., starting at \(1\). If you want them to start at \(0\), set the keyword from_zero to True.

INPUT:

• final_descent – boolean (default: False); if True, the last position of a non-empty permutation is also considered as a descent

• side – 'right' (default) or 'left'; if 'left', return the descents of the inverse permutation

• positive – boolean (default: False); if True, return the positions that are not descents

• from_zero – boolean (default: False); if True, return the positions starting from \(0\)

• index_set – list (default: [1, ..., n-1] where self is a permutation of n); the index set to check for descents

EXAMPLES:

Sage

sage: Permutation([3,1,2]).descents()
[1]
sage: Permutation([1,4,3,2]).descents()
[2, 3]
sage: Permutation([1,4,3,2]).descents(final_descent=True)
[2, 3, 4]
sage: Permutation([1,4,3,2]).descents(index_set=[1,2])
[2]
sage: Permutation([1,4,3,2]).descents(from_zero=True)
[1, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(1),Integer(2)]).descents()
[1]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).descents()
[2, 3]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).descents(final_descent=True)
[2, 3, 4]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).descents(index_set=[Integer(1),Integer(2)])
[2]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).descents(from_zero=True)
[1, 2]

descents_composition()

Return the descent composition of self.

The descent composition of a permutation \(p \in S_n\) is defined as the composition of \(n\) whose descent set equals the descent set of \(p\). Here, the descent set of \(p\) is defined as the set of all \(i \in \{ 1, 2, \ldots, n-1 \}\) satisfying \(p(i) > p(i+1)\). The descent set of a composition \(c = (i_1, i_2, \ldots, i_k)\) is defined as the set \(\{ i_1, i_1 + i_2, i_1 + i_2 + i_3, \ldots, i_1 + i_2 + \cdots + i_{k-1} \}\).

EXAMPLES:

Sage

sage: Permutation([1,3,2,4]).descents_composition()
[2, 2]
sage: Permutation([4,1,6,7,2,3,8,5]).descents_composition()
[1, 3, 3, 1]
sage: Permutation([]).descents_composition()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4)]).descents_composition()
[2, 2]
>>> Permutation([Integer(4),Integer(1),Integer(6),Integer(7),Integer(2),Integer(3),Integer(8),Integer(5)]).descents_composition()
[1, 3, 3, 1]
>>> Permutation([]).descents_composition()
[]

destandardize(weight, ordered_alphabet=None)

Return destandardization of self with respect to weight and ordered_alphabet.

INPUT:

• weight – list or tuple of nonnegative integers that sum to \(n\) if self is a permutation in \(S_n\)

• ordered_alphabet – (default: None) a list or tuple specifying the ordered alphabet the destandardized word is over

OUTPUT: word over the ordered_alphabet which standardizes to self

Let \(weight = (w_1,w_2,\ldots,w_\ell)\). Then this methods looks for an increasing sequence of \(1,2,\ldots, w_1\) and labels all letters in it by 1, then an increasing sequence of \(w_1+1,w_1+2,\ldots,w_1+w_2\) and labels all these letters by 2, etc.. If an increasing sequence for the specified weight does not exist, an error is returned. The output is a word w over the specified ordered alphabet with evaluation weight such that w.standard_permutation() is self.

EXAMPLES:

Sage

sage: p = Permutation([1,2,5,3,6,4])
sage: p.destandardize([3,1,2])                                              # needs sage.combinat
word: 113132
sage: p = Permutation([2,1,3])
sage: p.destandardize([2,1])
Traceback (most recent call last):
...
ValueError: Standardization with weight [2, 1] is not possible!

Python

>>> from sage.all import *
>>> p = Permutation([Integer(1),Integer(2),Integer(5),Integer(3),Integer(6),Integer(4)])
>>> p.destandardize([Integer(3),Integer(1),Integer(2)])                                              # needs sage.combinat
word: 113132
>>> p = Permutation([Integer(2),Integer(1),Integer(3)])
>>> p.destandardize([Integer(2),Integer(1)])
Traceback (most recent call last):
...
ValueError: Standardization with weight [2, 1] is not possible!

dict()

Return a dictionary corresponding to the permutation.

EXAMPLES:

Sage

sage: p = Permutation([2,1,3])
sage: d = p.dict()
sage: d[1]
2
sage: d[2]
1
sage: d[3]
3

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2),Integer(1),Integer(3)])
>>> d = p.dict()
>>> d[Integer(1)]
2
>>> d[Integer(2)]
1
>>> d[Integer(3)]
3

fixed_points()

Return a list of the fixed points of self.

EXAMPLES:

Sage

sage: Permutation([1,3,2,4]).fixed_points()
[1, 4]
sage: Permutation([1,2,3,4]).fixed_points()
[1, 2, 3, 4]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4)]).fixed_points()
[1, 4]
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4)]).fixed_points()
[1, 2, 3, 4]

foata_bijection()

Return the image of the permutation self under the Foata bijection \(\phi\).

The bijection shows that \(\mathrm{maj}\) (the major index) and \(\mathrm{inv}\) (the number of inversions) are equidistributed: if \(\phi(P) = Q\), then \(\mathrm{maj}(P) = \mathrm{inv}(Q)\).

The Foata bijection \(\phi\) is a bijection on the set of words with no two equal letters. It can be defined by induction on the size of the word: Given a word \(w_1 w_2 \cdots w_n\), start with \(\phi(w_1) = w_1\). At the \(i\)-th step, if \(\phi(w_1 w_2 \cdots w_i) = v_1 v_2 \cdots v_i\), we define \(\phi(w_1 w_2 \cdots w_i w_{i+1})\) by placing \(w_{i+1}\) on the end of the word \(v_1 v_2 \cdots v_i\) and breaking the word up into blocks as follows. If \(w_{i+1} > v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} > v_k\). Otherwise, if \(w_{i+1} < v_i\), place a vertical line to the right of each \(v_k\) for which \(w_{i+1} < v_k\). In either case, place a vertical line at the start of the word as well. Now, within each block between vertical lines, cyclically shift the entries one place to the right.

For instance, to compute \(\phi([1,4,2,5,3])\), the sequence of words is

• \(1\),

• \(|1|4 \to 14\),

• \(|14|2 \to 412\),

• \(|4|1|2|5 \to 4125\),

• \(|4|125|3 \to 45123\).

So \(\phi([1,4,2,5,3]) = [4,5,1,2,3]\).

See section 2 of [FS1978], and the proof of Proposition 1.4.6 in [EnumComb1].

See also

foata_bijection_inverse() for the inverse map.

EXAMPLES:

Sage

sage: Permutation([1,2,4,3]).foata_bijection()
[4, 1, 2, 3]
sage: Permutation([2,5,1,3,4]).foata_bijection()
[2, 1, 3, 5, 4]

sage: P = Permutation([2,5,1,3,4])
sage: P.major_index() == P.foata_bijection().number_of_inversions()
True

sage: all( P.major_index() == P.foata_bijection().number_of_inversions()
....:      for P in Permutations(4) )
True

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(4),Integer(3)]).foata_bijection()
[4, 1, 2, 3]
>>> Permutation([Integer(2),Integer(5),Integer(1),Integer(3),Integer(4)]).foata_bijection()
[2, 1, 3, 5, 4]

>>> P = Permutation([Integer(2),Integer(5),Integer(1),Integer(3),Integer(4)])
>>> P.major_index() == P.foata_bijection().number_of_inversions()
True

>>> all( P.major_index() == P.foata_bijection().number_of_inversions()
...      for P in Permutations(Integer(4)) )
True

The example from [FS1978]:

Sage

sage: Permutation([7,4,9,2,6,1,5,8,3]).foata_bijection()
[4, 7, 2, 6, 1, 9, 5, 8, 3]

Python

>>> from sage.all import *
>>> Permutation([Integer(7),Integer(4),Integer(9),Integer(2),Integer(6),Integer(1),Integer(5),Integer(8),Integer(3)]).foata_bijection()
[4, 7, 2, 6, 1, 9, 5, 8, 3]

Border cases:

Sage

sage: Permutation([]).foata_bijection()
[]
sage: Permutation([1]).foata_bijection()
[1]

Python

>>> from sage.all import *
>>> Permutation([]).foata_bijection()
[]
>>> Permutation([Integer(1)]).foata_bijection()
[1]

foata_bijection_inverse()

Return the image of the permutation self under the inverse of the Foata bijection \(\phi\).

See foata_bijection() for the definition of the Foata bijection.

EXAMPLES:

Sage

sage: Permutation([4, 1, 2, 3]).foata_bijection()
[1, 2, 4, 3]

Python

>>> from sage.all import *
>>> Permutation([Integer(4), Integer(1), Integer(2), Integer(3)]).foata_bijection()
[1, 2, 4, 3]

forget_cycles()

Return the image of self under the map which forgets cycles.

Consider a permutation \(\sigma\) written in standard cyclic form:

\[\sigma = (a_{1,1}, \ldots, a_{1,k_1}) (a_{2,1}, \ldots, a_{2,k_2}) \cdots (a_{m,1}, \ldots, a_{m,k_m}),\]

where \(a_{1,1} < a_{2,1} < \cdots < a_{m,1}\) and \(a_{j,1} < a_{j,i}\) for all \(1 \leq j \leq m\) and \(2 \leq i \leq k_j\) where we include cycles of length 1 as well. The image of the forget cycle map \(\phi\) is given by

\[\phi(\sigma) = [a_{1,1}, \ldots, a_{1,k_1}, a_{2,1}, \ldots, a_{2,k_2}, \ldots, a_{m,1}, \ldots, a_{m,k_m}],\]

considered as a permutation in 1-line notation.

See also

fundamental_transformation(), which is a similar map that is defined by instead taking \(a_{j,1} > a_{j,i}\) and is bijective.

EXAMPLES:

Sage

sage: P = Permutations(5)
sage: x = P([1, 5, 3, 4, 2])
sage: x.forget_cycles()
[1, 2, 5, 3, 4]

Python

>>> from sage.all import *
>>> P = Permutations(Integer(5))
>>> x = P([Integer(1), Integer(5), Integer(3), Integer(4), Integer(2)])
>>> x.forget_cycles()
[1, 2, 5, 3, 4]

We select all permutations with a cycle composition of \([2, 3, 1]\) in \(S_6\):

Sage

sage: P = Permutations(6)
sage: l = [p for p in P if [len(t) for t in p.to_cycles()] == [1,3,2]]

Python

>>> from sage.all import *
>>> P = Permutations(Integer(6))
>>> l = [p for p in P if [len(t) for t in p.to_cycles()] == [Integer(1),Integer(3),Integer(2)]]

Next we apply \(\phi\) and then take the inverse, and then view the results as a poset under the Bruhat order:

Sage

sage: l = [p.forget_cycles().inverse() for p in l]
sage: B = Poset([l, lambda x,y: x.bruhat_lequal(y)])                        # needs sage.combinat sage.graphs
sage: R.<q> = QQ[]
sage: sum(q^B.rank_function()(x) for x in B)                                # needs sage.combinat sage.graphs
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1

Python

>>> from sage.all import *
>>> l = [p.forget_cycles().inverse() for p in l]
>>> B = Poset([l, lambda x,y: x.bruhat_lequal(y)])                        # needs sage.combinat sage.graphs
>>> R = QQ['q']; (q,) = R._first_ngens(1)
>>> sum(q**B.rank_function()(x) for x in B)                                # needs sage.combinat sage.graphs
q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1

We check the statement in [CC2013] that the posets \(C_{[1,3,1,1]}\) and \(C_{[1,3,2]}\) are isomorphic:

Sage

sage: l2 = [p for p in P if [len(t) for t in p.to_cycles()] == [1,3,1,1]]
sage: l2 = [p.forget_cycles().inverse() for p in l2]
sage: B2 = Poset([l2, lambda x,y: x.bruhat_lequal(y)])                      # needs sage.combinat sage.graphs
sage: B.is_isomorphic(B2)                                                   # needs sage.combinat sage.graphs
True

Python

>>> from sage.all import *
>>> l2 = [p for p in P if [len(t) for t in p.to_cycles()] == [Integer(1),Integer(3),Integer(1),Integer(1)]]
>>> l2 = [p.forget_cycles().inverse() for p in l2]
>>> B2 = Poset([l2, lambda x,y: x.bruhat_lequal(y)])                      # needs sage.combinat sage.graphs
>>> B.is_isomorphic(B2)                                                   # needs sage.combinat sage.graphs
True

See also

fundamental_transformation().

fundamental_transformation()

Return the image of the permutation self under the Renyi-Foata-Schuetzenberger fundamental transformation.

The fundamental transformation is a bijection from the set of all permutations of \(\{1, 2, \ldots, n\}\) to itself, which transforms any such permutation \(w\) as follows: Write \(w\) in cycle form, with each cycle starting with its highest element, and the cycles being sorted in increasing order of their highest elements. Drop the parentheses in the resulting expression, thus reading it as a one-line notation of a new permutation \(u\). Then, \(u\) is the image of \(w\) under the fundamental transformation.

See [EnumComb1], Proposition 1.3.1.

See also

fundamental_transformation_inverse() for the inverse map.

forget_cycles() for a similar (but non-bijective) map where each cycle is starting from its lowest element.

EXAMPLES:

Sage

sage: Permutation([5, 1, 3, 4, 2]).fundamental_transformation()
[3, 4, 5, 2, 1]
sage: Permutations(5)([1, 5, 3, 4, 2]).fundamental_transformation()
[1, 3, 4, 5, 2]
sage: Permutation([8, 4, 7, 2, 9, 6, 5, 1, 3]).fundamental_transformation()
[4, 2, 6, 8, 1, 9, 3, 7, 5]

Python

>>> from sage.all import *
>>> Permutation([Integer(5), Integer(1), Integer(3), Integer(4), Integer(2)]).fundamental_transformation()
[3, 4, 5, 2, 1]
>>> Permutations(Integer(5))([Integer(1), Integer(5), Integer(3), Integer(4), Integer(2)]).fundamental_transformation()
[1, 3, 4, 5, 2]
>>> Permutation([Integer(8), Integer(4), Integer(7), Integer(2), Integer(9), Integer(6), Integer(5), Integer(1), Integer(3)]).fundamental_transformation()
[4, 2, 6, 8, 1, 9, 3, 7, 5]

Comparison with forget_cycles():

Sage

sage: P = Permutation([(1,3,4),(2,5)])
sage: P
[3, 5, 4, 1, 2]
sage: P.forget_cycles()
[1, 3, 4, 2, 5]
sage: P.fundamental_transformation()
[4, 1, 3, 5, 2]

Python

>>> from sage.all import *
>>> P = Permutation([(Integer(1),Integer(3),Integer(4)),(Integer(2),Integer(5))])
>>> P
[3, 5, 4, 1, 2]
>>> P.forget_cycles()
[1, 3, 4, 2, 5]
>>> P.fundamental_transformation()
[4, 1, 3, 5, 2]

fundamental_transformation_inverse()

Return the image of the permutation self under the inverse of the Renyi-Foata-Schuetzenberger fundamental transformation.

The inverse of the fundamental transformation is a bijection from the set of all permutations of \(\{1, 2, \ldots, n\}\) to itself, which transforms any such permutation \(w\) as follows: Let \(I = \{ i_1 < i_2 < \cdots < i_k \}\) be the set of all left-to-right maxima of \(w\) (that is, of all indices \(j\) such that \(w(j)\) is bigger than each of \(w(1), w(2), \ldots, w(j-1)\)). The image of \(w\) under the inverse of the fundamental transformation is the permutation \(u\) that sends \(w(i-1)\) to \(w(i)\) for all \(i \notin I\) (notice that this makes sense, since \(1 \in I\) whenever \(n > 0\)), while sending each \(w(i_p - 1)\) (with \(p \geq 2\)) to \(w(i_{p-1})\). Here, we set \(i_{k+1} = n+1\).

See [EnumComb1], Proposition 1.3.1.

See also

fundamental_transformation() for the inverse map.

EXAMPLES:

Sage

sage: Permutation([3, 4, 5, 2, 1]).fundamental_transformation_inverse()
[5, 1, 3, 4, 2]
sage: Permutation([4, 2, 6, 8, 1, 9, 3, 7, 5]).fundamental_transformation_inverse()
[8, 4, 7, 2, 9, 6, 5, 1, 3]

Python

>>> from sage.all import *
>>> Permutation([Integer(3), Integer(4), Integer(5), Integer(2), Integer(1)]).fundamental_transformation_inverse()
[5, 1, 3, 4, 2]
>>> Permutation([Integer(4), Integer(2), Integer(6), Integer(8), Integer(1), Integer(9), Integer(3), Integer(7), Integer(5)]).fundamental_transformation_inverse()
[8, 4, 7, 2, 9, 6, 5, 1, 3]

grade()

Return the size of self.

EXAMPLES:

Sage

sage: Permutation([3,4,1,2,5]).size()
5

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(4),Integer(1),Integer(2),Integer(5)]).size()
5

has_nth_root(n)

Check if self has \(n\)-th roots.

An \(n\)-th root of the permutation \(\sigma\) is a permutation \(\gamma\) such that \(\gamma^n = \sigma\).

Note that the number of \(n\)-th roots only depends on the cycle type of self.

EXAMPLES:

Sage

sage: # needs sage.combinat
sage: sigma = Permutations(5).identity()
sage: sigma.has_nth_root(3)
True
sage: sigma = Permutation('(1, 3)')
sage: sigma.has_nth_root(2)
False

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> sigma = Permutations(Integer(5)).identity()
>>> sigma.has_nth_root(Integer(3))
True
>>> sigma = Permutation('(1, 3)')
>>> sigma.has_nth_root(Integer(2))
False

See also

• nth_roots()

• number_of_nth_roots()

has_pattern(patt)

Test whether the permutation self contains the pattern patt.

EXAMPLES:

Sage

sage: Permutation([3,5,1,4,6,2]).has_pattern([1,3,2])                       # needs sage.combinat
True

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(5),Integer(1),Integer(4),Integer(6),Integer(2)]).has_pattern([Integer(1),Integer(3),Integer(2)])                       # needs sage.combinat
True

hyperoctahedral_double_coset_type()

Return the coset-type of self as a partition.

self must be a permutation of even size \(2n\). The coset-type determines the double class of the permutation, that is its image in \(H_n \backslash S_{2n} / H_n\), where \(H_n\) is the \(n\)-th hyperoctahedral group.

The coset-type is determined as follows. Consider the perfect matching \(\{\{1,2\},\{3,4\},\dots,\{2n-1,2n\}\}\) and its image by self, and draw them simultaneously as edges of a graph whose vertices are labeled by \(1,2,\dots,2n\). The coset-type is the ordered sequence of the semi-lengths of the cycles of this graph (see Chapter VII of [Mac1995] for more details, particularly Section VII.2).

EXAMPLES:

Sage

sage: # needs sage.combinat
sage: p = Permutation([3, 4, 6, 1, 5, 7, 2, 8])
sage: p.hyperoctahedral_double_coset_type()
[3, 1]
sage: all(p.hyperoctahedral_double_coset_type() ==
....:     p.inverse().hyperoctahedral_double_coset_type()
....:     for p in Permutations(4))
True
sage: Permutation([]).hyperoctahedral_double_coset_type()
[]
sage: Permutation([3,1,2]).hyperoctahedral_double_coset_type()
Traceback (most recent call last):
...
ValueError: [3, 1, 2] is a permutation of odd size and has no coset-type

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> p = Permutation([Integer(3), Integer(4), Integer(6), Integer(1), Integer(5), Integer(7), Integer(2), Integer(8)])
>>> p.hyperoctahedral_double_coset_type()
[3, 1]
>>> all(p.hyperoctahedral_double_coset_type() ==
...     p.inverse().hyperoctahedral_double_coset_type()
...     for p in Permutations(Integer(4)))
True
>>> Permutation([]).hyperoctahedral_double_coset_type()
[]
>>> Permutation([Integer(3),Integer(1),Integer(2)]).hyperoctahedral_double_coset_type()
Traceback (most recent call last):
...
ValueError: [3, 1, 2] is a permutation of odd size and has no coset-type

idescents(final_descent=False, from_zero=False)

Return a list of the idescents of self, that is the list of the descents of self’s inverse.

A descent of a permutation p is an integer i such that p(i) > p(i+1).

Warning

By default, the descents are returned as elements in the index set, i.e., starting at \(1\). If you want them to start at \(0\), set the keyword from_zero to True.

INPUT:

• final_descent – boolean (default: False); if True, the last position of a non-empty permutation is also considered as a descent

• from_zero – boolean (default: False); if False, return the positions starting from \(1\)

EXAMPLES:

Sage

sage: Permutation([2,3,1]).idescents()
[1]
sage: Permutation([1,4,3,2]).idescents()
[2, 3]
sage: Permutation([1,4,3,2]).idescents(final_descent=True)
[2, 3, 4]
sage: Permutation([1,4,3,2]).idescents(from_zero=True)
[1, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(1)]).idescents()
[1]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).idescents()
[2, 3]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).idescents(final_descent=True)
[2, 3, 4]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).idescents(from_zero=True)
[1, 2]

idescents_signature(final_descent=False)

Return the list obtained as follows: Each position in self is mapped to \(-1\) if it is an idescent and \(1\) if it is not an idescent.

See idescents() for a definition of idescents.

With the final_descent option, the last position of a non-empty permutation is also considered as a descent.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).idescents()
[2, 3]
sage: Permutation([1,4,3,2]).idescents_signature()
[1, -1, -1, 1]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).idescents()
[2, 3]
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).idescents_signature()
[1, -1, -1, 1]

imajor_index(final_descent=False)

Return the inverse major index of the permutation self, which is the major index of the inverse of self.

The major index of a permutation \(p\) is the sum of the descents of \(p\). Since our permutation indices are 0-based, we need to add the number of descents.

With the final_descent option, the last position of a non-empty permutation is also considered as a descent.

EXAMPLES:

Sage

sage: Permutation([2,1,3]).imajor_index()
1
sage: Permutation([3,4,1,2]).imajor_index()
2
sage: Permutation([4,3,2,1]).imajor_index()
6

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).imajor_index()
1
>>> Permutation([Integer(3),Integer(4),Integer(1),Integer(2)]).imajor_index()
2
>>> Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).imajor_index()
6

increasing_tree(compare=<built-in function min>)

Return the increasing tree associated to self.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).increasing_tree()                              # needs sage.graphs
1[., 2[3[4[., .], .], .]]
sage: Permutation([4,1,3,2]).increasing_tree()                              # needs sage.graphs
1[4[., .], 2[3[., .], .]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).increasing_tree()                              # needs sage.graphs
1[., 2[3[4[., .], .], .]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).increasing_tree()                              # needs sage.graphs
1[4[., .], 2[3[., .], .]]

By passing the option compare=max one can have the decreasing tree instead:

Sage

sage: Permutation([2,3,4,1]).increasing_tree(max)                           # needs sage.graphs
4[3[2[., .], .], 1[., .]]
sage: Permutation([2,3,1,4]).increasing_tree(max)                           # needs sage.graphs
4[3[2[., .], 1[., .]], .]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(4),Integer(1)]).increasing_tree(max)                           # needs sage.graphs
4[3[2[., .], .], 1[., .]]
>>> Permutation([Integer(2),Integer(3),Integer(1),Integer(4)]).increasing_tree(max)                           # needs sage.graphs
4[3[2[., .], 1[., .]], .]

increasing_tree_shape(compare=<built-in function min>)

Return the shape of the increasing tree associated with the permutation.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).increasing_tree_shape()                        # needs sage.graphs
[., [[[., .], .], .]]
sage: Permutation([4,1,3,2]).increasing_tree_shape()                        # needs sage.graphs
[[., .], [[., .], .]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).increasing_tree_shape()                        # needs sage.graphs
[., [[[., .], .], .]]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2)]).increasing_tree_shape()                        # needs sage.graphs
[[., .], [[., .], .]]

By passing the option compare=max one can have the decreasing tree instead:

Sage

sage: Permutation([2,3,4,1]).increasing_tree_shape(max)                     # needs sage.graphs
[[[., .], .], [., .]]
sage: Permutation([2,3,1,4]).increasing_tree_shape(max)                     # needs sage.graphs
[[[., .], [., .]], .]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(4),Integer(1)]).increasing_tree_shape(max)                     # needs sage.graphs
[[[., .], .], [., .]]
>>> Permutation([Integer(2),Integer(3),Integer(1),Integer(4)]).increasing_tree_shape(max)                     # needs sage.graphs
[[[., .], [., .]], .]

inverse()

Return the inverse of self.

EXAMPLES:

Sage

sage: Permutation([3,8,5,10,9,4,6,1,7,2]).inverse()
[8, 10, 1, 6, 3, 7, 9, 2, 5, 4]
sage: Permutation([2, 4, 1, 5, 3]).inverse()
[3, 1, 5, 2, 4]
sage: ~Permutation([2, 4, 1, 5, 3])
[3, 1, 5, 2, 4]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(8),Integer(5),Integer(10),Integer(9),Integer(4),Integer(6),Integer(1),Integer(7),Integer(2)]).inverse()
[8, 10, 1, 6, 3, 7, 9, 2, 5, 4]
>>> Permutation([Integer(2), Integer(4), Integer(1), Integer(5), Integer(3)]).inverse()
[3, 1, 5, 2, 4]
>>> ~Permutation([Integer(2), Integer(4), Integer(1), Integer(5), Integer(3)])
[3, 1, 5, 2, 4]

inversions()

Return a list of the inversions of self.

An inversion of a permutation \(p\) is a pair \((i, j)\) such that \(i < j\) and \(p(i) > p(j)\).

EXAMPLES:

Sage

sage: Permutation([3,2,4,1,5]).inversions()
[(1, 2), (1, 4), (2, 4), (3, 4)]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(2),Integer(4),Integer(1),Integer(5)]).inversions()
[(1, 2), (1, 4), (2, 4), (3, 4)]

is_derangement()

Return whether self is a derangement.

A permutation \(\sigma\) is a derangement if \(\sigma\) has no fixed points.

EXAMPLES:

Sage

sage: P = Permutation([1,4,2,3])
sage: P.is_derangement()
False
sage: P = Permutation([2,3,1])
sage: P.is_derangement()
True

Python

>>> from sage.all import *
>>> P = Permutation([Integer(1),Integer(4),Integer(2),Integer(3)])
>>> P.is_derangement()
False
>>> P = Permutation([Integer(2),Integer(3),Integer(1)])
>>> P.is_derangement()
True

is_even()

Return True if the permutation self is even and False otherwise.

EXAMPLES:

Sage

sage: Permutation([1,2,3]).is_even()
True
sage: Permutation([2,1,3]).is_even()
False

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).is_even()
True
>>> Permutation([Integer(2),Integer(1),Integer(3)]).is_even()
False

is_simple()

Return whether self is simple.

A permutation is simple if it does not send any proper sub-interval to a sub-interval.

For instance, [6,1,3,5,2,4] is not simple because it maps the interval [3,4,5,6] to [2,3,4,5], whereas [2,6,3,5,1,4] is simple.

See OEIS sequence A111111

EXAMPLES:

Sage

sage: g = Permutation([4,2,3,1])
sage: g.is_simple()
False

sage: g = Permutation([6,1,3,5,2,4])
sage: g.is_simple()
False

sage: g = Permutation([2,6,3,5,1,4])
sage: g.is_simple()
True

sage: [len([pi for pi in Permutations(n) if pi.is_simple()])
....:  for n in range(6)]
[1, 1, 2, 0, 2, 6]

Python

>>> from sage.all import *
>>> g = Permutation([Integer(4),Integer(2),Integer(3),Integer(1)])
>>> g.is_simple()
False

>>> g = Permutation([Integer(6),Integer(1),Integer(3),Integer(5),Integer(2),Integer(4)])
>>> g.is_simple()
False

>>> g = Permutation([Integer(2),Integer(6),Integer(3),Integer(5),Integer(1),Integer(4)])
>>> g.is_simple()
True

>>> [len([pi for pi in Permutations(n) if pi.is_simple()])
...  for n in range(Integer(6))]
[1, 1, 2, 0, 2, 6]

ishift(i)

Return the i-shift of self. If an i-shift of self can’t be performed, then self is returned.

An \(i\)-shift can be applied when \(i\) is not inbetween \(i-1\) and \(i+1\). The \(i\)-shift moves \(i\) to the other side, and leaves the relative positions of \(i-1\) and \(i+1\) in place. All other entries of the permutations are also left in place.

EXAMPLES:

Here, \(2\) is to the left of both \(1\) and \(3\). A \(2\)-shift can be applied which moves the \(2\) to the right and leaves \(1\) and \(3\) in their same relative order:

Sage

sage: Permutation([2,1,3]).ishift(2)
[1, 3, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).ishift(Integer(2))
[1, 3, 2]

All entries other than \(i\), \(i-1\) and \(i+1\) are unchanged:

Sage

sage: Permutation([2,4,1,3]).ishift(2)
[1, 4, 3, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(4),Integer(1),Integer(3)]).ishift(Integer(2))
[1, 4, 3, 2]

Since \(2\) is between \(1\) and \(3\) in [1,2,3], a \(2\)-shift cannot be applied to [1,2,3]

Sage

sage: Permutation([1,2,3]).ishift(2)
[1, 2, 3]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).ishift(Integer(2))
[1, 2, 3]

iswitch(i)

Return the i-switch of self. If an i-switch of self can’t be performed, then self is returned.

An \(i\)-switch can be applied when the subsequence of self formed by the entries \(i-1\), \(i\) and \(i+1\) is neither increasing nor decreasing. In this case, this subsequence is reversed (i. e., its leftmost element and its rightmost element switch places), while all other letters of self are kept in place.

EXAMPLES:

Here, \(2\) is to the left of both \(1\) and \(3\). A \(2\)-switch can be applied which moves the \(2\) to the right and switches the relative order between \(1\) and \(3\):

Sage

sage: Permutation([2,1,3]).iswitch(2)
[3, 1, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).iswitch(Integer(2))
[3, 1, 2]

All entries other than \(i-1\), \(i\) and \(i+1\) are unchanged:

Sage

sage: Permutation([2,4,1,3]).iswitch(2)
[3, 4, 1, 2]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(4),Integer(1),Integer(3)]).iswitch(Integer(2))
[3, 4, 1, 2]

Since \(2\) is between \(1\) and \(3\) in [1,2,3], a \(2\)-switch cannot be applied to [1,2,3]

Sage

sage: Permutation([1,2,3]).iswitch(2)
[1, 2, 3]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).iswitch(Integer(2))
[1, 2, 3]

left_action_product(lp)

Return the permutation obtained by composing self with lp in such an order that lp is applied first and self is applied afterwards.

This is usually denoted by either self * lp or lp * self depending on the conventions used by the author. If the value of a permutation \(p \in S_n\) on an integer \(i \in \{ 1, 2, \cdots, n \}\) is denoted by \(p(i)\), then this should be denoted by self * lp in order to have associativity (i.e., in order to have \((p \cdot q)(i) = p(q(i))\) for all \(p\), \(q\) and \(i\)). If, on the other hand, the value of a permutation \(p \in S_n\) on an integer \(i \in \{ 1, 2, \cdots, n \}\) is denoted by \(i^p\), then this should be denoted by lp * self in order to have associativity (i.e., in order to have \(i^{p \cdot q} = (i^p)^q\) for all \(p\), \(q\) and \(i\)).

EXAMPLES:

Sage

sage: p = Permutation([2,1,3])
sage: q = Permutation([3,1,2])
sage: p.left_action_product(q)
[3, 2, 1]
sage: q.left_action_product(p)
[1, 3, 2]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2),Integer(1),Integer(3)])
>>> q = Permutation([Integer(3),Integer(1),Integer(2)])
>>> p.left_action_product(q)
[3, 2, 1]
>>> q.left_action_product(p)
[1, 3, 2]

left_tableau()

Return the left standard tableau after performing the RSK algorithm on self.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).left_tableau()                                 # needs sage.combinat
[[1, 2], [3], [4]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).left_tableau()                                 # needs sage.combinat
[[1, 2], [3], [4]]

length()

Return the Coxeter length of self.

The length of a permutation \(p\) is given by the number of inversions of \(p\).

EXAMPLES:

Sage

sage: Permutation([5, 1, 3, 4, 2]).length()
6

Python

>>> from sage.all import *
>>> Permutation([Integer(5), Integer(1), Integer(3), Integer(4), Integer(2)]).length()
6

longest_increasing_subsequence_length()

Return the length of the longest increasing subsequences of self.

EXAMPLES:

Sage

sage: Permutation([2,3,1,4]).longest_increasing_subsequence_length()
3
sage: all(i.longest_increasing_subsequence_length() == len(RSK(i)[0][0])    # needs sage.combinat
....:     for i in Permutations(5))
True
sage: Permutation([]).longest_increasing_subsequence_length()
0

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(1),Integer(4)]).longest_increasing_subsequence_length()
3
>>> all(i.longest_increasing_subsequence_length() == len(RSK(i)[Integer(0)][Integer(0)])    # needs sage.combinat
...     for i in Permutations(Integer(5)))
True
>>> Permutation([]).longest_increasing_subsequence_length()
0

longest_increasing_subsequences()

Return the list of the longest increasing subsequences of self.

A theorem of Schensted ([Sch1961]) states that an increasing subsequence of length \(i\) ends with the value entered in the \(i\)-th column of the p-tableau. The algorithm records which column of the p-tableau each value of the permutation is entered into, creates a digraph to record all increasing subsequences, and reads the paths from a source to a sink; these are the longest increasing subsequences.

EXAMPLES:

Sage

sage: Permutation([2,3,4,1]).longest_increasing_subsequences()              # needs sage.graphs
[[2, 3, 4]]
sage: Permutation([5, 7, 1, 2, 6, 4, 3]).longest_increasing_subsequences()  # needs sage.graphs
[[1, 2, 6], [1, 2, 4], [1, 2, 3]]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(4),Integer(1)]).longest_increasing_subsequences()              # needs sage.graphs
[[2, 3, 4]]
>>> Permutation([Integer(5), Integer(7), Integer(1), Integer(2), Integer(6), Integer(4), Integer(3)]).longest_increasing_subsequences()  # needs sage.graphs
[[1, 2, 6], [1, 2, 4], [1, 2, 3]]

Note

This algorithm could be made faster using a balanced search tree for each column instead of sorted lists. See discussion on Issue #31451.

longest_increasing_subsequences_number()

Return the number of increasing subsequences of maximal length in self.

The list of longest increasing subsequences of a permutation is given by longest_increasing_subsequences(), and the length of these subsequences is given by longest_increasing_subsequence_length().

The algorithm is similar to longest_increasing_subsequences(). Namely, the longest increasing subsequences are encoded as increasing sequences in a ranked poset from a smallest to a largest element. Their number can be obtained via dynamic programming: for each \(v\) in the poset we compute the number of paths from a smallest element to \(v\).

EXAMPLES:

Sage

sage: sum(p.longest_increasing_subsequences_number()
....:     for p in Permutations(8))
120770

sage: p = Permutations(50).random_element()
sage: (len(p.longest_increasing_subsequences()) ==                          # needs sage.graphs
....:  p.longest_increasing_subsequences_number())
True

Python

>>> from sage.all import *
>>> sum(p.longest_increasing_subsequences_number()
...     for p in Permutations(Integer(8)))
120770

>>> p = Permutations(Integer(50)).random_element()
>>> (len(p.longest_increasing_subsequences()) ==                          # needs sage.graphs
...  p.longest_increasing_subsequences_number())
True

major_index(final_descent=False)

Return the major index of self.

The major index of a permutation \(p\) is the sum of the descents of \(p\). Since our permutation indices are 0-based, we need to add the number of descents.

With the final_descent option, the last position of a non-empty permutation is also considered as a descent.

EXAMPLES:

Sage

sage: Permutation([2,1,3]).major_index()
1
sage: Permutation([3,4,1,2]).major_index()
2
sage: Permutation([4,3,2,1]).major_index()
6

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).major_index()
1
>>> Permutation([Integer(3),Integer(4),Integer(1),Integer(2)]).major_index()
2
>>> Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).major_index()
6

multi_major_index(composition)

Return the multimajor index of this permutation with respect to composition.

INPUT:

• composition – a composition of the size() of this permutation

EXAMPLES:

Sage

sage: p = Permutation([5, 6, 2, 1, 3, 7, 4])
sage: p.multi_major_index([3, 2, 2])
[2, 0, 1]
sage: p.multi_major_index([7]) == [p.major_index()]
True
sage: p.multi_major_index([1]*7)
[0, 0, 0, 0, 0, 0, 0]
sage: Permutation([]).multi_major_index([])
[]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(5), Integer(6), Integer(2), Integer(1), Integer(3), Integer(7), Integer(4)])
>>> p.multi_major_index([Integer(3), Integer(2), Integer(2)])
[2, 0, 1]
>>> p.multi_major_index([Integer(7)]) == [p.major_index()]
True
>>> p.multi_major_index([Integer(1)]*Integer(7))
[0, 0, 0, 0, 0, 0, 0]
>>> Permutation([]).multi_major_index([])
[]

REFERENCES:

• [JS2000]

next()

Return the permutation that follows self on the symmetric group containing self. If self is the last permutation, then next returns False. If the algorithm parameter is specified, the permutations will be generated according to it. Supported algorithms are:

• lex: lexicographic order generation, this is the default algorithm.

• sjt: Steinhaus-Johnson-Trotter algorithm to generate permutations using only transposition of two elements in the list. It is highly recommended to set check=True (default value).

EXAMPLES:

Sage

sage: p = Permutation([1, 3, 2])
sage: next(p)
[2, 1, 3]
sage: p = Permutation([4,3,2,1])
sage: next(p)
False
sage: p = Permutation([1, 2, 3], algorithm='sjt')
sage: p = next(p); p
[1, 3, 2]
sage: p = next(p); p
[3, 1, 2]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(1), Integer(3), Integer(2)])
>>> next(p)
[2, 1, 3]
>>> p = Permutation([Integer(4),Integer(3),Integer(2),Integer(1)])
>>> next(p)
False
>>> p = Permutation([Integer(1), Integer(2), Integer(3)], algorithm='sjt')
>>> p = next(p); p
[1, 3, 2]
>>> p = next(p); p
[3, 1, 2]

noninversions(k)

Return the list of all k-noninversions in self.

If \(k\) is an integer and \(p \in S_n\) is a permutation, then a \(k\)-noninversion in \(p\) is defined as a strictly increasing sequence \((i_1, i_2, \ldots, i_k)\) of elements of \(\{ 1, 2, \ldots, n \}\) satisfying \(p(i_1) < p(i_2) < \cdots < p(i_k)\). (In other words, a \(k\)-noninversion in \(p\) can be regarded as a \(k\)-element subset of \(\{ 1, 2, \ldots, n \}\) on which \(p\) restricts to an increasing map.)

EXAMPLES:

Sage

sage: p = Permutation([3, 2, 4, 1, 5])
sage: p.noninversions(1)
[[3], [2], [4], [1], [5]]
sage: p.noninversions(2)
[[3, 4], [3, 5], [2, 4], [2, 5], [4, 5], [1, 5]]
sage: p.noninversions(3)
[[3, 4, 5], [2, 4, 5]]
sage: p.noninversions(4)
[]
sage: p.noninversions(5)
[]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3), Integer(2), Integer(4), Integer(1), Integer(5)])
>>> p.noninversions(Integer(1))
[[3], [2], [4], [1], [5]]
>>> p.noninversions(Integer(2))
[[3, 4], [3, 5], [2, 4], [2, 5], [4, 5], [1, 5]]
>>> p.noninversions(Integer(3))
[[3, 4, 5], [2, 4, 5]]
>>> p.noninversions(Integer(4))
[]
>>> p.noninversions(Integer(5))
[]

nth_roots(n)

Return all \(n\)-th roots of self (as a generator).

An \(n\)-th root of the permutation \(\sigma\) is a permutation \(\gamma\) such that \(\gamma^n = \sigma\).

Note that the number of \(n\)-th roots only depends on the cycle type of self.

EXAMPLES:

Sage

sage: # needs sage.combinat
sage: sigma = Permutations(5).identity()
sage: list(sigma.nth_roots(3))
[[1, 4, 3, 5, 2], [1, 5, 3, 2, 4], [1, 2, 4, 5, 3], [1, 2, 5, 3, 4],
 [4, 2, 3, 5, 1], [5, 2, 3, 1, 4], [3, 2, 5, 4, 1], [5, 2, 1, 4, 3],
 [2, 5, 3, 4, 1], [5, 1, 3, 4, 2], [2, 3, 1, 4, 5], [3, 1, 2, 4, 5],
 [2, 4, 3, 1, 5], [4, 1, 3, 2, 5], [3, 2, 4, 1, 5], [4, 2, 1, 3, 5],
 [1, 3, 4, 2, 5], [1, 4, 2, 3, 5], [1, 3, 5, 4, 2], [1, 5, 2, 4, 3],
 [1, 2, 3, 4, 5]]
sage: sigma = Permutation('(1, 3)')
sage: list(sigma.nth_roots(2))
[]

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> sigma = Permutations(Integer(5)).identity()
>>> list(sigma.nth_roots(Integer(3)))
[[1, 4, 3, 5, 2], [1, 5, 3, 2, 4], [1, 2, 4, 5, 3], [1, 2, 5, 3, 4],
 [4, 2, 3, 5, 1], [5, 2, 3, 1, 4], [3, 2, 5, 4, 1], [5, 2, 1, 4, 3],
 [2, 5, 3, 4, 1], [5, 1, 3, 4, 2], [2, 3, 1, 4, 5], [3, 1, 2, 4, 5],
 [2, 4, 3, 1, 5], [4, 1, 3, 2, 5], [3, 2, 4, 1, 5], [4, 2, 1, 3, 5],
 [1, 3, 4, 2, 5], [1, 4, 2, 3, 5], [1, 3, 5, 4, 2], [1, 5, 2, 4, 3],
 [1, 2, 3, 4, 5]]
>>> sigma = Permutation('(1, 3)')
>>> list(sigma.nth_roots(Integer(2)))
[]

For \(n \geq 6\), this algorithm begins to be more efficient than naive search (look at all permutations and test their \(n\)-th power).

See also

• has_nth_root()

• number_of_nth_roots()

number_of_descents(final_descent=False)

Return the number of descents of self.

With the final_descent option, the last position of a non-empty permutation is also considered as a descent.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).number_of_descents()
2
sage: Permutation([1,4,3,2]).number_of_descents(final_descent=True)
3

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).number_of_descents()
2
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).number_of_descents(final_descent=True)
3

number_of_fixed_points()

Return the number of fixed points of self.

EXAMPLES:

Sage

sage: Permutation([1,3,2,4]).number_of_fixed_points()
2
sage: Permutation([1,2,3,4]).number_of_fixed_points()
4

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4)]).number_of_fixed_points()
2
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4)]).number_of_fixed_points()
4

number_of_idescents(final_descent=False)

Return the number of idescents of self.

See idescents() for a definition of idescents.

With the final_descent option, the last position of a non-empty permutation is also considered as a descent.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).number_of_idescents()
2
sage: Permutation([1,4,3,2]).number_of_idescents(final_descent=True)
3

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).number_of_idescents()
2
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).number_of_idescents(final_descent=True)
3

number_of_inversions()

Return the number of inversions in self.

An inversion of a permutation is a pair of elements \((i, j)\) with \(i < j\) and \(p(i) > p(j)\).

REFERENCES:

• http://mathworld.wolfram.com/PermutationInversion.html

EXAMPLES:

Sage

sage: Permutation([3, 2, 4, 1, 5]).number_of_inversions()
4
sage: Permutation([1, 2, 6, 4, 7, 3, 5]).number_of_inversions()
6

Python

>>> from sage.all import *
>>> Permutation([Integer(3), Integer(2), Integer(4), Integer(1), Integer(5)]).number_of_inversions()
4
>>> Permutation([Integer(1), Integer(2), Integer(6), Integer(4), Integer(7), Integer(3), Integer(5)]).number_of_inversions()
6

number_of_noninversions(k)

Return the number of k-noninversions in self.

If \(k\) is an integer and \(p \in S_n\) is a permutation, then a \(k\)-noninversion in \(p\) is defined as a strictly increasing sequence \((i_1, i_2, \ldots, i_k)\) of elements of \(\{ 1, 2, \ldots, n \}\) satisfying \(p(i_1) < p(i_2) < \cdots < p(i_k)\). (In other words, a \(k\)-noninversion in \(p\) can be regarded as a \(k\)-element subset of \(\{ 1, 2, \ldots, n \}\) on which \(p\) restricts to an increasing map.)

The number of \(k\)-noninversions in \(p\) has been denoted by \(\mathrm{noninv}_k(p)\) in [RSW2011], where conjectures and results regarding this number have been stated.

EXAMPLES:

Sage

sage: p = Permutation([3, 2, 4, 1, 5])
sage: p.number_of_noninversions(1)
5
sage: p.number_of_noninversions(2)
6
sage: p.number_of_noninversions(3)
2
sage: p.number_of_noninversions(4)
0
sage: p.number_of_noninversions(5)
0

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3), Integer(2), Integer(4), Integer(1), Integer(5)])
>>> p.number_of_noninversions(Integer(1))
5
>>> p.number_of_noninversions(Integer(2))
6
>>> p.number_of_noninversions(Integer(3))
2
>>> p.number_of_noninversions(Integer(4))
0
>>> p.number_of_noninversions(Integer(5))
0

The number of \(2\)-noninversions of a permutation \(p \in S_n\) is \(\binom{n}{2}\) minus its number of inversions:

Sage

sage: b = binomial(5, 2)                                                    # needs sage.symbolic
sage: all( x.number_of_noninversions(2) == b - x.number_of_inversions()     # needs sage.symbolic
....:      for x in Permutations(5) )
True

Python

>>> from sage.all import *
>>> b = binomial(Integer(5), Integer(2))                                                    # needs sage.symbolic
>>> all( x.number_of_noninversions(Integer(2)) == b - x.number_of_inversions()     # needs sage.symbolic
...      for x in Permutations(Integer(5)) )
True

We also check some corner cases:

Sage

sage: all( x.number_of_noninversions(1) == 5 for x in Permutations(5) )
True
sage: all( x.number_of_noninversions(0) == 1 for x in Permutations(5) )
True
sage: Permutation([]).number_of_noninversions(1)
0
sage: Permutation([]).number_of_noninversions(0)
1
sage: Permutation([2, 1]).number_of_noninversions(3)
0

Python

>>> from sage.all import *
>>> all( x.number_of_noninversions(Integer(1)) == Integer(5) for x in Permutations(Integer(5)) )
True
>>> all( x.number_of_noninversions(Integer(0)) == Integer(1) for x in Permutations(Integer(5)) )
True
>>> Permutation([]).number_of_noninversions(Integer(1))
0
>>> Permutation([]).number_of_noninversions(Integer(0))
1
>>> Permutation([Integer(2), Integer(1)]).number_of_noninversions(Integer(3))
0

number_of_nth_roots(n)

Return the number of \(n\)-th roots of self.

An \(n\)-th root of the permutation \(\sigma\) is a permutation \(\gamma\) such that \(\gamma^n = \sigma\).

Note that the number of \(n\)-th roots only depends on the cycle type of self.

EXAMPLES:

Sage

sage: # needs sage.combinat
sage: Sigma = Permutations(5).identity()
sage: Sigma.number_of_nth_roots(3)
21
sage: Sigma = Permutation('(1, 3)')
sage: Sigma.number_of_nth_roots(2)
0

Python

>>> from sage.all import *
>>> # needs sage.combinat
>>> Sigma = Permutations(Integer(5)).identity()
>>> Sigma.number_of_nth_roots(Integer(3))
21
>>> Sigma = Permutation('(1, 3)')
>>> Sigma.number_of_nth_roots(Integer(2))
0

See also

• nth_roots()

• has_nth_root()

number_of_peaks()

Return the number of peaks of the permutation self.

A peak of a permutation \(p\) is an integer \(i\) such that \(p(i-1) < p(i)\) and \(p(i) > p(i+1)\).

EXAMPLES:

Sage

sage: Permutation([1,3,2,4,5]).number_of_peaks()
1
sage: Permutation([4,1,3,2,6,5]).number_of_peaks()
2

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4),Integer(5)]).number_of_peaks()
1
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2),Integer(6),Integer(5)]).number_of_peaks()
2

number_of_recoils()

Return the number of recoils of the permutation self.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).number_of_recoils()
2

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).number_of_recoils()
2

number_of_reduced_words()

Return the number of reduced words of self without explicitly computing them all.

EXAMPLES:

Sage

sage: p = Permutation([6,4,2,5,1,8,3,7])
sage: len(p.reduced_words()) == p.number_of_reduced_words()                 # needs sage.combinat
True

Python

>>> from sage.all import *
>>> p = Permutation([Integer(6),Integer(4),Integer(2),Integer(5),Integer(1),Integer(8),Integer(3),Integer(7)])
>>> len(p.reduced_words()) == p.number_of_reduced_words()                 # needs sage.combinat
True

number_of_saliances()

Return the number of saliances of self.

A saliance of a permutation \(p\) is an integer \(i\) such that \(p(i) > p(j)\) for all \(j > i\).

EXAMPLES:

Sage

sage: Permutation([2,3,1,5,4]).number_of_saliances()
2
sage: Permutation([5,4,3,2,1]).number_of_saliances()
5

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(1),Integer(5),Integer(4)]).number_of_saliances()
2
>>> Permutation([Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]).number_of_saliances()
5

order()

Return the order of self.

EXAMPLES:

Sage

sage: sigma = Permutation([3,4,1,2,5])
sage: sigma.order()
2
sage: sigma * sigma
[1, 2, 3, 4, 5]

Python

>>> from sage.all import *
>>> sigma = Permutation([Integer(3),Integer(4),Integer(1),Integer(2),Integer(5)])
>>> sigma.order()
2
>>> sigma * sigma
[1, 2, 3, 4, 5]

pattern_positions(patt)

Return the list of positions where the pattern patt appears in the permutation self.

EXAMPLES:

Sage

sage: Permutation([3,5,1,4,6,2]).pattern_positions([1,3,2])                 # needs sage.combinat
[[0, 1, 3], [2, 3, 5], [2, 4, 5]]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(5),Integer(1),Integer(4),Integer(6),Integer(2)]).pattern_positions([Integer(1),Integer(3),Integer(2)])                 # needs sage.combinat
[[0, 1, 3], [2, 3, 5], [2, 4, 5]]

peaks()

Return a list of the peaks of the permutation self.

A peak of a permutation \(p\) is an integer \(i\) such that \(p(i-1) < p(i)\) and \(p(i) > p(i+1)\).

EXAMPLES:

Sage

sage: Permutation([1,3,2,4,5]).peaks()
[1]
sage: Permutation([4,1,3,2,6,5]).peaks()
[2, 4]
sage: Permutation([]).peaks()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4),Integer(5)]).peaks()
[1]
>>> Permutation([Integer(4),Integer(1),Integer(3),Integer(2),Integer(6),Integer(5)]).peaks()
[2, 4]
>>> Permutation([]).peaks()
[]

permutation_poset()

Return the permutation poset of self.

The permutation poset of a permutation \(p\) is the poset with vertices \((i, p(i))\) for \(i = 1, 2, \ldots, n\) (where \(n\) is the size of \(p\)) and order inherited from \(\ZZ \times \ZZ\).

EXAMPLES:

Sage

sage: # needs sage.combinat sage.graphs
sage: Permutation([3,1,5,4,2]).permutation_poset().cover_relations()
[[(2, 1), (5, 2)],
 [(2, 1), (3, 5)],
 [(2, 1), (4, 4)],
 [(1, 3), (3, 5)],
 [(1, 3), (4, 4)]]
sage: Permutation([]).permutation_poset().cover_relations()
[]
sage: Permutation([1,3,2]).permutation_poset().cover_relations()
[[(1, 1), (2, 3)], [(1, 1), (3, 2)]]
sage: Permutation([1,2]).permutation_poset().cover_relations()
[[(1, 1), (2, 2)]]
sage: P = Permutation([1,5,2,4,3])

Python

>>> from sage.all import *
>>> # needs sage.combinat sage.graphs
>>> Permutation([Integer(3),Integer(1),Integer(5),Integer(4),Integer(2)]).permutation_poset().cover_relations()
[[(2, 1), (5, 2)],
 [(2, 1), (3, 5)],
 [(2, 1), (4, 4)],
 [(1, 3), (3, 5)],
 [(1, 3), (4, 4)]]
>>> Permutation([]).permutation_poset().cover_relations()
[]
>>> Permutation([Integer(1),Integer(3),Integer(2)]).permutation_poset().cover_relations()
[[(1, 1), (2, 3)], [(1, 1), (3, 2)]]
>>> Permutation([Integer(1),Integer(2)]).permutation_poset().cover_relations()
[[(1, 1), (2, 2)]]
>>> P = Permutation([Integer(1),Integer(5),Integer(2),Integer(4),Integer(3)])

This should hold for any \(P\):

Sage

sage: P.permutation_poset().greene_shape() == P.RS_partition()              # needs sage.combinat sage.graphs
True

Python

>>> from sage.all import *
>>> P.permutation_poset().greene_shape() == P.RS_partition()              # needs sage.combinat sage.graphs
True

permutohedron_greater(side='right')

Return a list of permutations greater than or equal to self in the permutohedron order.

By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: Permutation([4,2,1,3]).permutohedron_greater()
[[4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1]]
sage: Permutation([4,2,1,3]).permutohedron_greater(side='left')
[[4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]).permutohedron_greater()
[[4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1]]
>>> Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]).permutohedron_greater(side='left')
[[4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]

permutohedron_join(other, side='right')

Return the join of the permutations self and other in the right permutohedron order (or, if side is set to 'left', in the left permutohedron order).

The permutohedron orders (see permutohedron_lequal()) are lattices; the join operation refers to this lattice structure. In more elementary terms, the join of two permutations \(\pi\) and \(\psi\) in the symmetric group \(S_n\) is the permutation in \(S_n\) whose set of inversion is the transitive closure of the union of the set of inversions of \(\pi\) with the set of inversions of \(\psi\).

See also

permutohedron_lequal(), permutohedron_meet().

ALGORITHM:

It is enough to construct the join of any two permutations \(\pi\) and \(\psi\) in \(S_n\) with respect to the right weak order. (The join of \(\pi\) and \(\psi\) with respect to the left weak order is the inverse of the join of \(\pi^{-1}\) and \(\psi^{-1}\) with respect to the right weak order.) Start with an empty list \(l\) (denoted xs in the actual code). For \(i = 1, 2, \ldots, n\) (in this order), we insert \(i\) into this list in the rightmost possible position such that any letter in \(\{ 1, 2, ..., i-1 \}\) which appears further right than \(i\) in either \(\pi\) or \(\psi\) (or both) must appear further right than \(i\) in the resulting list. After all numbers are inserted, we are left with a list which is precisely the join of \(\pi\) and \(\psi\) (in one-line notation). This algorithm is due to Markowsky, [Mar1994] (Theorem 1 (a)).

AUTHORS:

Viviane Pons and Darij Grinberg, 18 June 2014.

EXAMPLES:

Sage

sage: p = Permutation([3,1,2])
sage: q = Permutation([1,3,2])
sage: p.permutohedron_join(q)
[3, 1, 2]
sage: r = Permutation([2,1,3])
sage: r.permutohedron_join(p)
[3, 2, 1]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(1),Integer(2)])
>>> q = Permutation([Integer(1),Integer(3),Integer(2)])
>>> p.permutohedron_join(q)
[3, 1, 2]
>>> r = Permutation([Integer(2),Integer(1),Integer(3)])
>>> r.permutohedron_join(p)
[3, 2, 1]

Sage

sage: p = Permutation([3,2,4,1])
sage: q = Permutation([4,2,1,3])
sage: p.permutohedron_join(q)
[4, 3, 2, 1]
sage: r = Permutation([3,1,2,4])
sage: p.permutohedron_join(r)
[3, 2, 4, 1]
sage: q.permutohedron_join(r)
[4, 3, 2, 1]
sage: s = Permutation([1,4,2,3])
sage: s.permutohedron_join(r)
[4, 3, 1, 2]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(2),Integer(4),Integer(1)])
>>> q = Permutation([Integer(4),Integer(2),Integer(1),Integer(3)])
>>> p.permutohedron_join(q)
[4, 3, 2, 1]
>>> r = Permutation([Integer(3),Integer(1),Integer(2),Integer(4)])
>>> p.permutohedron_join(r)
[3, 2, 4, 1]
>>> q.permutohedron_join(r)
[4, 3, 2, 1]
>>> s = Permutation([Integer(1),Integer(4),Integer(2),Integer(3)])
>>> s.permutohedron_join(r)
[4, 3, 1, 2]

The universal property of the join operation is satisfied:

Sage

sage: def test_uni_join(p, q):
....:     j = p.permutohedron_join(q)
....:     if not p.permutohedron_lequal(j):
....:         return False
....:     if not q.permutohedron_lequal(j):
....:         return False
....:     for r in p.permutohedron_greater():
....:         if q.permutohedron_lequal(r) and not j.permutohedron_lequal(r):
....:             return False
....:     return True
sage: all( test_uni_join(p, q) for p in Permutations(3) for q in Permutations(3) )
True
sage: test_uni_join(Permutation([6, 4, 7, 3, 2, 5, 8, 1]), Permutation([7, 3, 1, 2, 5, 4, 6, 8]))
True

Python

>>> from sage.all import *
>>> def test_uni_join(p, q):
...     j = p.permutohedron_join(q)
...     if not p.permutohedron_lequal(j):
...         return False
...     if not q.permutohedron_lequal(j):
...         return False
...     for r in p.permutohedron_greater():
...         if q.permutohedron_lequal(r) and not j.permutohedron_lequal(r):
...             return False
...     return True
>>> all( test_uni_join(p, q) for p in Permutations(Integer(3)) for q in Permutations(Integer(3)) )
True
>>> test_uni_join(Permutation([Integer(6), Integer(4), Integer(7), Integer(3), Integer(2), Integer(5), Integer(8), Integer(1)]), Permutation([Integer(7), Integer(3), Integer(1), Integer(2), Integer(5), Integer(4), Integer(6), Integer(8)]))
True

Border cases:

Sage

sage: p = Permutation([])
sage: p.permutohedron_join(p)
[]
sage: p = Permutation([1])
sage: p.permutohedron_join(p)
[1]

Python

>>> from sage.all import *
>>> p = Permutation([])
>>> p.permutohedron_join(p)
[]
>>> p = Permutation([Integer(1)])
>>> p.permutohedron_join(p)
[1]

The left permutohedron:

Sage

sage: p = Permutation([3,1,2])
sage: q = Permutation([1,3,2])
sage: p.permutohedron_join(q, side='left')
[3, 2, 1]
sage: r = Permutation([2,1,3])
sage: r.permutohedron_join(p, side='left')
[3, 1, 2]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(1),Integer(2)])
>>> q = Permutation([Integer(1),Integer(3),Integer(2)])
>>> p.permutohedron_join(q, side='left')
[3, 2, 1]
>>> r = Permutation([Integer(2),Integer(1),Integer(3)])
>>> r.permutohedron_join(p, side='left')
[3, 1, 2]

permutohedron_lequal(p2, side='right')

Return True if self is less or equal to p2 in the permutohedron order.

By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.

For every nonnegative integer \(n\), the right (resp. left) permutohedron order (also called the right (resp. left) weak order, or the right (resp. left) weak Bruhat order) is a partial order on the symmetric group \(S_n\). It can be defined in various ways, including the following ones:

• Two permutations \(u\) and \(v\) in \(S_n\) satisfy \(u \leq v\) in the right (resp. left) permutohedron order if and only if the (Coxeter) length of the permutation \(v^{-1} \circ u\) (resp. of the permutation \(u \circ v^{-1}\)) equals the length of \(v\) minus the length of \(u\). Here, \(p \circ q\) means the permutation obtained by applying \(q\) first and then \(p\). (Recall that the Coxeter length of a permutation is its number of inversions.)

• Two permutations \(u\) and \(v\) in \(S_n\) satisfy \(u \leq v\) in the right (resp. left) permutohedron order if and only if every pair \((i, j)\) of elements of \(\{ 1, 2, \cdots, n \}\) such that \(i < j\) and \(u^{-1}(i) > u^{-1}(j)\) (resp. \(u(i) > u(j)\)) also satisfies \(v^{-1}(i) > v^{-1}(j)\) (resp. \(v(i) > v(j)\)).

• A permutation \(v \in S_n\) covers a permutation \(u \in S_n\) in the right (resp. left) permutohedron order if and only if we have \(v = u \circ (i, i + 1)\) (resp. \(v = (i, i + 1) \circ u\)) for some \(i \in \{ 1, 2, \cdots, n - 1 \}\) satisfying \(u(i) < u(i + 1)\) (resp. \(u^{-1}(i) < u^{-1}(i + 1)\)). Here, again, \(p \circ q\) means the permutation obtained by applying \(q\) first and then \(p\).

The right and the left permutohedron order are mutually isomorphic, with the isomorphism being the map sending every permutation to its inverse. Each of these orders endows the symmetric group \(S_n\) with the structure of a graded poset (the rank function being the Coxeter length).

Warning

The permutohedron order is not to be mistaken for the strong Bruhat order (bruhat_lequal()), despite both orders being occasionally referred to as the Bruhat order.

EXAMPLES:

Sage

sage: p = Permutation([3,2,1,4])
sage: p.permutohedron_lequal(Permutation([4,2,1,3]))
False
sage: p.permutohedron_lequal(Permutation([4,2,1,3]), side='left')
True
sage: p.permutohedron_lequal(p)
True

sage: Permutation([2,1,3]).permutohedron_lequal(Permutation([2,3,1]))
True
sage: Permutation([2,1,3]).permutohedron_lequal(Permutation([3,1,2]))
False
sage: Permutation([2,1,3]).permutohedron_lequal(Permutation([1,2,3]))
False
sage: Permutation([1,3,2]).permutohedron_lequal(Permutation([2,1,3]))
False
sage: Permutation([1,3,2]).permutohedron_lequal(Permutation([2,3,1]))
False
sage: Permutation([2,3,1]).permutohedron_lequal(Permutation([1,3,2]))
False
sage: Permutation([2,1,3]).permutohedron_lequal(Permutation([2,3,1]), side='left')
False
sage: sorted( [len([b for b in Permutations(3) if a.permutohedron_lequal(b)])
....:          for a in Permutations(3)] )
[1, 2, 2, 3, 3, 6]
sage: sorted( [len([b for b in Permutations(3) if a.permutohedron_lequal(b, side='left')])
....:          for a in Permutations(3)] )
[1, 2, 2, 3, 3, 6]

sage: Permutation([]).permutohedron_lequal(Permutation([]))
True

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(2),Integer(1),Integer(4)])
>>> p.permutohedron_lequal(Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]))
False
>>> p.permutohedron_lequal(Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]), side='left')
True
>>> p.permutohedron_lequal(p)
True

>>> Permutation([Integer(2),Integer(1),Integer(3)]).permutohedron_lequal(Permutation([Integer(2),Integer(3),Integer(1)]))
True
>>> Permutation([Integer(2),Integer(1),Integer(3)]).permutohedron_lequal(Permutation([Integer(3),Integer(1),Integer(2)]))
False
>>> Permutation([Integer(2),Integer(1),Integer(3)]).permutohedron_lequal(Permutation([Integer(1),Integer(2),Integer(3)]))
False
>>> Permutation([Integer(1),Integer(3),Integer(2)]).permutohedron_lequal(Permutation([Integer(2),Integer(1),Integer(3)]))
False
>>> Permutation([Integer(1),Integer(3),Integer(2)]).permutohedron_lequal(Permutation([Integer(2),Integer(3),Integer(1)]))
False
>>> Permutation([Integer(2),Integer(3),Integer(1)]).permutohedron_lequal(Permutation([Integer(1),Integer(3),Integer(2)]))
False
>>> Permutation([Integer(2),Integer(1),Integer(3)]).permutohedron_lequal(Permutation([Integer(2),Integer(3),Integer(1)]), side='left')
False
>>> sorted( [len([b for b in Permutations(Integer(3)) if a.permutohedron_lequal(b)])
...          for a in Permutations(Integer(3))] )
[1, 2, 2, 3, 3, 6]
>>> sorted( [len([b for b in Permutations(Integer(3)) if a.permutohedron_lequal(b, side='left')])
...          for a in Permutations(Integer(3))] )
[1, 2, 2, 3, 3, 6]

>>> Permutation([]).permutohedron_lequal(Permutation([]))
True

permutohedron_meet(other, side='right')

Return the meet of the permutations self and other in the right permutohedron order (or, if side is set to 'left', in the left permutohedron order).

The permutohedron orders (see permutohedron_lequal()) are lattices; the meet operation refers to this lattice structure. It is connected to the join operation by the following simple symmetry property: If \(\pi\) and \(\psi\) are two permutations \(\pi\) and \(\psi\) in the symmetric group \(S_n\), and if \(w_0\) denotes the permutation \((n, n-1, \ldots, 1) \in S_n\), then

\[\pi \wedge \psi = w_0 \circ ((w_0 \circ \pi) \vee (w_0 \circ \psi)) = ((\pi \circ w_0) \vee (\psi \circ w_0)) \circ w_0\]

and

\[\pi \vee \psi = w_0 \circ ((w_0 \circ \pi) \wedge (w_0 \circ \psi)) = ((\pi \circ w_0) \wedge (\psi \circ w_0)) \circ w_0,\]

where \(\wedge\) means meet and \(\vee\) means join.

See also

permutohedron_lequal(), permutohedron_join().

AUTHORS:

Viviane Pons and Darij Grinberg, 18 June 2014.

EXAMPLES:

Sage

sage: p = Permutation([3,1,2])
sage: q = Permutation([1,3,2])
sage: p.permutohedron_meet(q)
[1, 3, 2]
sage: r = Permutation([2,1,3])
sage: r.permutohedron_meet(p)
[1, 2, 3]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(1),Integer(2)])
>>> q = Permutation([Integer(1),Integer(3),Integer(2)])
>>> p.permutohedron_meet(q)
[1, 3, 2]
>>> r = Permutation([Integer(2),Integer(1),Integer(3)])
>>> r.permutohedron_meet(p)
[1, 2, 3]

Sage

sage: p = Permutation([3,2,4,1])
sage: q = Permutation([4,2,1,3])
sage: p.permutohedron_meet(q)
[2, 1, 3, 4]
sage: r = Permutation([3,1,2,4])
sage: p.permutohedron_meet(r)
[3, 1, 2, 4]
sage: q.permutohedron_meet(r)
[1, 2, 3, 4]
sage: s = Permutation([1,4,2,3])
sage: s.permutohedron_meet(r)
[1, 2, 3, 4]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(2),Integer(4),Integer(1)])
>>> q = Permutation([Integer(4),Integer(2),Integer(1),Integer(3)])
>>> p.permutohedron_meet(q)
[2, 1, 3, 4]
>>> r = Permutation([Integer(3),Integer(1),Integer(2),Integer(4)])
>>> p.permutohedron_meet(r)
[3, 1, 2, 4]
>>> q.permutohedron_meet(r)
[1, 2, 3, 4]
>>> s = Permutation([Integer(1),Integer(4),Integer(2),Integer(3)])
>>> s.permutohedron_meet(r)
[1, 2, 3, 4]

The universal property of the meet operation is satisfied:

Sage

sage: def test_uni_meet(p, q):
....:     m = p.permutohedron_meet(q)
....:     if not m.permutohedron_lequal(p):
....:         return False
....:     if not m.permutohedron_lequal(q):
....:         return False
....:     for r in p.permutohedron_smaller():
....:         if r.permutohedron_lequal(q) and not r.permutohedron_lequal(m):
....:             return False
....:     return True
sage: all( test_uni_meet(p, q) for p in Permutations(3) for q in Permutations(3) )
True
sage: test_uni_meet(Permutation([6, 4, 7, 3, 2, 5, 8, 1]), Permutation([7, 3, 1, 2, 5, 4, 6, 8]))
True

Python

>>> from sage.all import *
>>> def test_uni_meet(p, q):
...     m = p.permutohedron_meet(q)
...     if not m.permutohedron_lequal(p):
...         return False
...     if not m.permutohedron_lequal(q):
...         return False
...     for r in p.permutohedron_smaller():
...         if r.permutohedron_lequal(q) and not r.permutohedron_lequal(m):
...             return False
...     return True
>>> all( test_uni_meet(p, q) for p in Permutations(Integer(3)) for q in Permutations(Integer(3)) )
True
>>> test_uni_meet(Permutation([Integer(6), Integer(4), Integer(7), Integer(3), Integer(2), Integer(5), Integer(8), Integer(1)]), Permutation([Integer(7), Integer(3), Integer(1), Integer(2), Integer(5), Integer(4), Integer(6), Integer(8)]))
True

Border cases:

Sage

sage: p = Permutation([])
sage: p.permutohedron_meet(p)
[]
sage: p = Permutation([1])
sage: p.permutohedron_meet(p)
[1]

Python

>>> from sage.all import *
>>> p = Permutation([])
>>> p.permutohedron_meet(p)
[]
>>> p = Permutation([Integer(1)])
>>> p.permutohedron_meet(p)
[1]

The left permutohedron:

Sage

sage: p = Permutation([3,1,2])
sage: q = Permutation([1,3,2])
sage: p.permutohedron_meet(q, side='left')
[1, 2, 3]
sage: r = Permutation([2,1,3])
sage: r.permutohedron_meet(p, side='left')
[2, 1, 3]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3),Integer(1),Integer(2)])
>>> q = Permutation([Integer(1),Integer(3),Integer(2)])
>>> p.permutohedron_meet(q, side='left')
[1, 2, 3]
>>> r = Permutation([Integer(2),Integer(1),Integer(3)])
>>> r.permutohedron_meet(p, side='left')
[2, 1, 3]

permutohedron_pred(side='right')

Return a list of the permutations strictly smaller than self in the permutohedron order such that there is no permutation between any of those and self.

By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: p = Permutation([4,2,1,3])
sage: p.permutohedron_pred()
[[2, 4, 1, 3], [4, 1, 2, 3]]
sage: p.permutohedron_pred(side='left')
[[4, 1, 2, 3], [3, 2, 1, 4]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(4),Integer(2),Integer(1),Integer(3)])
>>> p.permutohedron_pred()
[[2, 4, 1, 3], [4, 1, 2, 3]]
>>> p.permutohedron_pred(side='left')
[[4, 1, 2, 3], [3, 2, 1, 4]]

permutohedron_smaller(side='right')

Return a list of permutations smaller than or equal to self in the permutohedron order.

By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: Permutation([4,2,1,3]).permutohedron_smaller()
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [2, 4, 1, 3],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]).permutohedron_smaller()
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [2, 4, 1, 3],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]

Sage

sage: Permutation([4,2,1,3]).permutohedron_smaller(side='left')
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [2, 1, 3, 4],
 [2, 3, 1, 4],
 [3, 1, 2, 4],
 [3, 2, 1, 4],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(2),Integer(1),Integer(3)]).permutohedron_smaller(side='left')
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [2, 1, 3, 4],
 [2, 3, 1, 4],
 [3, 1, 2, 4],
 [3, 2, 1, 4],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]

permutohedron_succ(side='right')

Return a list of the permutations strictly greater than self in the permutohedron order such that there is no permutation between any of those and self.

By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: p = Permutation([4,2,1,3])
sage: p.permutohedron_succ()
[[4, 2, 3, 1]]
sage: p.permutohedron_succ(side='left')
[[4, 3, 1, 2]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(4),Integer(2),Integer(1),Integer(3)])
>>> p.permutohedron_succ()
[[4, 2, 3, 1]]
>>> p.permutohedron_succ(side='left')
[[4, 3, 1, 2]]

prev()

Return the permutation that comes directly before self in lexicographic order on the symmetric group containing self. If self is the first permutation, then it returns False. Does not support the Steinhaus-Johnson-Trotter algorithm for the moment.

EXAMPLES:

Sage

sage: p = Permutation([1,2,3])
sage: p.prev()
False
sage: p = Permutation([1,3,2])
sage: p.prev()
[1, 2, 3]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(1),Integer(2),Integer(3)])
>>> p.prev()
False
>>> p = Permutation([Integer(1),Integer(3),Integer(2)])
>>> p.prev()
[1, 2, 3]

Todo

Implement the previous permutation for the Steinhaus-Johnson-Trotter algorithm.

rank()

Return the rank of self in the lexicographic ordering on the symmetric group to which self belongs.

EXAMPLES:

Sage

sage: Permutation([1,2,3]).rank()
0
sage: Permutation([1, 2, 4, 6, 3, 5]).rank()
10
sage: perms = Permutations(6).list()
sage: [p.rank() for p in perms] == list(range(factorial(6)))
True

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3)]).rank()
0
>>> Permutation([Integer(1), Integer(2), Integer(4), Integer(6), Integer(3), Integer(5)]).rank()
10
>>> perms = Permutations(Integer(6)).list()
>>> [p.rank() for p in perms] == list(range(factorial(Integer(6))))
True

recoils()

Return the list of the positions of the recoils of self.

A recoil of a permutation \(p\) is an integer \(i\) such that \(i+1\) appears to the left of \(i\) in \(p\). Here, the positions are being counted starting at \(0\). (Note that it is the positions, not the recoils themselves, which are being listed.)

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).recoils()
[2, 3]
sage: Permutation([]).recoils()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).recoils()
[2, 3]
>>> Permutation([]).recoils()
[]

recoils_composition()

Return the recoils composition of self.

The recoils composition of a permutation \(p \in S_n\) is the composition of \(n\) whose descent set is the set of the recoils of \(p\) (not their positions). In other words, this is the descents composition of \(p^{-1}\).

EXAMPLES:

Sage

sage: Permutation([1,3,2,4]).recoils_composition()
[2, 2]
sage: Permutation([]).recoils_composition()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4)]).recoils_composition()
[2, 2]
>>> Permutation([]).recoils_composition()
[]

reduced_word()

Return a reduced word of the permutation self.

See reduced_words() for the definition of reduced words and a way to compute them all.

Warning

This does not respect the multiplication convention.

EXAMPLES:

Sage

sage: Permutation([3,5,4,6,2,1]).reduced_word()
[2, 1, 4, 3, 2, 4, 3, 5, 4, 5]

Permutation([1]).reduced_word_lexmin()
[]
Permutation([]).reduced_word_lexmin()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(5),Integer(4),Integer(6),Integer(2),Integer(1)]).reduced_word()
[2, 1, 4, 3, 2, 4, 3, 5, 4, 5]

Permutation([1]).reduced_word_lexmin()
[]
Permutation([]).reduced_word_lexmin()
[]

reduced_word_lexmin()

Return a lexicographically minimal reduced word of the permutation self.

See reduced_words() for the definition of reduced words and a way to compute them all.

EXAMPLES:

Sage

sage: Permutation([3,4,2,1]).reduced_word_lexmin()
[1, 2, 1, 3, 2]

Permutation([1]).reduced_word_lexmin()
[]
Permutation([]).reduced_word_lexmin()
[]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(4),Integer(2),Integer(1)]).reduced_word_lexmin()
[1, 2, 1, 3, 2]

Permutation([1]).reduced_word_lexmin()
[]
Permutation([]).reduced_word_lexmin()
[]

reduced_words()

Return a list of the reduced words of self.

The notion of a reduced word is based on the well-known fact that every permutation can be written as a product of adjacent transpositions. In more detail: If \(n\) is a nonnegative integer, we can define the transpositions \(s_i = (i, i+1) \in S_n\) for all \(i \in \{ 1, 2, \ldots, n-1 \}\), and every \(p \in S_n\) can then be written as a product \(s_{i_1} s_{i_2} \cdots s_{i_k}\) for some sequence \((i_1, i_2, \ldots, i_k)\) of elements of \(\{ 1, 2, \ldots, n-1 \}\) (here \(\{ 1, 2, \ldots, n-1 \}\) denotes the empty set when \(n \leq 1\)). Fixing a \(p\), the sequences \((i_1, i_2, \ldots, i_k)\) of smallest length satisfying \(p = s_{i_1} s_{i_2} \cdots s_{i_k}\) are called the reduced words of \(p\). (Their length is the Coxeter length of \(p\), and can be computed using length().)

Note that the product of permutations is defined here in such a way that \((pq)(i) = p(q(i))\) for all permutations \(p\) and \(q\) and each \(i \in \{ 1, 2, \ldots, n \}\) (this is the same convention as in left_action_product(), but not the default semantics of the \(*\) operator on permutations in Sage). Thus, for instance, \(s_2 s_1\) is the permutation obtained by first transposing \(1\) with \(2\) and then transposing \(2\) with \(3\).

See also

reduced_word(), reduced_word_lexmin()

EXAMPLES:

Sage

sage: Permutation([2,1,3]).reduced_words()
[[1]]
sage: Permutation([3,1,2]).reduced_words()
[[2, 1]]
sage: Permutation([3,2,1]).reduced_words()
[[1, 2, 1], [2, 1, 2]]
sage: Permutation([3,2,4,1]).reduced_words()
[[1, 2, 3, 1], [1, 2, 1, 3], [2, 1, 2, 3]]

Permutation([1]).reduced_words()
[[]]
Permutation([]).reduced_words()
[[]]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).reduced_words()
[[1]]
>>> Permutation([Integer(3),Integer(1),Integer(2)]).reduced_words()
[[2, 1]]
>>> Permutation([Integer(3),Integer(2),Integer(1)]).reduced_words()
[[1, 2, 1], [2, 1, 2]]
>>> Permutation([Integer(3),Integer(2),Integer(4),Integer(1)]).reduced_words()
[[1, 2, 3, 1], [1, 2, 1, 3], [2, 1, 2, 3]]

Permutation([1]).reduced_words()
[[]]
Permutation([]).reduced_words()
[[]]

reduced_words_iterator()

Return an iterator for the reduced words of self.

EXAMPLES:

Sage

sage: next(Permutation([5,2,3,4,1]).reduced_words_iterator())
[1, 2, 3, 4, 3, 2, 1]

Python

>>> from sage.all import *
>>> next(Permutation([Integer(5),Integer(2),Integer(3),Integer(4),Integer(1)]).reduced_words_iterator())
[1, 2, 3, 4, 3, 2, 1]

remove_extra_fixed_points()

Return the permutation obtained by removing any fixed points at the end of self.

However, return [1] rather than [] if self is the identity permutation.

This is mostly a helper method for sage.combinat.schubert_polynomial, where it is used to normalize finitary permutations of \(\{1,2,3,\ldots\}\).

EXAMPLES:

Sage

sage: Permutation([2,1,3]).remove_extra_fixed_points()
[2, 1]
sage: Permutation([1,2,3,4]).remove_extra_fixed_points()
[1]
sage: Permutation([2,1]).remove_extra_fixed_points()
[2, 1]
sage: Permutation([]).remove_extra_fixed_points()
[1]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3)]).remove_extra_fixed_points()
[2, 1]
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4)]).remove_extra_fixed_points()
[1]
>>> Permutation([Integer(2),Integer(1)]).remove_extra_fixed_points()
[2, 1]
>>> Permutation([]).remove_extra_fixed_points()
[1]

See also

retract_plain()

retract_direct_product(m)

Return the direct-product retract of the permutation self \(\in S_n\) to \(S_m\), where \(m \leq n\). If this retract is undefined, then None is returned.

If \(p \in S_n\) is a permutation, and \(m\) is a nonnegative integer less or equal to \(n\), then the direct-product retract of \(p\) to \(S_m\) is defined only if \(p([m]) = [m]\), where \([m]\) denotes the interval \(\{1, 2, \ldots, m\}\). In this case, it is defined as the permutation written \((p(1), p(2), \ldots, p(m))\) in one-line notation.

EXAMPLES:

Sage

sage: Permutation([4,1,2,3,5]).retract_direct_product(4)
[4, 1, 2, 3]
sage: Permutation([4,1,2,3,5]).retract_direct_product(3)

sage: Permutation([1,4,2,3,6,5]).retract_direct_product(5)
sage: Permutation([1,4,2,3,6,5]).retract_direct_product(4)
[1, 4, 2, 3]
sage: Permutation([1,4,2,3,6,5]).retract_direct_product(3)
sage: Permutation([1,4,2,3,6,5]).retract_direct_product(2)
sage: Permutation([1,4,2,3,6,5]).retract_direct_product(1)
[1]
sage: Permutation([1,4,2,3,6,5]).retract_direct_product(0)
[]

sage: all( p.retract_direct_product(3) == p for p in Permutations(3) )
True

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_direct_product(Integer(4))
[4, 1, 2, 3]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_direct_product(Integer(3))

>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(5))
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(4))
[1, 4, 2, 3]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(3))
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(2))
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(1))
[1]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_direct_product(Integer(0))
[]

>>> all( p.retract_direct_product(Integer(3)) == p for p in Permutations(Integer(3)) )
True

See also

retract_plain(), retract_okounkov_vershik()

retract_okounkov_vershik(m)

Return the Okounkov-Vershik retract of the permutation self \(\in S_n\) to \(S_m\), where \(m \leq n\).

If \(p \in S_n\) is a permutation, and \(m\) is a nonnegative integer less or equal to \(n\), then the Okounkov-Vershik retract of \(p\) to \(S_m\) is defined as the permutation in \(S_m\) which sends every \(i \in \{1, 2, \ldots, m\}\) to \(p^{k_i}(i)\), where \(k_i\) is the smallest positive integer \(k\) satisfying \(p^k(i) \leq m\).

In other words, the Okounkov-Vershik retract of \(p\) is the permutation whose disjoint cycle decomposition is obtained by removing all letters strictly greater than \(m\) from the decomposition of \(p\) into disjoint cycles (and removing all cycles which are emptied in the process).

When \(m = n-1\), the Okounkov-Vershik retract (as a map \(S_n \to S_{n-1}\)) is the map \(\widetilde{p}_n\) introduced in Section 7 of [VO2005], and appears as (3.20) in [CST2010]. In the general case, the Okounkov-Vershik retract of a permutation in \(S_n\) to \(S_m\) can be obtained by first taking its Okounkov-Vershik retract to \(S_{n-1}\), then that of the resulting permutation to \(S_{n-2}\), etc. until arriving in \(S_m\).

EXAMPLES:

Sage

sage: Permutation([4,1,2,3,5]).retract_okounkov_vershik(4)
[4, 1, 2, 3]
sage: Permutation([4,1,2,3,5]).retract_okounkov_vershik(3)
[3, 1, 2]
sage: Permutation([4,1,2,3,5]).retract_okounkov_vershik(2)
[2, 1]
sage: Permutation([4,1,2,3,5]).retract_okounkov_vershik(1)
[1]
sage: Permutation([4,1,2,3,5]).retract_okounkov_vershik(0)
[]

sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(5)
[1, 4, 2, 3, 5]
sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(4)
[1, 4, 2, 3]
sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(3)
[1, 3, 2]
sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(2)
[1, 2]
sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(1)
[1]
sage: Permutation([1,4,2,3,6,5]).retract_okounkov_vershik(0)
[]

sage: Permutation([6,5,4,3,2,1]).retract_okounkov_vershik(5)
[1, 5, 4, 3, 2]
sage: Permutation([6,5,4,3,2,1]).retract_okounkov_vershik(4)
[1, 2, 4, 3]

sage: Permutation([1,5,2,6,3,7,4,8]).retract_okounkov_vershik(4)
[1, 3, 2, 4]

sage: all( p.retract_direct_product(3) == p for p in Permutations(3) )
True

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_okounkov_vershik(Integer(4))
[4, 1, 2, 3]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_okounkov_vershik(Integer(3))
[3, 1, 2]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_okounkov_vershik(Integer(2))
[2, 1]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_okounkov_vershik(Integer(1))
[1]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_okounkov_vershik(Integer(0))
[]

>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(5))
[1, 4, 2, 3, 5]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(4))
[1, 4, 2, 3]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(3))
[1, 3, 2]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(2))
[1, 2]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(1))
[1]
>>> Permutation([Integer(1),Integer(4),Integer(2),Integer(3),Integer(6),Integer(5)]).retract_okounkov_vershik(Integer(0))
[]

>>> Permutation([Integer(6),Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]).retract_okounkov_vershik(Integer(5))
[1, 5, 4, 3, 2]
>>> Permutation([Integer(6),Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]).retract_okounkov_vershik(Integer(4))
[1, 2, 4, 3]

>>> Permutation([Integer(1),Integer(5),Integer(2),Integer(6),Integer(3),Integer(7),Integer(4),Integer(8)]).retract_okounkov_vershik(Integer(4))
[1, 3, 2, 4]

>>> all( p.retract_direct_product(Integer(3)) == p for p in Permutations(Integer(3)) )
True

See also

retract_plain(), retract_direct_product()

retract_plain(m)

Return the plain retract of the permutation self in \(S_n\) to \(S_m\), where \(m \leq n\). If this retract is undefined, then None is returned.

If \(p \in S_n\) is a permutation, and \(m\) is a nonnegative integer less or equal to \(n\), then the plain retract of \(p\) to \(S_m\) is defined only if every \(i > m\) satisfies \(p(i) = i\). In this case, it is defined as the permutation written \((p(1), p(2), \ldots, p(m))\) in one-line notation.

EXAMPLES:

Sage

sage: Permutation([4,1,2,3,5]).retract_plain(4)
[4, 1, 2, 3]
sage: Permutation([4,1,2,3,5]).retract_plain(3)

sage: Permutation([1,3,2,4,5,6]).retract_plain(3)
[1, 3, 2]
sage: Permutation([1,3,2,4,5,6]).retract_plain(2)

sage: Permutation([1,2,3,4,5]).retract_plain(1)
[1]
sage: Permutation([1,2,3,4,5]).retract_plain(0)
[]

sage: all( p.retract_plain(3) == p for p in Permutations(3) )
True

Python

>>> from sage.all import *
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_plain(Integer(4))
[4, 1, 2, 3]
>>> Permutation([Integer(4),Integer(1),Integer(2),Integer(3),Integer(5)]).retract_plain(Integer(3))

>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4),Integer(5),Integer(6)]).retract_plain(Integer(3))
[1, 3, 2]
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(4),Integer(5),Integer(6)]).retract_plain(Integer(2))

>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).retract_plain(Integer(1))
[1]
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).retract_plain(Integer(0))
[]

>>> all( p.retract_plain(Integer(3)) == p for p in Permutations(Integer(3)) )
True

See also

retract_direct_product(), retract_okounkov_vershik(), remove_extra_fixed_points()

reverse()

Return the permutation obtained by reversing the list.

EXAMPLES:

Sage

sage: Permutation([3,4,1,2]).reverse()
[2, 1, 4, 3]
sage: Permutation([1,2,3,4,5]).reverse()
[5, 4, 3, 2, 1]

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(4),Integer(1),Integer(2)]).reverse()
[2, 1, 4, 3]
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)]).reverse()
[5, 4, 3, 2, 1]

right_action_product(rp)

Return the permutation obtained by composing self with rp in such an order that self is applied first and rp is applied afterwards.

This is usually denoted by either self * rp or rp * self depending on the conventions used by the author. If the value of a permutation \(p \in S_n\) on an integer \(i \in \{ 1, 2, \cdots, n \}\) is denoted by \(p(i)\), then this should be denoted by rp * self in order to have associativity (i.e., in order to have \((p \cdot q)(i) = p(q(i))\) for all \(p\), \(q\) and \(i\)). If, on the other hand, the value of a permutation \(p \in S_n\) on an integer \(i \in \{ 1, 2, \cdots, n \}\) is denoted by \(i^p\), then this should be denoted by self * rp in order to have associativity (i.e., in order to have \(i^{p \cdot q} = (i^p)^q\) for all \(p\), \(q\) and \(i\)).

EXAMPLES:

Sage

sage: p = Permutation([2,1,3])
sage: q = Permutation([3,1,2])
sage: p.right_action_product(q)
[1, 3, 2]
sage: q.right_action_product(p)
[3, 2, 1]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2),Integer(1),Integer(3)])
>>> q = Permutation([Integer(3),Integer(1),Integer(2)])
>>> p.right_action_product(q)
[1, 3, 2]
>>> q.right_action_product(p)
[3, 2, 1]

right_permutohedron_interval(other)

Return the list of the permutations belonging to the right permutohedron interval where self is the minimal element and other the maximal element.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: p = Permutation([2, 1, 4, 5, 3]); q = Permutation([2, 5, 4, 1, 3])
sage: p.right_permutohedron_interval(q)                                     # needs sage.graphs sage.modules
[[2, 4, 5, 1, 3], [2, 4, 1, 5, 3], [2, 1, 4, 5, 3],
 [2, 1, 5, 4, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2), Integer(1), Integer(4), Integer(5), Integer(3)]); q = Permutation([Integer(2), Integer(5), Integer(4), Integer(1), Integer(3)])
>>> p.right_permutohedron_interval(q)                                     # needs sage.graphs sage.modules
[[2, 4, 5, 1, 3], [2, 4, 1, 5, 3], [2, 1, 4, 5, 3],
 [2, 1, 5, 4, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]]

right_permutohedron_interval_iterator(other)

Return an iterator on the permutations (represented as integer lists) belonging to the right permutohedron interval where self is the minimal element and other the maximal element.

See permutohedron_lequal() for the definition of the permutohedron orders.

EXAMPLES:

Sage

sage: p = Permutation([2, 1, 4, 5, 3]); q = Permutation([2, 5, 4, 1, 3])
sage: p.right_permutohedron_interval(q)  # indirect doctest                 # needs sage.graphs sage.modules
[[2, 4, 5, 1, 3], [2, 4, 1, 5, 3], [2, 1, 4, 5, 3],
 [2, 1, 5, 4, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2), Integer(1), Integer(4), Integer(5), Integer(3)]); q = Permutation([Integer(2), Integer(5), Integer(4), Integer(1), Integer(3)])
>>> p.right_permutohedron_interval(q)  # indirect doctest                 # needs sage.graphs sage.modules
[[2, 4, 5, 1, 3], [2, 4, 1, 5, 3], [2, 1, 4, 5, 3],
 [2, 1, 5, 4, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]]

right_tableau()

Return the right standard tableau after performing the RSK algorithm on self.

EXAMPLES:

Sage

sage: Permutation([1,4,3,2]).right_tableau()                                # needs sage.combinat
[[1, 2], [3], [4]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(4),Integer(3),Integer(2)]).right_tableau()                                # needs sage.combinat
[[1, 2], [3], [4]]

robinson_schensted()

Return the pair of standard tableaux obtained by running the Robinson-Schensted algorithm on self.

This can also be done by running RSK() on self (with the optional argument check_standard=True to return standard Young tableaux).

EXAMPLES:

Sage

sage: Permutation([6,2,3,1,7,5,4]).robinson_schensted()                     # needs sage.combinat
[[[1, 3, 4], [2, 5], [6, 7]], [[1, 3, 5], [2, 6], [4, 7]]]

Python

>>> from sage.all import *
>>> Permutation([Integer(6),Integer(2),Integer(3),Integer(1),Integer(7),Integer(5),Integer(4)]).robinson_schensted()                     # needs sage.combinat
[[[1, 3, 4], [2, 5], [6, 7]], [[1, 3, 5], [2, 6], [4, 7]]]

rothe_diagram()

Return the Rothe diagram of self.

EXAMPLES:

Sage

sage: p = Permutation([4,2,1,3])
sage: D = p.rothe_diagram(); D                                              # needs sage.combinat
[(0, 0), (0, 1), (0, 2), (1, 0)]
sage: D.pp()                                                                # needs sage.combinat
O O O .
O . . .
. . . .
. . . .

Python

>>> from sage.all import *
>>> p = Permutation([Integer(4),Integer(2),Integer(1),Integer(3)])
>>> D = p.rothe_diagram(); D                                              # needs sage.combinat
[(0, 0), (0, 1), (0, 2), (1, 0)]
>>> D.pp()                                                                # needs sage.combinat
O O O .
O . . .
. . . .
. . . .

runs(as_tuple=False)

Return a list of the runs in the nonempty permutation self.

A run in a permutation is defined to be a maximal (with respect to inclusion) nonempty increasing substring (i. e., contiguous subsequence). For instance, the runs in the permutation [6,1,7,3,4,5,2] are [6], [1,7], [3,4,5] and [2].

Runs in an empty permutation are not defined.

INPUT:

• as_tuple – boolean (default: False); choice of output format

OUTPUT: list of lists or a tuple of tuples

REFERENCES:

• http://mathworld.wolfram.com/PermutationRun.html

EXAMPLES:

Sage

sage: Permutation([1,2,3,4]).runs()
[[1, 2, 3, 4]]
sage: Permutation([4,3,2,1]).runs()
[[4], [3], [2], [1]]
sage: Permutation([2,4,1,3]).runs()
[[2, 4], [1, 3]]
sage: Permutation([1]).runs()
[[1]]

Python

>>> from sage.all import *
>>> Permutation([Integer(1),Integer(2),Integer(3),Integer(4)]).runs()
[[1, 2, 3, 4]]
>>> Permutation([Integer(4),Integer(3),Integer(2),Integer(1)]).runs()
[[4], [3], [2], [1]]
>>> Permutation([Integer(2),Integer(4),Integer(1),Integer(3)]).runs()
[[2, 4], [1, 3]]
>>> Permutation([Integer(1)]).runs()
[[1]]

The example from above:

Sage

sage: Permutation([6,1,7,3,4,5,2]).runs()
[[6], [1, 7], [3, 4, 5], [2]]
sage: Permutation([6,1,7,3,4,5,2]).runs(as_tuple=True)
((6,), (1, 7), (3, 4, 5), (2,))

Python

>>> from sage.all import *
>>> Permutation([Integer(6),Integer(1),Integer(7),Integer(3),Integer(4),Integer(5),Integer(2)]).runs()
[[6], [1, 7], [3, 4, 5], [2]]
>>> Permutation([Integer(6),Integer(1),Integer(7),Integer(3),Integer(4),Integer(5),Integer(2)]).runs(as_tuple=True)
((6,), (1, 7), (3, 4, 5), (2,))

The number of runs in a nonempty permutation equals its number of descents plus 1:

Sage

sage: all( len(p.runs()) == p.number_of_descents() + 1
....:      for p in Permutations(6) )
True

Python

>>> from sage.all import *
>>> all( len(p.runs()) == p.number_of_descents() + Integer(1)
...      for p in Permutations(Integer(6)) )
True

saliances()

Return a list of the saliances of the permutation self.

A saliance of a permutation \(p\) is an integer \(i\) such that \(p(i) > p(j)\) for all \(j > i\).

EXAMPLES:

Sage

sage: Permutation([2,3,1,5,4]).saliances()
[3, 4]
sage: Permutation([5,4,3,2,1]).saliances()
[0, 1, 2, 3, 4]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(3),Integer(1),Integer(5),Integer(4)]).saliances()
[3, 4]
>>> Permutation([Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]).saliances()
[0, 1, 2, 3, 4]

shifted_concatenation(other, side='right')

Return the right (or left) shifted concatenation of self with a permutation other. These operations are also known as the Loday-Ronco over and under operations.

INPUT:

• other – a permutation, a list, a tuple, or any iterable representing a permutation

• side – string (default: 'right'); 'left' or 'right'

OUTPUT:

If side is 'right', the method returns the permutation obtained by concatenating self with the letters of other incremented by the size of self. This is what is called side / other in [LR0102066], and denoted as the “over” operation. Otherwise, i. e., when side is 'left', the method returns the permutation obtained by concatenating the letters of other incremented by the size of self with self. This is what is called side \ other in [LR0102066] (which seems to use the \((\sigma \pi)(i) = \pi(\sigma(i))\) convention for the product of permutations).

EXAMPLES:

Sage

sage: Permutation([]).shifted_concatenation(Permutation([]), "right")
[]
sage: Permutation([]).shifted_concatenation(Permutation([]), "left")
[]
sage: Permutation([2, 4, 1, 3]).shifted_concatenation(Permutation([3, 1, 2]), "right")
[2, 4, 1, 3, 7, 5, 6]
sage: Permutation([2, 4, 1, 3]).shifted_concatenation(Permutation([3, 1, 2]), "left")
[7, 5, 6, 2, 4, 1, 3]

Python

>>> from sage.all import *
>>> Permutation([]).shifted_concatenation(Permutation([]), "right")
[]
>>> Permutation([]).shifted_concatenation(Permutation([]), "left")
[]
>>> Permutation([Integer(2), Integer(4), Integer(1), Integer(3)]).shifted_concatenation(Permutation([Integer(3), Integer(1), Integer(2)]), "right")
[2, 4, 1, 3, 7, 5, 6]
>>> Permutation([Integer(2), Integer(4), Integer(1), Integer(3)]).shifted_concatenation(Permutation([Integer(3), Integer(1), Integer(2)]), "left")
[7, 5, 6, 2, 4, 1, 3]

shifted_shuffle(other)

Return the shifted shuffle of two permutations self and other.

INPUT:

• other – a permutation, a list, a tuple, or any iterable representing a permutation

OUTPUT:

The list of the permutations appearing in the shifted shuffle of the permutations self and other.

EXAMPLES:

Sage

sage: # needs sage.graphs sage.modules
sage: Permutation([]).shifted_shuffle(Permutation([]))
[[]]
sage: Permutation([1, 2, 3]).shifted_shuffle(Permutation([1]))
[[4, 1, 2, 3], [1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3]]
sage: Permutation([1, 2]).shifted_shuffle(Permutation([2, 1]))
[[4, 1, 3, 2], [4, 3, 1, 2], [1, 4, 3, 2],
 [1, 4, 2, 3], [1, 2, 4, 3], [4, 1, 2, 3]]
sage: Permutation([1]).shifted_shuffle([1])
[[2, 1], [1, 2]]
sage: p = Permutation([3, 1, 5, 4, 2])
sage: len(p.shifted_shuffle(Permutation([2, 1, 4, 3])))
126

Python

>>> from sage.all import *
>>> # needs sage.graphs sage.modules
>>> Permutation([]).shifted_shuffle(Permutation([]))
[[]]
>>> Permutation([Integer(1), Integer(2), Integer(3)]).shifted_shuffle(Permutation([Integer(1)]))
[[4, 1, 2, 3], [1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3]]
>>> Permutation([Integer(1), Integer(2)]).shifted_shuffle(Permutation([Integer(2), Integer(1)]))
[[4, 1, 3, 2], [4, 3, 1, 2], [1, 4, 3, 2],
 [1, 4, 2, 3], [1, 2, 4, 3], [4, 1, 2, 3]]
>>> Permutation([Integer(1)]).shifted_shuffle([Integer(1)])
[[2, 1], [1, 2]]
>>> p = Permutation([Integer(3), Integer(1), Integer(5), Integer(4), Integer(2)])
>>> len(p.shifted_shuffle(Permutation([Integer(2), Integer(1), Integer(4), Integer(3)])))
126

The shifted shuffle product is associative. We can test this on an admittedly toy example:

Sage

sage: all( all( all( sorted(flatten([abs.shifted_shuffle(c)                 # needs sage.graphs sage.modules
....:                                for abs in a.shifted_shuffle(b)]))
....:                == sorted(flatten([a.shifted_shuffle(bcs)
....:                                   for bcs in b.shifted_shuffle(c)]))
....:                for c in Permutations(2) )
....:           for b in Permutations(2) )
....:      for a in Permutations(2) )
True

Python

>>> from sage.all import *
>>> all( all( all( sorted(flatten([abs.shifted_shuffle(c)                 # needs sage.graphs sage.modules
...                                for abs in a.shifted_shuffle(b)]))
...                == sorted(flatten([a.shifted_shuffle(bcs)
...                                   for bcs in b.shifted_shuffle(c)]))
...                for c in Permutations(Integer(2)) )
...           for b in Permutations(Integer(2)) )
...      for a in Permutations(Integer(2)) )
True

The shifted_shuffle method on permutations gives the same permutations as the shifted_shuffle method on words (but is faster):

Sage

sage: all( all( sorted(p1.shifted_shuffle(p2))                              # needs sage.combinat sage.graphs sage.modules sage.rings.finite_rings
....:           == sorted([Permutation(p) for p in
....:                      Word(p1).shifted_shuffle(Word(p2))])
....:           for p2 in Permutations(3) )
....:      for p1 in Permutations(2) )
True

Python

>>> from sage.all import *
>>> all( all( sorted(p1.shifted_shuffle(p2))                              # needs sage.combinat sage.graphs sage.modules sage.rings.finite_rings
...           == sorted([Permutation(p) for p in
...                      Word(p1).shifted_shuffle(Word(p2))])
...           for p2 in Permutations(Integer(3)) )
...      for p1 in Permutations(Integer(2)) )
True

show(representation='cycles', orientation='landscape', **args)

Display the permutation as a drawing.

INPUT:

• representation – different kinds of drawings are available

  • 'cycles' – default; the permutation is displayed as a collection of directed cycles

  • 'braid' – the permutation is displayed as segments linking each element \(1, ..., n\) to its image on a parallel line

    When using this drawing, it is also possible to display the permutation horizontally (orientation = "landscape", default option) or vertically (orientation = "portrait").

  • 'chord-diagram' – the permutation is displayed as a directed graph, all of its vertices being located on a circle

All additional arguments are forwarded to the show subcalls.

EXAMPLES:

Sage

sage: P20 = Permutations(20)
sage: P20.random_element().show(representation='cycles')                    # needs sage.graphs sage.plot
sage: P20.random_element().show(representation='chord-diagram')             # needs sage.graphs sage.plot
sage: P20.random_element().show(representation='braid')                     # needs sage.plot
sage: P20.random_element().show(representation='braid',                     # needs sage.plot
....:                           orientation='portrait')

Python

>>> from sage.all import *
>>> P20 = Permutations(Integer(20))
>>> P20.random_element().show(representation='cycles')                    # needs sage.graphs sage.plot
>>> P20.random_element().show(representation='chord-diagram')             # needs sage.graphs sage.plot
>>> P20.random_element().show(representation='braid')                     # needs sage.plot
>>> P20.random_element().show(representation='braid',                     # needs sage.plot
...                           orientation='portrait')

sign()

Return the signature of the permutation self. This is \((-1)^l\), where \(l\) is the number of inversions of self.

Note

sign() can be used as an alias for signature().

EXAMPLES:

Sage

sage: Permutation([4, 2, 3, 1, 5]).signature()
-1
sage: Permutation([1,3,2,5,4]).sign()
1
sage: Permutation([]).sign()
1

Python

>>> from sage.all import *
>>> Permutation([Integer(4), Integer(2), Integer(3), Integer(1), Integer(5)]).signature()
-1
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(5),Integer(4)]).sign()
1
>>> Permutation([]).sign()
1

signature()

Return the signature of the permutation self. This is \((-1)^l\), where \(l\) is the number of inversions of self.

Note

sign() can be used as an alias for signature().

EXAMPLES:

Sage

sage: Permutation([4, 2, 3, 1, 5]).signature()
-1
sage: Permutation([1,3,2,5,4]).sign()
1
sage: Permutation([]).sign()
1

Python

>>> from sage.all import *
>>> Permutation([Integer(4), Integer(2), Integer(3), Integer(1), Integer(5)]).signature()
-1
>>> Permutation([Integer(1),Integer(3),Integer(2),Integer(5),Integer(4)]).sign()
1
>>> Permutation([]).sign()
1

simion_schmidt(avoid=[1, 2, 3])

Implement the Simion-Schmidt map which sends an arbitrary permutation to a pattern avoiding permutation, where the permutation pattern is one of four length-three patterns. This method also implements the bijection between (for example) [1,2,3]- and [1,3,2]-avoiding permutations.

INPUT:

• avoid – one of the patterns [1,2,3], [1,3,2], [3,1,2], [3,2,1]

EXAMPLES:

Sage

sage: P = Permutations(6)
sage: p = P([4,5,1,6,3,2])
sage: pl = [ [1,2,3], [1,3,2], [3,1,2], [3,2,1] ]
sage: for q in pl:                                                          # needs sage.combinat
....:     s = p.simion_schmidt(q)
....:     print("{} {}".format(s, s.has_pattern(q)))
[4, 6, 1, 5, 3, 2] False
[4, 2, 1, 3, 5, 6] False
[4, 5, 3, 6, 2, 1] False
[4, 5, 1, 6, 2, 3] False

Python

>>> from sage.all import *
>>> P = Permutations(Integer(6))
>>> p = P([Integer(4),Integer(5),Integer(1),Integer(6),Integer(3),Integer(2)])
>>> pl = [ [Integer(1),Integer(2),Integer(3)], [Integer(1),Integer(3),Integer(2)], [Integer(3),Integer(1),Integer(2)], [Integer(3),Integer(2),Integer(1)] ]
>>> for q in pl:                                                          # needs sage.combinat
...     s = p.simion_schmidt(q)
...     print("{} {}".format(s, s.has_pattern(q)))
[4, 6, 1, 5, 3, 2] False
[4, 2, 1, 3, 5, 6] False
[4, 5, 3, 6, 2, 1] False
[4, 5, 1, 6, 2, 3] False

size()

Return the size of self.

EXAMPLES:

Sage

sage: Permutation([3,4,1,2,5]).size()
5

Python

>>> from sage.all import *
>>> Permutation([Integer(3),Integer(4),Integer(1),Integer(2),Integer(5)]).size()
5

stack_sort()

Return the stack sort of a permutation.

This is another permutation obtained through the process of sorting using one stack. If the result is the identity permutation, the original permutation is stack-sortable.

See Wikipedia article Stack-sortable_permutation

EXAMPLES:

Sage

sage: p = Permutation([2,1,5,3,4,9,7,8,6])
sage: p.stack_sort()
[1, 2, 3, 4, 5, 7, 6, 8, 9]

sage: S5 = Permutations(5)
sage: len([1 for s in S5 if s.stack_sort() == S5.one()])
42

Python

>>> from sage.all import *
>>> p = Permutation([Integer(2),Integer(1),Integer(5),Integer(3),Integer(4),Integer(9),Integer(7),Integer(8),Integer(6)])
>>> p.stack_sort()
[1, 2, 3, 4, 5, 7, 6, 8, 9]

>>> S5 = Permutations(Integer(5))
>>> len([Integer(1) for s in S5 if s.stack_sort() == S5.one()])
42

sylvester_class(left_to_right=False)

Iterate over the equivalence class of the permutation self under sylvester congruence.

Sylvester congruence is an equivalence relation on the set \(S_n\) of all permutations of \(n\). It is defined as the smallest equivalence relation such that every permutation of the form \(uacvbw\) with \(u\), \(v\) and \(w\) being words and \(a\), \(b\) and \(c\) being letters satisfying \(a \leq b < c\) is equivalent to the permutation \(ucavbw\). (Here, permutations are regarded as words by way of one-line notation.) This definition comes from [HNT2005], Definition 8, where it is more generally applied to arbitrary words.

The equivalence class of a permutation \(p \in S_n\) under sylvester congruence is called the sylvester class of \(p\). It is an interval in the right permutohedron order (see permutohedron_lequal()) on \(S_n\).

This is related to the sylvester_class() method in that the equivalence class of a permutation \(\pi\) under sylvester congruence is the sylvester class of the right-to-left binary search tree of \(\pi\). However, the present method yields permutations, while the method on labelled binary trees yields plain lists.

If the variable left_to_right is set to True, the method instead iterates over the equivalence class of self with respect to the left sylvester congruence. The left sylvester congruence is easiest to define by saying that two permutations are equivalent under it if and only if their reverses (reverse()) are equivalent under (standard) sylvester congruence.

EXAMPLES:

The sylvester class of a permutation in \(S_5\):

Sage

sage: p = Permutation([3, 5, 1, 2, 4])
sage: sorted(p.sylvester_class())                                           # needs sage.combinat sage.graphs
[[1, 3, 2, 5, 4],
 [1, 3, 5, 2, 4],
 [1, 5, 3, 2, 4],
 [3, 1, 2, 5, 4],
 [3, 1, 5, 2, 4],
 [3, 5, 1, 2, 4],
 [5, 1, 3, 2, 4],
 [5, 3, 1, 2, 4]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(3), Integer(5), Integer(1), Integer(2), Integer(4)])
>>> sorted(p.sylvester_class())                                           # needs sage.combinat sage.graphs
[[1, 3, 2, 5, 4],
 [1, 3, 5, 2, 4],
 [1, 5, 3, 2, 4],
 [3, 1, 2, 5, 4],
 [3, 1, 5, 2, 4],
 [3, 5, 1, 2, 4],
 [5, 1, 3, 2, 4],
 [5, 3, 1, 2, 4]]

The sylvester class of a permutation \(p\) contains \(p\):

Sage

sage: all(p in p.sylvester_class() for p in Permutations(4))                # needs sage.combinat sage.graphs
True

Python

>>> from sage.all import *
>>> all(p in p.sylvester_class() for p in Permutations(Integer(4)))                # needs sage.combinat sage.graphs
True

Small cases:

Sage

sage: list(Permutation([]).sylvester_class())                               # needs sage.combinat sage.graphs
[[]]

sage: list(Permutation([1]).sylvester_class())                              # needs sage.combinat sage.graphs
[[1]]

Python

>>> from sage.all import *
>>> list(Permutation([]).sylvester_class())                               # needs sage.combinat sage.graphs
[[]]

>>> list(Permutation([Integer(1)]).sylvester_class())                              # needs sage.combinat sage.graphs
[[1]]

The sylvester classes in \(S_3\):

Sage

sage: [sorted(p.sylvester_class()) for p in Permutations(3)]                # needs sage.combinat sage.graphs
[[[1, 2, 3]],
 [[1, 3, 2], [3, 1, 2]],
 [[2, 1, 3]],
 [[2, 3, 1]],
 [[1, 3, 2], [3, 1, 2]],
 [[3, 2, 1]]]

Python

>>> from sage.all import *
>>> [sorted(p.sylvester_class()) for p in Permutations(Integer(3))]                # needs sage.combinat sage.graphs
[[[1, 2, 3]],
 [[1, 3, 2], [3, 1, 2]],
 [[2, 1, 3]],
 [[2, 3, 1]],
 [[1, 3, 2], [3, 1, 2]],
 [[3, 2, 1]]]

The left sylvester classes in \(S_3\):

Sage

sage: [sorted(p.sylvester_class(left_to_right=True))                        # needs sage.combinat sage.graphs
....:  for p in Permutations(3)]
[[[1, 2, 3]],
 [[1, 3, 2]],
 [[2, 1, 3], [2, 3, 1]],
 [[2, 1, 3], [2, 3, 1]],
 [[3, 1, 2]],
 [[3, 2, 1]]]

Python

>>> from sage.all import *
>>> [sorted(p.sylvester_class(left_to_right=True))                        # needs sage.combinat sage.graphs
...  for p in Permutations(Integer(3))]
[[[1, 2, 3]],
 [[1, 3, 2]],
 [[2, 1, 3], [2, 3, 1]],
 [[2, 1, 3], [2, 3, 1]],
 [[3, 1, 2]],
 [[3, 2, 1]]]

A left sylvester class in \(S_5\):

Sage

sage: p = Permutation([4, 2, 1, 5, 3])
sage: sorted(p.sylvester_class(left_to_right=True))                         # needs sage.combinat sage.graphs
[[4, 2, 1, 3, 5],
 [4, 2, 1, 5, 3],
 [4, 2, 3, 1, 5],
 [4, 2, 3, 5, 1],
 [4, 2, 5, 1, 3],
 [4, 2, 5, 3, 1],
 [4, 5, 2, 1, 3],
 [4, 5, 2, 3, 1]]

Python

>>> from sage.all import *
>>> p = Permutation([Integer(4), Integer(2), Integer(1), Integer(5), Integer(3)])
>>> sorted(p.sylvester_class(left_to_right=True))                         # needs sage.combinat sage.graphs
[[4, 2, 1, 3, 5],
 [4, 2, 1, 5, 3],
 [4, 2, 3, 1, 5],
 [4, 2, 3, 5, 1],
 [4, 2, 5, 1, 3],
 [4, 2, 5, 3, 1],
 [4, 5, 2, 1, 3],
 [4, 5, 2, 3, 1]]

to_alternating_sign_matrix()

Return a matrix representing the permutation in the AlternatingSignMatrix class.

EXAMPLES:

Sage

sage: m = Permutation([1,2,3]).to_alternating_sign_matrix(); m              # needs sage.combinat sage.modules
[1 0 0]
[0 1 0]
[0 0 1]
sage: parent(m)                                                             # needs sage.combinat sage.modules
Alternating sign matrices of size 3

Python

>>> from sage.all import *
>>> m = Permutation([Integer(1),Integer(2),Integer(3)]).to_alternating_sign_matrix(); m              # needs sage.combinat sage.modules
[1 0 0]
[0 1 0]
[0 0 1]
>>> parent(m)                                                             # needs sage.combinat sage.modules
Alternating sign matrices of size 3

to_cycles(singletons=True, use_min=True)

Return the permutation self as a list of disjoint cycles.

The cycles are returned in the order of increasing smallest elements, and each cycle is returned as a tuple which starts with its smallest element.

If singletons=False is given, the list does not contain the singleton cycles.

If use_min=False is given, the cycles are returned in the order of increasing largest (not smallest) elements, and each cycle starts with its largest element.

EXAMPLES:

Sage

sage: Permutation([2,1,3,4]).to_cycles()
[(1, 2), (3,), (4,)]
sage: Permutation([2,1,3,4]).to_cycles(singletons=False)
[(1, 2)]
sage: Permutation([2,1,3,4]).to_cycles(use_min=True)
[(1, 2), (3,), (4,)]
sage: Permutation([2,1,3,4]).to_cycles(use_min=False)
[(4,), (3,), (2, 1)]
sage: Permutation([2,1,3,4]).to_cycles(singletons=False, use_min=False)
[(2, 1)]

sage: Permutation([4,1,5,2,6,3]).to_cycles()
[(1, 4, 2), (3, 5, 6)]
sage: Permutation([4,1,5,2,6,3]).to_cycles(use_min=False)
[(6, 3, 5), (4, 2, 1)]

sage: Permutation([6, 4, 5, 2, 3, 1]).to_cycles()
[(1, 6), (2, 4), (3, 5)]
sage: Permutation([6, 4, 5, 2, 3, 1]).to_cycles(use_min=False)
[(6, 1), (5, 3), (4, 2)]

Python

>>> from sage.all import *
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles()
[(1, 2), (3,), (4,)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(singletons=False)
[(1, 2)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(use_min=True)
[(1, 2), (3,), (4,)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(use_min=False)
[(4,), (3,), (2, 1)]
>>> Permutation([Integer(2),Integer(1),Integer(3),Integer(4)]).to_cycles(singletons=False, use_min=False)
[(2, 1)]

>>> Permutation([Integer(4),Integer(1),Integer(5),Integer(2),Integer(6),Integer(3)]).to_cycles()
[(1, 4, 2), (3, 5, 6)]
>>> Permutation([Integer(4),Integer(1),Integer(5),Integer(2),Integer(6),Integer(3)]).to_cycles(use_min=False)
[(6, 3, 5), (4, 2, 1)]

>>> Permutation([Integer(6), Integer(4), Integer(5), Integer(2), Integer(3), Integer(1)]).to_cycles()
[(1, 6), (2, 4), (3, 5)]
>>> Permutation([Integer(6), Integer(4), Integer(5), Integer(2), Integer(3), Integer(1)]).to_cycles(use_min=False)
[(6, 1), (5, 3), (4, 2)]

The algorithm is of complexity \(O(n)\) where \(n\) is the size of the given permutation.

to_digraph()

Return a digraph representation of self.

EXAMPLES:

Sage

sage: d = Permutation([3, 1, 2]).to_digraph()                               # needs sage.graphs
sage: d.edges(sort=True, labels=False)                                      # needs sage.graphs
[(1, 3), (2, 1), (3, 2)]
sage: P =