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 trac ticket #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() Returns the product of self with another permutation, in which the other permutation is applied first.
right_action_product() Returns the product of self with another permutation, in which self is applied first.
size() Returns the size of the permutation self.
cycle_string() Returns the disjoint-cycles representation of self as string.
next() Returns the permutation that follows self in lexicographic order (in the same symmetric group as self).
prev() Returns the permutation that comes directly before self in lexicographic order (in the same symmetric group as self).
to_tableau_by_shape() Returns a tableau of shape shape with the entries in self.
to_cycles() Returns the permutation self as a list of disjoint cycles.
forget_cycles() Return self under the forget cycle map.
to_permutation_group_element() Returns a PermutationGroupElement equal to self.
signature() Returns the signature of the permutation sef.
is_even() Returns True if the permutation self is even, and False otherwise.
to_matrix() Returns a matrix representing the permutation self.
rank() Returns the rank of self in lexicographic ordering (on the symmetric group containing self).
to_inversion_vector() Returns the inversion vector of a permutation self.
inversions() Returns a list of the inversions of permutation self.
show() Displays the permutation as a drawing.
number_of_inversions() Returns the number of inversions in the permutation self.
noninversions() Returns the k-noninversions in the permutation self.
number_of_noninversions() Returns the number of k-noninversions in the permutation self.
length() Returns the Coxeter length of a permutation self.
inverse() Returns the inverse of a permutation self.
ishift() Returns the i-shift of self.
iswitch() Returns the i-switch of self.
runs() Returns a list of the runs in the permutation self.
longest_increasing_subsequence_length() Returns the length of the longest increasing subsequences of self.
longest_increasing_subsequences() Returns the list of the longest increasing subsequences of self.
cycle_type() Returns the cycle type of self as a partition of len(self).
foata_bijection() Returns the image of the permutation self under the Foata bijection \(\phi\).
foata_bijection_inverse() Returns the image of the permutation self under the inverse of the Foata bijection \(\phi\).
fundamental_transformation() Returns the image of the permutation self under the Renyi-Foata-Schuetzenberger fundamental transformation.
fundamental_transformation_inverse() Returns 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() Returns the Lehmer code of the permutation self.
to_lehmer_cocode() Returns the Lehmer cocode of self.
reduced_word() Returns the reduced word of the permutation self.
reduced_words() Returns 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() Returns a lexicographically minimal reduced word of a permutation self.
fixed_points() Returns a list of the fixed points of the permutation self.
number_of_fixed_points() Returns the number of fixed points of the permutation self.
recoils() Returns the list of the positions of the recoils of the permutation self.
number_of_recoils() Returns the number of recoils of the permutation self.
recoils_composition() Returns the composition corresponding to the recoils of self.
descents() Returns the list of the descents of the permutation self.
idescents() Returns a list of the idescents of self.
idescents_signature() Returns 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() Returns the number of descents of the permutation self.
number_of_idescents() Returns the number of idescents of the permutation self.
descents_composition() Returns the composition corresponding to the descents of self.
descent_polynomial() Returns the descent polynomial of the permutation self.
major_index() Returns the major index of the permutation self.
imajor_index() Returns the inverse major index of the permutation self.
to_major_code() Returns the major code of the permutation self.
peaks() Returns a list of the peaks of the permutation self.
number_of_peaks() Returns the number of peaks of the permutation self.
saliances() Returns a list of the saliances of the permutation self.
number_of_saliances() Returns the number of saliances of the permutation self.
bruhat_lequal() Returns True if self is less or equal to p2 in the Bruhat order.
weak_excedences() Returns all the numbers self[i] such that self[i] >= i+1.
bruhat_inversions() Returns the list of inversions of self such that the application of this inversion to self decrements its number of inversions.
bruhat_inversions_iterator() Returns an iterator over Bruhat inversions of self.
bruhat_succ() Returns 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() Returns 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() Returns the combinatorial class of permutations smaller than or equal to self in the Bruhat order.
bruhat_greater() Returns the combinatorial class of permutations greater than or equal to self in the Bruhat order.
permutohedron_lequal() Returns True if self is less or equal to p2 in the permutohedron order.
permutohedron_succ() Returns a list of the permutations covering self in the permutohedron order.
permutohedron_pred() Returns a list of the permutations covered by self in the permutohedron order.
permutohedron_smaller() Returns a list of permutations smaller than or equal to self in the permutohedron order.
permutohedron_greater() Returns a list of permutations greater than or equal to self in the permutohedron order.
right_permutohedron_interval_iterator() Returns an iterator over permutations in an interval of the permutohedron order.
right_permutohedron_interval() Returns a list of permutations in an interval of the permutohedron order.
has_pattern() Tests whether the permutation self matches the pattern.
avoids() Tests whether the permutation self avoids the pattern.
pattern_positions() Returns the list of positions where the pattern patt appears in self.
reverse() Returns the permutation obtained by reversing the 1-line notation of self.
complement() Returns 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() Returns the permutation poset of self.
dict() Returns a dictionary corresponding to the permutation self.
action() Returns the action of the permutation self on a list.
robinson_schensted() Returns the pair of standard tableaux obtained by running the Robinson-Schensted Algorithm on self.
left_tableau() Returns the left standard tableau after performing the RSK algorithm.
right_tableau() Returns the right standard tableau after performing the RSK algorithm.
increasing_tree() Returns the increasing tree of self.
increasing_tree_shape() Returns the shape of the increasing tree of self.
binary_search_tree() Returns the binary search tree of self.
sylvester_class() Iterates over the equivalence class of self under sylvester congruence
RS_partition() Returns the shape of the tableaux obtained by the RSK algorithm.
remove_extra_fixed_points() Returns the permutation obtained by removing any fixed points at the end of self.
retract_plain() Returns the plain retract of self to a smaller symmetric group \(S_m\).
retract_direct_product() Returns the direct-product retract of self to a smaller symmetric group \(S_m\).
retract_okounkov_vershik() Returns the Okounkov-Vershik retract of self to a smaller symmetric group \(S_m\).
hyperoctahedral_double_coset_type() Returns the coset-type of self as a partition.
binary_search_tree_shape() Returns the shape of the binary search tree of self (a non labelled binary tree).
shifted_concatenation() Returns the right (or left) shifted concatenation of self with a permutation other.
shifted_shuffle() Returns 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() Returns the permutation corresponding to major code mc.
from_permutation_group_element() Returns a Permutation give a PermutationGroupElement pge.
from_rank() Returns the permutation with the specified lexicographic rank.
from_inversion_vector() Returns the permutation corresponding to inversion vector iv.
from_cycles() Returns the permutation with given disjoint-cycle representation cycles.
from_lehmer_code() Returns the permutation with Lehmer code lehmer.
from_reduced_word() Returns the permutation corresponding to the reduced word rw.
bistochastic_as_sum_of_permutations() Returns a given bistochastic matrix as a nonnegative linear combination of permutations.
bounded_affine_permutation() Returns a partial permutation representing the bounded affine permutation of a matrix.
descents_composition_list() Returns a list of all the permutations in a given descent class (i. e., having a given descents composition).
descents_composition_first() Returns the smallest element of a descent class.
descents_composition_last() Returns the largest element of a descent class.
bruhat_lequal() Returns True if p1 is less or equal to p2 in the Bruhat order.
permutohedron_lequal() Returns True if p1 is less or equal to p2 in the permutohedron order.
to_standard() Returns 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 trac ticket #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.

Classes and methods

sage.combinat.permutation.Arrangements

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: mset = [1,1,2,3,4,4,5]
sage: Arrangements(mset,2).list()
[[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()
 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']]
sage.combinat.permutation.Arrangements_msetk

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

sage.combinat.permutation.Arrangements_setk

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

sage.combinat.permutation.CyclicPermutations

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

INPUT:

  • mset – A multiset

EXAMPLES:

sage: CyclicPermutations(range(4)).list()
[[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()
[[1, 1, 1]]
sage.combinat.permutation.CyclicPermutationsOfPartition

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

This is the same as a Cartesian product of necklaces.

EXAMPLES:

sage: CyclicPermutationsOfPartition([[1,2,3,4],[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]]]
sage: CyclicPermutationsOfPartition([[1,2,3,4],[4,4,4]]).list()
[[[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: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)
[[[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: sage.combinat.backtrack.GenericBacktracker

EXAMPLES:

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...>
sage.combinat.permutation.Permutation

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_input 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_input (boolean) – whether to check that input is correct. Slows
    the function down, but ensures that nothing bad happens. This is set to True by default.

Warning

Since trac ticket #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_input = 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 trac ticket #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: 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'>

Construction from a string in cycle notation:

sage: 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: p2 = Permutation( '(4,5)(10)' ); p2
[1, 2, 3, 5, 4, 6, 7, 8, 9, 10]
sage: len(p); len(p2)
5
10

We construct a Permutation from a PermutationGroupElement:

sage: g = PermutationGroupElement([2,1,3])
sage: Permutation(g)
[2, 1, 3]

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

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]
Permutation.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: 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]
Permutation.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: 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]
sage.combinat.permutation.Permutations

Permutations.

Permutations(n) returns the class of permutations of n, if n is an integer, list, set, or string.

Permutations(n, k) returns the class of length-k partial permutations of n (where n is any of the above things); k must be a nonnegative integer. A length-\(k\) partial permutation of \(n\) is defined as a \(k\)-tuple of pairwise distinct elements of \(\{ 1, 2, \ldots, n \}\).

Valid keyword arguments are: ‘descents’, ‘bruhat_smaller’, ‘bruhat_greater’, ‘recoils_finer’, ‘recoils_fatter’, ‘recoils’, and ‘avoiding’. With the exception of ‘avoiding’, you cannot specify n or k along with a keyword.

Permutations(descents=(list,n)) returns the class of permutations of \(n\) with descents in the positions specified by list. This uses the slightly nonstandard convention that the images of \(1,2,...,n\) under the permutation are regarded as positions \(0,1,...,n-1\), so for example the presence of \(1\) in list signifies that the permutations \(\pi\) should satisfy \(\pi(2) > \pi(3)\). Note that list is supposed to be a list of positions of the descents, not the descents composition. It does not return the class of permutations with descents composition list.

Permutations(bruhat_smaller=p) and Permutations(bruhat_greater=p) return the class of permutations smaller-or-equal or greater-or-equal, respectively, than the given permutation p in the Bruhat order. (The Bruhat order is defined in bruhat_lequal(). It is also referred to as the strong Bruhat order.)

Permutations(recoils=p) returns the class of permutations whose recoils composition is p. Unlike the descents=(list, n) syntax, this actually takes a composition as input.

Permutations(recoils_fatter=p) and Permutations(recoils_finer=p) return the class of permutations whose recoils composition is fatter or finer, respectively, than the given composition p.

Permutations(n, avoiding=P) returns the class of permutations of n avoiding P. Here P may be a single permutation or a list of permutations; the returned class will avoid all patterns in P.

EXAMPLES:

sage: p = Permutations(3); p
Standard permutations of 3
sage: p.list()
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: p = Permutations(3, 2); p
Permutations of {1,...,3} of length 2
sage: p.list()
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
sage: p = Permutations(['c', 'a', 't']); p
Permutations of the set ['c', 'a', 't']
sage: p.list()
[['c', 'a', 't'],
 ['c', 't', 'a'],
 ['a', 'c', 't'],
 ['a', 't', 'c'],
 ['t', 'c', 'a'],
 ['t', 'a', 'c']]
sage: p = Permutations(['c', 'a', 't'], 2); p
Permutations of the set ['c', 'a', 't'] of length 2
sage: p.list()
[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
sage: p = Permutations([1,1,2]); p
Permutations of the multi-set [1, 1, 2]
sage: p.list()
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
sage: p = Permutations([1,1,2], 2); p
Permutations of the multi-set [1, 1, 2] of length 2
sage: p.list()
[[1, 1], [1, 2], [2, 1]]
sage: p = Permutations(descents=([1], 4)); p
Standard permutations of 4 with descents [1]
sage: p.list()
[[2, 4, 1, 3], [3, 4, 1, 2], [1, 4, 2, 3], [1, 3, 2, 4], [2, 3, 1, 4]]
sage: p = Permutations(bruhat_smaller=[1,3,2,4]); p
Standard permutations that are less than or equal to [1, 3, 2, 4] in the Bruhat order
sage: p.list()
[[1, 2, 3, 4], [1, 3, 2, 4]]
sage: p = Permutations(bruhat_greater=[4,2,3,1]); p
Standard permutations that are greater than or equal to [4, 2, 3, 1] in the Bruhat order
sage: p.list()
[[4, 2, 3, 1], [4, 3, 2, 1]]
sage: p = Permutations(recoils_finer=[2,1]); p
Standard permutations whose recoils composition is finer than [2, 1]
sage: p.list()
[[3, 1, 2], [1, 2, 3], [1, 3, 2]]
sage: p = Permutations(recoils_fatter=[2,1]); p
Standard permutations whose recoils composition is fatter than [2, 1]
sage: p.list()
[[3, 1, 2], [3, 2, 1], [1, 3, 2]]
sage: p = Permutations(recoils=[2,1]); p
Standard permutations whose recoils composition is [2, 1]
sage: p.list()
[[3, 1, 2], [1, 3, 2]]
sage: p = Permutations(4, avoiding=[1,3,2]); p
Standard permutations of 4 avoiding [1, 3, 2]
sage: p.list()
[[4, 1, 2, 3],
 [4, 2, 1, 3],
 [4, 2, 3, 1],
 [4, 3, 1, 2],
 [4, 3, 2, 1],
 [3, 4, 1, 2],
 [3, 4, 2, 1],
 [2, 3, 4, 1],
 [3, 2, 4, 1],
 [1, 2, 3, 4],
 [2, 1, 3, 4],
 [2, 3, 1, 4],
 [3, 1, 2, 4],
 [3, 2, 1, 4]]
sage: p = Permutations(5, avoiding=[[3,4,1,2], [4,2,3,1]]); p
Standard permutations of 5 avoiding [[3, 4, 1, 2], [4, 2, 3, 1]]
sage: p.cardinality()
88
sage: p.random_element()
[5, 1, 2, 4, 3]
sage.combinat.permutation.PermutationsNK

This exists solely for unpickling PermutationsNK objects created with Sage <= 6.3.

sage.combinat.permutation.Permutations_mset

Permutations of a multiset \(M\).

A permutation of a multiset \(M\) is represented by a list that contains exactly the same elements as \(M\) (with the same multiplicities), but possibly in different order. If \(M\) is a proper set there are \(|M| !\) such permutations. Otherwise, if the first element appears \(k_1\) times, the second element appears \(k_2\) times and so on, the number of permutations is \(|M|! / (k_1! k_2! \ldots)\), which is sometimes called a multinomial coefficient.

EXAMPLES:

sage: mset = [1,1,2,2,2]
sage: from sage.combinat.permutation import Permutations_mset
sage: P = Permutations_mset(mset); P
Permutations of the multi-set [1, 1, 2, 2, 2]
sage: sorted(P)
[[1, 1, 2, 2, 2],
 [1, 2, 1, 2, 2],
 [1, 2, 2, 1, 2],
 [1, 2, 2, 2, 1],
 [2, 1, 1, 2, 2],
 [2, 1, 2, 1, 2],
 [2, 1, 2, 2, 1],
 [2, 2, 1, 1, 2],
 [2, 2, 1, 2, 1],
 [2, 2, 2, 1, 1]]
sage: MS = MatrixSpace(GF(2),2,2)
sage: A = MS([1,0,1,1])
sage: rows = A.rows()
sage: rows[0].set_immutable()
sage: rows[1].set_immutable()
sage: P = Permutations_mset(rows); P
Permutations of the multi-set [(1, 0), (1, 1)]
sage: sorted(P)
[[(1, 0), (1, 1)], [(1, 1), (1, 0)]]
sage.combinat.permutation.Permutations_msetk

Length-\(k\) partial permutations of a multiset.

A length-\(k\) partial permutation of a multiset \(M\) is represented by a list of length \(k\) whose entries are elements of \(M\), appearing in the list with a multiplicity not higher than their respective multiplicity in \(M\).

sage.combinat.permutation.Permutations_nk

Length-\(k\) partial permutations of \(\{1, 2, \ldots, n\}\).

sage.combinat.permutation.Permutations_set

Permutations of an arbitrary given finite set.

Here, a “permutation of a finite set \(S\)” means a list of the elements of \(S\) in which every element of \(S\) occurs exactly once. This is not to be confused with bijections from \(S\) to \(S\), which are also often called permutations in literature.

sage.combinat.permutation.Permutations_setk

Length-\(k\) partial permutations of an arbitrary given finite set.

Here, a “length-\(k\) partial permutation of a finite set \(S\)” means a list of length \(k\) whose entries are pairwise distinct and all belong to \(S\).

sage.combinat.permutation.StandardPermutations_all

All standard permutations.

class sage.combinat.permutation.StandardPermutations_avoiding_12(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

Return the cardinality of self.

EXAMPLES:

sage: P = Permutations(3, avoiding=[1, 2])
sage: P.cardinality()
1
class sage.combinat.permutation.StandardPermutations_avoiding_123(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[1, 2, 3]).cardinality()
42
sage: len( Permutations(5, avoiding=[1, 2, 3]).list() )
42
class sage.combinat.permutation.StandardPermutations_avoiding_132(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[1, 3, 2]).cardinality()
42
sage: len( Permutations(5, avoiding=[1, 3, 2]).list() )
42
class sage.combinat.permutation.StandardPermutations_avoiding_21(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

Return the cardinality of self.

EXAMPLES:

sage: P = Permutations(3, avoiding=[2, 1])
sage: P.cardinality()
1
class sage.combinat.permutation.StandardPermutations_avoiding_213(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[2, 1, 3]).cardinality()
42
sage: len( Permutations(5, avoiding=[2, 1, 3]).list() )
42
class sage.combinat.permutation.StandardPermutations_avoiding_231(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[2, 3, 1]).cardinality()
42
sage: len( Permutations(5, avoiding=[2, 3, 1]).list() )
42
class sage.combinat.permutation.StandardPermutations_avoiding_312(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[3, 1, 2]).cardinality()
42
sage: len( Permutations(5, avoiding=[3, 1, 2]).list() )
42
class sage.combinat.permutation.StandardPermutations_avoiding_321(n)

Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic

cardinality()

EXAMPLES:

sage: Permutations(5, avoiding=[3, 2, 1]).cardinality()
42
sage: len( Permutations(5, avoiding=[3, 2, 1]).list() )
42
sage.combinat.permutation.StandardPermutations_avoiding_generic

Generic class for subset of permutations avoiding a particular pattern.

sage.combinat.permutation.StandardPermutations_bruhat_greater

Permutations of \(\{1, \ldots, n\}\) that are greater than or equal to a permutation \(p\) in the Bruhat order.

sage.combinat.permutation.StandardPermutations_bruhat_smaller

Permutations of \(\{1, \ldots, n\}\) that are less than or equal to a permutation \(p\) in the Bruhat order.

sage.combinat.permutation.StandardPermutations_descents

Permutations of \(\{1, \ldots, n\}\) with a fixed set of descents.

sage.combinat.permutation.StandardPermutations_n

Permutations of the set \(\{1, 2, \ldots, n\}\).

These are also called permutations of size \(n\), or the elements of the \(n\)-th symmetric group.

Todo

Have a reduced_word() which works in both multiplication conventions.

sage.combinat.permutation.StandardPermutations_n_abstract

Abstract base class for subsets of permutations of the set \(\{1, 2, \ldots, n\}\).

Warning

Anything inheriting from this class should override the __contains__ method.

sage.combinat.permutation.StandardPermutations_recoils

Permutations of \(\{1, \ldots, n\}\) with a fixed recoils composition.

class sage.combinat.permutation.StandardPermutations_recoilsfatter(recoils)

Bases: sage.combinat.permutation.Permutations

class sage.combinat.permutation.StandardPermutations_recoilsfiner(recoils)

Bases: sage.combinat.permutation.Permutations

sage.combinat.permutation.bistochastic_as_sum_of_permutations(M, check=True)

Return the positive sum of permutations corresponding to the bistochastic matrix M.

A stochastic matrix is a matrix with nonnegative real entries such that the sum of the elements of any row is equal to \(1\). A bistochastic matrix is a stochastic matrix whose transpose matrix is also stochastic ( there are conditions both on the rows and on the columns ).

According to the Birkhoff-von Neumann Theorem, any bistochastic matrix can be written as a convex combination of permutation matrices, which also means that the polytope of bistochastic matrices is integer.

As a non-bistochastic matrix can obviously not be written as a convex combination of permutations, this theorem is an equivalence.

This function, given a bistochastic matrix, returns the corresponding decomposition.

INPUT:

  • M – A bistochastic matrix
  • check (boolean) – set to True (default) to check that the matrix is indeed bistochastic

OUTPUT:

  • An element of CombinatorialFreeModule, which is a free \(F\)-module ( where \(F\) is the ground ring of the given matrix ) whose basis is indexed by the permutations.

Note

  • In this function, we just assume 1 to be any constant : for us a matrix \(M\) is bistochastic if there exists \(c>0\) such that \(M/c\) is bistochastic.
  • You can obtain a sequence of pairs (permutation,coeff), where permutation is a Sage Permutation instance, and coeff its corresponding coefficient from the result of this function by applying the list function.
  • If you are interested in the matrix corresponding to a Permutation you will be glad to learn about the Permutation.to_matrix() method.
  • The base ring of the matrix can be anything that can be coerced to RR.

See also

  • as_sum_of_permutations() to use this method through the Matrix class.

EXAMPLES:

We create a bistochastic matrix from a convex sum of permutations, then try to deduce the decomposition from the matrix:

sage: from sage.combinat.permutation import bistochastic_as_sum_of_permutations
sage: L = []
sage: L.append((9,Permutation([4, 1, 3, 5, 2])))
sage: L.append((6,Permutation([5, 3, 4, 1, 2])))
sage: L.append((3,Permutation([3, 1, 4, 2, 5])))
sage: L.append((2,Permutation([1, 4, 2, 3, 5])))
sage: M = sum([c * p.to_matrix() for (c,p) in L])
sage: decomp = bistochastic_as_sum_of_permutations(M)
sage: print(decomp)
2*B[[1, 4, 2, 3, 5]] + 3*B[[3, 1, 4, 2, 5]] + 9*B[[4, 1, 3, 5, 2]] + 6*B[[5, 3, 4, 1, 2]]

An exception is raised when the matrix is not positive and bistochastic:

sage: M = Matrix([[2,3],[2,2]])
sage: decomp = bistochastic_as_sum_of_permutations(M)
Traceback (most recent call last):
...
ValueError: The matrix is not bistochastic

sage: bistochastic_as_sum_of_permutations(Matrix(GF(7), 2, [2,1,1,2]))
Traceback (most recent call last):
...
ValueError: The base ring of the matrix must have a coercion map to RR

sage: bistochastic_as_sum_of_permutations(Matrix(ZZ, 2, [2,-1,-1,2]))
Traceback (most recent call last):
...
ValueError: The matrix should have nonnegative entries
sage.combinat.permutation.bounded_affine_permutation(A)

Return the bounded affine permutation of a matrix.

The bounded affine permutation of a matrix \(A\) with entries in \(R\) is a partial permutation of length \(n\), where \(n\) is the number of columns of \(A\). The entry in position \(i\) is the smallest value \(j\) such that column \(i\) is in the span of columns \(i+1, \ldots, j\), over \(R\), where column indices are taken modulo \(n\). If column \(i\) is the zero vector, then the permutation has a fixed point at \(i\).

INPUT:

  • A – matrix with entries in a ring \(R\)

EXAMPLES:

sage: from sage.combinat.permutation import bounded_affine_permutation
sage: A = Matrix(ZZ, [[1,0,0,0], [0,1,0,0]])
sage: bounded_affine_permutation(A)
[5, 6, 3, 4]

sage: A = Matrix(ZZ, [[0,1,0,1,0], [0,0,1,1,0]])
sage: bounded_affine_permutation(A)
[1, 4, 7, 8, 5]

REFERENCES:

sage.combinat.permutation.bruhat_lequal(p1, p2)

Return True if p1 is less than p2 in the Bruhat order.

Algorithm from mupad-combinat.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.bruhat_lequal([2,4,3,1],[3,4,2,1])
True
sage.combinat.permutation.descents_composition_first(dc)

Compute the smallest element of a descent class having a descent composition dc.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.descents_composition_first([1,1,3,4,3])
[3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
sage.combinat.permutation.descents_composition_last(dc)

Return the largest element of a descent class having a descent composition dc.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.descents_composition_last([1,1,3,4,3])
[12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
sage.combinat.permutation.descents_composition_list(dc)

Return a list of all the permutations that have the descent composition dc.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.descents_composition_list([1,2,2])
[[5, 2, 4, 1, 3],
 [5, 3, 4, 1, 2],
 [4, 3, 5, 1, 2],
 [4, 2, 5, 1, 3],
 [3, 2, 5, 1, 4],
 [2, 1, 5, 3, 4],
 [3, 1, 5, 2, 4],
 [4, 1, 5, 2, 3],
 [5, 1, 4, 2, 3],
 [5, 1, 3, 2, 4],
 [4, 1, 3, 2, 5],
 [3, 1, 4, 2, 5],
 [2, 1, 4, 3, 5],
 [3, 2, 4, 1, 5],
 [4, 2, 3, 1, 5],
 [5, 2, 3, 1, 4]]
sage.combinat.permutation.from_cycles(n, cycles, parent=None)

Return the permutation in the \(n\)-th symmetric group whose decomposition into disjoint cycles is cycles.

This function checks that its input is correct (i.e. that the cycles are disjoint and their elements integers among \(1...n\)). It raises an exception otherwise.

Warning

It assumes that the elements are of int type.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.from_cycles(4, [[1,2]])
[2, 1, 3, 4]
sage: permutation.from_cycles(4, [[1,2,4]])
[2, 4, 3, 1]
sage: permutation.from_cycles(10, [[3,1],[4,5],[6,8,9]])
[3, 2, 1, 5, 4, 8, 7, 9, 6, 10]
sage: permutation.from_cycles(10, ((2, 5), (6, 1, 3)))
[3, 5, 6, 4, 2, 1, 7, 8, 9, 10]
sage: permutation.from_cycles(4, [])
[1, 2, 3, 4]
sage: permutation.from_cycles(4, [[]])
[1, 2, 3, 4]
sage: permutation.from_cycles(0, [])
[]

Bad input (see trac ticket #13742):

sage: Permutation("(-12,2)(3,4)")
Traceback (most recent call last):
...
ValueError: All elements should be strictly positive integers, and I just found a non-positive one.
sage: Permutation("(1,2)(2,4)")
Traceback (most recent call last):
...
ValueError: An element appears twice. It should not.
sage: permutation.from_cycles(4, [[1,18]])
Traceback (most recent call last):
...
ValueError: You claimed that this was a permutation on 1...4 but it contains 18
sage.combinat.permutation.from_inversion_vector(iv, parent=None)

Return the permutation corresponding to inversion vector iv.

See \(~sage.combinat.permutation.Permutation.to_inversion_vector\) for a definition of the inversion vector of a permutation.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.from_inversion_vector([3,1,0,0,0])
[3, 2, 4, 1, 5]
sage: permutation.from_inversion_vector([2,3,6,4,0,2,2,1,0])
[5, 9, 1, 8, 2, 6, 4, 7, 3]
sage: permutation.from_inversion_vector([0])
[1]
sage: permutation.from_inversion_vector([])
[]
sage.combinat.permutation.from_lehmer_code(lehmer, parent=None)

Return the permutation with Lehmer code lehmer.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: lc = Permutation([2,1,5,4,3]).to_lehmer_code(); lc
[1, 0, 2, 1, 0]
sage: permutation.from_lehmer_code(lc)
[2, 1, 5, 4, 3]
sage.combinat.permutation.from_major_code(mc, final_descent=False)

Return the permutation with major code mc.

The major code of a permutation is defined in to_major_code().

Warning

This function creates illegal permutations (i.e. Permutation([9]), and this is dangerous as the Permutation() class is only designed to handle permutations on \(1...n\). This will have to be changed when Sage permutations will be able to handle anything, but right now this should be fixed. Be careful with the results.

Warning

If mc is not a major index of a permutation, then the return value of this method can be anything. Garbage in, garbage out!

REFERENCES:

  • Skandera, M. An Eulerian Partner for Inversions. Sem. Lothar. Combin. 46 (2001) B46d.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.from_major_code([5, 0, 1, 0, 1, 2, 0, 1, 0])
[9, 3, 5, 7, 2, 1, 4, 6, 8]
sage: permutation.from_major_code([8, 3, 3, 1, 4, 0, 1, 0, 0])
[2, 8, 4, 3, 6, 7, 9, 5, 1]
sage: Permutation([2,1,6,4,7,3,5]).to_major_code()
[3, 2, 0, 2, 2, 0, 0]
sage: permutation.from_major_code([3, 2, 0, 2, 2, 0, 0])
[2, 1, 6, 4, 7, 3, 5]
sage.combinat.permutation.from_permutation_group_element(pge, parent=None)

Return a Permutation given a PermutationGroupElement pge.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: pge = PermutationGroupElement([(1,2),(3,4)])
sage: permutation.from_permutation_group_element(pge)
[2, 1, 4, 3]
sage.combinat.permutation.from_rank(n, rank)

Return the permutation of the set \(\{1,...,n\}\) with lexicographic rank rank. This is the permutation whose Lehmer code is the factoradic representation of rank. In particular, the permutation with rank \(0\) is the identity permutation.

The permutation is computed without iterating through all of the permutations with lower rank. This makes it efficient for large permutations.

Note

The variable rank is not checked for being in the interval from \(0\) to \(n! - 1\). When outside this interval, it acts as its residue modulo \(n!\).

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: Permutation([3, 6, 5, 4, 2, 1]).rank()
359
sage: [permutation.from_rank(3, i) for i in range(6)]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: Permutations(6)[10]
[1, 2, 4, 6, 3, 5]
sage: permutation.from_rank(6,10)
[1, 2, 4, 6, 3, 5]
sage.combinat.permutation.from_reduced_word(rw, parent=None)

Return the permutation corresponding to the reduced word rw.

See reduced_words() for a definition of reduced words and the convention on the order of multiplication used.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.from_reduced_word([3,2,3,1,2,3,1])
[3, 4, 2, 1]
sage: permutation.from_reduced_word([])
[]
sage.combinat.permutation.permutohedron_lequal(p1, p2, side='right')

Return True if p1 is less than 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.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.permutohedron_lequal(Permutation([3,2,1,4]),Permutation([4,2,1,3]))
False
sage: permutation.permutohedron_lequal(Permutation([3,2,1,4]),Permutation([4,2,1,3]), side='left')
True
sage.combinat.permutation.to_standard(p, key=None)

Return a standard permutation corresponding to the iterable p.

INPUT:

  • p – an iterable
  • key – (optional) a comparison key for the element x of p

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.to_standard([4,2,7])
[2, 1, 3]
sage: permutation.to_standard([1,2,3])
[1, 2, 3]
sage: permutation.to_standard([])
[]
sage: permutation.to_standard([1,2,3], key=lambda x: -x)
[3, 2, 1]
sage: permutation.to_standard([5,8,2,5], key=lambda x: -x)
[2, 1, 4, 3]