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
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.
- (2012-08-16):
- 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 withSymmetricGroup
. 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 frommset
, but maybe in a different order.Arrangements
returns the combinatorial class of arrangements of the multisetmset
that containk
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.
- an instance of
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 settingcheck_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 methodsleft_action_product()
andright_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 underpermutohedron*
.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 aPermutationGroupElement
: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
withlp
in such an order thatlp
is applied first andself
is applied afterwards.This is usually denoted by either
self * lp
orlp * 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 byself * 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 bylp * 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
withrp
in such an order thatself
is applied first andrp
is applied afterwards.This is usually denoted by either
self * rp
orrp * 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 byrp * 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 byself * 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 ofn
, ifn
is an integer, list, set, or string.Permutations(n, k)
returns the class of length-k
partial permutations ofn
(wheren
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
ork
along with a keyword.Permutations(descents=(list,n))
returns the class of permutations of \(n\) with descents in the positions specified bylist
. 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\) inlist
signifies that the permutations \(\pi\) should satisfy \(\pi(2) > \pi(3)\). Note thatlist
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 compositionlist
.Permutations(bruhat_smaller=p)
andPermutations(bruhat_greater=p)
return the class of permutations smaller-or-equal or greater-or-equal, respectively, than the given permutationp
in the Bruhat order. (The Bruhat order is defined inbruhat_lequal()
. It is also referred to as the strong Bruhat order.)Permutations(recoils=p)
returns the class of permutations whose recoils composition isp
. Unlike thedescents=(list, n)
syntax, this actually takes a composition as input.Permutations(recoils_fatter=p)
andPermutations(recoils_finer=p)
return the class of permutations whose recoils composition is fatter or finer, respectively, than the given compositionp
.Permutations(n, avoiding=P)
returns the class of permutations ofn
avoidingP
. HereP
may be a single permutation or a list of permutations; the returned class will avoid all patterns inP
.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)¶
-
class
sage.combinat.permutation.
StandardPermutations_recoilsfiner
(recoils)¶
-
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 matrixcheck
(boolean) – set toTrue
(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)
, wherepermutation
is a SagePermutation
instance, andcoeff
its corresponding coefficient from the result of this function by applying thelist
function. - If you are interested in the matrix corresponding to a
Permutation
you will be glad to learn about thePermutation.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 theMatrix
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
ifp1
is less thanp2
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 thePermutation()
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 aPermutationGroupElement
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 ofrank
. 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
ifp1
is less than or equal top2
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 iterablekey
– (optional) a comparison key for the elementx
ofp
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]