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 trough 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
PermutationOptions
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 ![]() |
destandardization() |
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_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 ![]() ![]() |
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 ![]() self with ![]() |
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 ![]() |
retract_direct_product() |
Returns the direct-product retract of self to a smaller symmetric group ![]() |
retract_okounkov_vershik() |
Returns the Okounkov-Vershik retract of self to a smaller symmetric group ![]() |
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. |
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
- Sebastien Labbe (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¶
-
class
sage.combinat.permutation.
Arrangements
¶ Bases:
sage.combinat.permutation.Permutations
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']]
-
cardinality
()¶ Return the cardinality of
self
.EXAMPLES:
sage: A = Arrangements([1,1,2,3,4,4,5], 2) sage: A.cardinality() 22
-
-
class
sage.combinat.permutation.
Arrangements_msetk
(mset, k)¶ Bases:
sage.combinat.permutation.Arrangements
,sage.combinat.permutation.Permutations_msetk
Arrangements of length
of a multiset
.
-
class
sage.combinat.permutation.
Arrangements_setk
(s, k)¶ Bases:
sage.combinat.permutation.Arrangements
,sage.combinat.permutation.Permutations_setk
Arrangements of length
of a set
.
-
class
sage.combinat.permutation.
CyclicPermutations
(mset)¶ Bases:
sage.combinat.permutation.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: 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]]
-
iterator
(distinct=False)¶ EXAMPLES:
sage: CyclicPermutations(range(4)).list() # indirect doctest [[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: CyclicPermutations([1,1,1]).list(distinct=True) [[1, 1, 1], [1, 1, 1]]
-
list
(distinct=False)¶ 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]]
-
class
sage.combinat.permutation.
CyclicPermutationsOfPartition
(partition)¶ Bases:
sage.combinat.permutation.Permutations
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
Element
¶ Bases:
sage.structure.list_clone.ClonableArray
A cyclic permutation of a partition.
-
check
()¶ Check that
self
is a valid element.EXAMPLES:
sage: CP = CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]) sage: elt = CP[0] sage: elt.check()
-
-
CyclicPermutationsOfPartition.
iterator
(distinct=False)¶ AUTHORS:
- Robert Miller
EXAMPLES:
sage: CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]).list() # indirect doctest [[[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]]]
-
CyclicPermutationsOfPartition.
list
(distinct=False)¶ EXAMPLES:
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.
CyclicPermutationsOfPartition_partition
(partition)¶ EXAMPLES:
sage: sage.combinat.permutation.CyclicPermutationsOfPartition_partition([[1,2,3,4],[5,6,7]]) doctest:...: DeprecationWarning: this class is deprecated. Use sage.combinat.permutation.CyclicPermutationsOfPartition instead See http://trac.sagemath.org/14772 for details. Cyclic permutations of partition [[1, 2, 3, 4], [5, 6, 7]]
-
sage.combinat.permutation.
CyclicPermutations_mset
(partition)¶ EXAMPLES:
sage: sage.combinat.permutation.CyclicPermutations_mset(range(4)) doctest:...: DeprecationWarning: this class is deprecated. Use sage.combinat.permutation.CyclicPermutations instead See http://trac.sagemath.org/14772 for details. Cyclic permutations of [0, 1, 2, 3]
-
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...>
-
class
sage.combinat.permutation.
Permutation
(parent, l, check_input=True)¶ Bases:
sage.combinat.combinat.CombinatorialElement
A permutation.
Converts
l
to a permutation on.
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. Slowsthe 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
. 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
for any permutations
and
and any
. (This equation looks less strange when the action of permutations on numbers is written from the right: then it takes the form
, which is an associativity law). There is an alternative convention, which has
instead. The conventions can be switched at runtime using
sage.combinat.permutation.Permutations.global_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]
TESTS:
sage: Permutation([()]) [] sage: Permutation('()') [] sage: Permutation(()) [] sage: Permutation( [1] ) [1]
From a pair of empty tableaux
sage: Permutation( ([], []) ) [] sage: Permutation( [[], []] ) []
-
_left_to_right_multiply_on_right
(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 permutationon an integer
is denoted by
, then this should be denoted by
rp * self
in order to have associativity (i.e., in order to havefor all
,
and
). If, on the other hand, the value of a permutation
on an integer
is denoted by
, then this should be denoted by
self * rp
in order to have associativity (i.e., in order to havefor all
,
and
).
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]
-
_left_to_right_multiply_on_left
(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 permutationon an integer
is denoted by
, then this should be denoted by
self * lp
in order to have associativity (i.e., in order to havefor all
,
and
). If, on the other hand, the value of a permutation
on an integer
is denoted by
, then this should be denoted by
lp * self
in order to have associativity (i.e., in order to havefor all
,
and
).
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]
-
RS_partition
()¶ Return the shape of the tableaux obtained by applying the RSK algorithm to
self
.EXAMPLES:
sage: Permutation([1,4,3,2]).RS_partition() [2, 1, 1]
-
action
(a)¶ Return the action of the permutation
self
on a lista
.The action of a permutation
on an
-element list
is defined to be
.
EXAMPLES:
sage: p = Permutation([2,1,3]) sage: a = 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 = range(3) sage: q.action(a) [1, 2, 0]
-
avoids
(patt)¶ Test whether the permutation
self
avoids the patternpatt
.EXAMPLES:
sage: Permutation([6,2,5,4,3,1]).avoids([4,2,3,1]) False sage: Permutation([6,1,2,5,4,3]).avoids([4,2,3,1]) True sage: Permutation([6,1,2,5,4,3]).avoids([3,4,1,2]) True
-
binary_search_tree
(left_to_right=True)¶ Return the binary search tree associated to
self
.If
is a word, then the binary search tree associated to
is defined as the result of starting with an empty binary tree, and then inserting the letters of
one by one into this tree. Here, the insertion is being done according to the method
binary_search_insert()
, and the wordis 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 toFalse
, the wordis being traversed from right to left instead.
EXAMPLES:
sage: Permutation([1,4,3,2]).binary_search_tree() 1[., 4[3[2[., .], .], .]] sage: Permutation([4,1,3,2]).binary_search_tree() 4[1[., 3[2[., .], .]], .]
By passing the option
left_to_right=False
one can have the insertion going from right to left:sage: Permutation([1,4,3,2]).binary_search_tree(False) 2[1[., .], 3[., 4[., .]]] sage: Permutation([4,1,3,2]).binary_search_tree(False) 2[1[., .], 3[., 4[., .]]]
TESTS:
sage: Permutation([]).binary_search_tree() .
-
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: Permutation([1,4,3,2]).binary_search_tree_shape() [., [[[., .], .], .]] sage: Permutation([4,1,3,2]).binary_search_tree_shape() [[., [[., .], .]], .]
By passing the option
left_to_right=False
one can have the insertion going from right to left:sage: Permutation([1,4,3,2]).binary_search_tree_shape(False) [[., .], [., [., .]]] sage: Permutation([4,1,3,2]).binary_search_tree_shape(False) [[., .], [., [., .]]]
-
bruhat_greater
()¶ Returns the combinatorial class of permutations greater than or equal to
self
in the Bruhat order (on the symmetric group containingself
).See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
bruhat_inversions
()¶ Return the list of inversions of
self
such that the application of this inversion toself
decreases its number of inversions by exactly 1.Equivalently, it returns the list of pairs
such that
, such that
and such that there exists no
(strictly) between
and
satisfying
.
EXAMPLES:
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]]
-
bruhat_inversions_iterator
()¶ Return the iterator for the inversions of
self
such that the application of this inversion toself
decreases its number of inversions by exactly 1.EXAMPLES:
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]]
-
bruhat_lequal
(p2)¶ Return
True
ifself
is less or equal top2
in the Bruhat order.The Bruhat order (also called strong Bruhat order or Chevalley order) on the symmetric group
is the partial order on
determined by the following condition: If
is a permutation, and
and
are two indices satisfying
and
(that is,
is an inversion of
with
), then
(the permutation obtained by first switching
with
and then applying
) is smaller than
in the Bruhat order.
One can show that a permutation
is less or equal to a permutation
in the Bruhat order if and only if for every
and
, the number of the elements among
that are greater than
is
to the number of the elements among
that are greater than
.
This method assumes that
self
andp2
are permutations of the same integer.
EXAMPLES:
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
-
bruhat_pred
()¶ Return a list of the permutations strictly smaller than
self
in the Bruhat order (on the symmetric group containingself
) such that there is no permutation between one of those andself
.See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
bruhat_pred_iterator
()¶ An iterator for the permutations strictly smaller than
self
in the Bruhat order (on the symmetric group containingself
) such that there is no permutation between one of those andself
.See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
bruhat_smaller
()¶ Return the combinatorial class of permutations smaller than or equal to
self
in the Bruhat order (on the symmetric group containingself
).See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
bruhat_succ
()¶ Return a list of the permutations strictly greater than
self
in the Bruhat order (on the symmetric group containingself
) such that there is no permutation between one of those andself
.See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
bruhat_succ_iterator
()¶ An iterator for the permutations that are strictly greater than
self
in the Bruhat order (on the symmetric group containingself
) such that there is no permutation between one of those andself
.See
bruhat_lequal()
for the definition of the Bruhat order.EXAMPLES:
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]]
-
complement
()¶ Return the complement of the permutation
self
.The complement of a permutation
is defined as the permutation in
sending each
to
.
EXAMPLES:
sage: Permutation([1,2,3]).complement() [3, 2, 1] sage: Permutation([1, 3, 2]).complement() [3, 1, 2]
-
cycle_string
(singletons=False)¶ Returns a string of the permutation in cycle notation.
If
singletons=True
, it includes 1-cycles in the string.EXAMPLES:
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)'
-
cycle_tuples
(singletons=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.EXAMPLES:
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([4,1,5,2,6,3]).to_cycles() [(1, 4, 2), (3, 5, 6)]
The algorithm is of complexity
where
is the size of the given permutation.
TESTS:
sage: from sage.combinat.permutation import from_cycles sage: for n in range(1,6): ....: for p in Permutations(n): ....: if from_cycles(n, p.to_cycles()) != p: ....: print "There is a problem with ",p ....: break sage: size = 10000 sage: sample = (Permutations(size).random_element() for i in range(5)) sage: all(from_cycles(size, p.to_cycles()) == p for p in sample) True
Note: there is an alternative implementation called
_to_cycle_set
which could be slightly (10%) faster for some input (typically for permutations of size in the range [100, 10000]). You can run the following benchmarks. For small permutations:sage: for size in range(9): # not tested ....: print size ....: lp = Permutations(size).list() ....: timeit('[p.to_cycles(False) for p in lp]') ....: timeit('[p._to_cycles_set(False) for p in lp]') ....: timeit('[p._to_cycles_list(False) for p in lp]') ....: timeit('[p._to_cycles_orig(False) for p in lp]')
and larger ones:
sage: for size in [10, 20, 50, 75, 100, 200, 500, 1000, # not tested ....: 2000, 5000, 10000, 15000, 20000, 30000, ....: 50000, 80000, 100000]: ....: print(size) ....: lp = [Permutations(size).random_element() for i in range(20)] ....: timeit("[p.to_cycles() for p in lp]") ....: timeit("[p._to_cycles_set() for p in lp]") ....: timeit("[p._to_cycles_list() for p in lp]")
-
cycle_type
()¶ Return a partition of
len(self)
corresponding to the cycle type ofself
. This is a non-increasing sequence of the cycle lengths ofself
.EXAMPLES:
sage: Permutation([3,1,2,4]).cycle_type() [3, 1]
-
decreasing_runs
(as_tuple=False)¶ Decreasing runs of the permutation.
INPUT:
as_tuple
– boolean (default:False
) choice of output format
OUTPUT:
a list of lists or a tuple of tuples
See also
EXAMPLES:
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,))
-
descent_polynomial
()¶ Return the descent polynomial of the permutation
self
.The descent polynomial of a permutation
is the product of all the
z[p[i]]
wherei
ranges over the descents ofp
.A descent of a permutation
p
is an integeri
such thatp[i] > p[i+1]
. Here, Python’s indexing convention is used, sop[i]
means.
REFERENCES:
[GarStan1984] A. M. Garsia, Dennis Stanton. Group actions on Stanley-Reisner rings and invariants of permutation groups. Adv. in Math. 51 (1984), 107-201. http://www.sciencedirect.com/science/article/pii/0001870884900057 EXAMPLES:
sage: Permutation([2,1,3]).descent_polynomial() z1 sage: Permutation([4,3,2,1]).descent_polynomial() z1*z2^2*z3^3
Todo
This docstring needs to be fixed. First, the definition does not match the implementation (or the examples). Second, this doesn’t seem to be defined in [GarStan1984] (the descent monomial in their (7.23) is different).
-
descents
(final_descent=False)¶ Return the list of the descents of
self
.A descent of a permutation
p
is an integeri
such thatp[i] > p[i+1]
. Here, Python’s indexing convention is used, sop[i]
means.
With the
final_descent
option, the last position of a non-empty permutation is also considered as a descent.EXAMPLES:
sage: Permutation([3,1,2]).descents() [0] sage: Permutation([1,4,3,2]).descents() [1, 2] sage: Permutation([1,4,3,2]).descents(final_descent=True) [1, 2, 3]
-
descents_composition
()¶ Return the descent composition of
self
.The descent composition of a permutation
is defined as the composition of
whose descent set equals the descent set of
. Here, the descent set of
is defined as the set of all
satisfying
(note that this differs from the output of the
descents()
method, since the latter uses Python’s indexing which starts atinstead of
). The descent set of a composition
is defined as the set
.
EXAMPLES:
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() []
-
destandardize
(weight, ordered_alphabet=None)¶ Return destandardization of
self
with respect toweight
andordered_alphabet
.INPUT:
weight
– list or tuple of nonnegative integers that sum toif
self
is a permutation in.
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 toself
Let
. Then this methods looks for an increasing sequence of
and labels all letters in it by 1, then an increasing sequence of
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 wordw
over the specified ordered alphabet with evaluationweight
such thatw.standard_permutation()
isself
.EXAMPLES:
sage: p = Permutation([1,2,5,3,6,4]) sage: p.destandardize([3,1,2]) 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!
TESTS:
sage: p = Permutation([4,1,2,3,5,6]) sage: p.destandardize([2,1,3], ordered_alphabet = [1,'a',3]) word: 311a33 sage: p.destandardize([2,1,3], ordered_alphabet = [1,'a']) Traceback (most recent call last): ... ValueError: Not enough letters in the alphabet are specified compared to the weight
-
dict
()¶ Returns a dictionary corresponding to the permutation.
EXAMPLES:
sage: p = Permutation([2,1,3]) sage: d = p.dict() sage: d[1] 2 sage: d[2] 1 sage: d[3] 3
-
fixed_points
()¶ Return a list of the fixed points of
self
.EXAMPLES:
sage: Permutation([1,3,2,4]).fixed_points() [1, 4] sage: Permutation([1,2,3,4]).fixed_points() [1, 2, 3, 4]
-
foata_bijection
()¶ Return the image of the permutation
self
under the Foata bijection.
The bijection shows that
and
are equidistributed: if
, then
.
The Foata bijection
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
, start with
. At the
-th step, if
, we define
by placing
on the end of the word
and breaking the word up into blocks as follows. If
, place a vertical line to the right of each
for which
. Otherwise, if
, place a vertical line to the right of each
for which
. 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
, the sequence of words is
,
,
,
,
.
So
.
See section 2 of [FoSc78].
REFERENCES:
[FoSc78] (1, 2) Dominique Foata, Marcel-Paul Schuetzenberger. Major Index and Inversion Number of Permutations. Mathematische Nachrichten, volume 83, Issue 1, pages 143-159, 1978. http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1978-3MajorIndexMathNachr.pdf EXAMPLES:
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
The example from [FoSc78]:
sage: Permutation([7,4,9,2,6,1,5,8,3]).foata_bijection() [4, 7, 2, 6, 1, 9, 5, 8, 3]
Border cases:
sage: Permutation([]).foata_bijection() [] sage: Permutation([1]).foata_bijection() [1]
-
forget_cycles
()¶ Return the image of
self
under the map which forgets cycles.Consider a permutation
written in standard cyclic form:
where
and
for all
and
where we include cycles of length 1 as well. The image of the forget cycle map
is given by
considered as a permutation in 1-line notation.
EXAMPLES:
sage: P = Permutations(5) sage: x = P([1, 5, 3, 4, 2]) sage: x.forget_cycles() [1, 2, 5, 3, 4]
We select all permutations with a cycle composition of
in
:
sage: P = Permutations(6) sage: l = [p for p in P if [len(t) for t in p.to_cycles()] == [1,3,2]]
Next we apply
and then take the inverse, and then view the results as a poset under the Bruhat order:
sage: l = [p.forget_cycles().inverse() for p in l] sage: B = Poset([l, lambda x,y: x.bruhat_lequal(y)]) sage: R.<q> = QQ[] sage: sum(q^B.rank_function()(x) for x in B) q^5 + 2*q^4 + 3*q^3 + 3*q^2 + 2*q + 1
We check the statement in [CC13] that the posets
and
are isomorphic:
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)]) sage: B.is_isomorphic(B2) True
REFERENCES:
[CC13] Mahir Bilen Can and Yonah Cherniavsky. Omitting parentheses from the cyclic notation. (2013). Arxiv 1308.0936v2.
-
has_pattern
(patt)¶ Test whether the permutation
self
contains the patternpatt
.EXAMPLES:
sage: Permutation([3,5,1,4,6,2]).has_pattern([1,3,2]) True
-
hyperoctahedral_double_coset_type
()¶ Return the coset-type of
self
as a partition.self
must be a permutation of even size. The coset-type determines the double class of the permutation, that is its image in
, where
is the
-th hyperoctahedral group.
The coset-type is determined as follows. Consider the perfect matching
and its image by
self
, and draw them simultaneously as edges of a graph whose vertices are labeled by. The coset-type is the ordered sequence of the semi-lengths of the cycles of this graph (see Chapter VII of [Mcd] for more details, particularly Section VII.2).
EXAMPLE:
sage: Permutation([3, 4, 6, 1, 5, 7, 2, 8]).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
REFERENCES:
[Mcd] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford University Press, second edition, 1995.
-
idescents
(final_descent=False)¶ Return a list of the idescents of
self
, that is the list of the descents ofself
‘s inverse.A descent of a permutation
p
is an integeri
such thatp[i] > p[i+1]
. Here, Python’s indexing convention is used, sop[i]
means.
With the
final_descent
option, the last position of a non-empty permutation is also considered as a descent.EXAMPLES:
sage: Permutation([2,3,1]).idescents() [0] sage: Permutation([1,4,3,2]).idescents() [1, 2] sage: Permutation([1,4,3,2]).idescents(final_descent=True) [1, 2, 3]
-
idescents_signature
(final_descent=False)¶ Return the list obtained as follows: Each position in
self
is mapped toif it is an idescent and
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: Permutation([1,4,3,2]).idescents() [1, 2] sage: Permutation([1,4,3,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 ofself
.The major index of a permutation
is the sum of the descents of
. 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: 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
-
increasing_tree
(compare=<built-in function min>)¶ Return the increasing tree associated to
self
.EXAMPLES:
sage: Permutation([1,4,3,2]).increasing_tree() 1[., 2[3[4[., .], .], .]] sage: Permutation([4,1,3,2]).increasing_tree() 1[4[., .], 2[3[., .], .]]
By passing the option
compare=max
one can have the decreasing tree instead:sage: Permutation([2,3,4,1]).increasing_tree(max) 4[3[2[., .], .], 1[., .]] sage: Permutation([2,3,1,4]).increasing_tree(max) 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: Permutation([1,4,3,2]).increasing_tree_shape() [., [[[., .], .], .]] sage: Permutation([4,1,3,2]).increasing_tree_shape() [[., .], [[., .], .]]
By passing the option
compare=max
one can have the decreasing tree instead:sage: Permutation([2,3,4,1]).increasing_tree_shape(max) [[[., .], .], [., .]] sage: Permutation([2,3,1,4]).increasing_tree_shape(max) [[[., .], [., .]], .]
-
inverse
()¶ Return the inverse of
self
.EXAMPLES:
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]
-
inversions
()¶ Return a list of the inversions of
self
.An inversion of a permutation
is a pair
such that
and
.
EXAMPLES:
sage: Permutation([3,2,4,1,5]).inversions() [(1, 2), (1, 4), (2, 4), (3, 4)]
-
is_even
()¶ Return
True
if the permutationself
is even andFalse
otherwise.EXAMPLES:
sage: Permutation([1,2,3]).is_even() True sage: Permutation([2,1,3]).is_even() False
-
ishift
(i)¶ Return the
i
-shift ofself
. If ani
-shift ofself
can’t be performed, thenself
is returned.An
-shift can be applied when
is not inbetween
and
. The
-shift moves
to the other side, and leaves the relative positions of
and
in place. All other entries of the permutations are also left in place.
EXAMPLES:
Here,
is to the left of both
and
. A
-shift can be applied which moves the
to the right and leaves
and
in their same relative order:
sage: Permutation([2,1,3]).ishift(2) [1, 3, 2]
All entries other than
,
and
are unchanged:
sage: Permutation([2,4,1,3]).ishift(2) [1, 4, 3, 2]
Since
is between
and
in
[1,2,3]
, a-shift cannot be applied to
[1,2,3]
sage: Permutation([1,2,3]).ishift(2) [1, 2, 3]
-
iswitch
(i)¶ Return the
i
-switch ofself
. If ani
-switch ofself
can’t be performed, thenself
is returned.An
-switch can be applied when the subsequence of
self
formed by the entries,
and
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,
is to the left of both
and
. A
-switch can be applied which moves the
to the right and switches the relative order between
and
:
sage: Permutation([2,1,3]).iswitch(2) [3, 1, 2]
All entries other than
,
and
are unchanged:
sage: Permutation([2,4,1,3]).iswitch(2) [3, 4, 1, 2]
Since
is between
and
in
[1,2,3]
, a-switch cannot be applied to
[1,2,3]
sage: Permutation([1,2,3]).iswitch(2) [1, 2, 3]
-
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 permutationon an integer
is denoted by
, then this should be denoted by
self * lp
in order to have associativity (i.e., in order to havefor all
,
and
). If, on the other hand, the value of a permutation
on an integer
is denoted by
, then this should be denoted by
lp * self
in order to have associativity (i.e., in order to havefor all
,
and
).
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]
-
left_tableau
()¶ Return the left standard tableau after performing the RSK algorithm on
self
.EXAMPLES:
sage: Permutation([1,4,3,2]).left_tableau() [[1, 2], [3], [4]]
-
length
()¶ Return the Coxeter length of
self
.The length of a permutation
is given by the number of inversions of
.
EXAMPLES:
sage: Permutation([5, 1, 3, 4, 2]).length() 6
-
longest_increasing_subsequence_length
()¶ Return the length of the longest increasing subsequences of
self
.EXAMPLES:
sage: Permutation([2,3,1,4]).longest_increasing_subsequence_length() 3 sage: all([i.longest_increasing_subsequence_length() == len(RSK(i)[0][0]) for i in Permutations(5)]) True sage: Permutation([]).longest_increasing_subsequence_length() 0
-
longest_increasing_subsequences
()¶ Return the list of the longest increasing subsequences of
self
.Note
The algorithm is not optimal.
EXAMPLES:
sage: Permutation([2,3,4,1]).longest_increasing_subsequences() [[2, 3, 4]] sage: Permutation([5, 7, 1, 2, 6, 4, 3]).longest_increasing_subsequences() [[1, 2, 6], [1, 2, 4], [1, 2, 3]]
-
major_index
(final_descent=False)¶ Return the major index of
self
.The major index of a permutation
is the sum of the descents of
. 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: 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
-
next
()¶ Return the permutation that follows
self
in lexicographic order on the symmetric group containingself
. Ifself
is the last permutation, thennext
returnsFalse
.EXAMPLES:
sage: p = Permutation([1, 3, 2]) sage: next(p) [2, 1, 3] sage: p = Permutation([4,3,2,1]) sage: next(p) False
TESTS:
sage: p = Permutation([]) sage: next(p) False
-
noninversions
(k)¶ Return the list of all
k
-noninversions inself
.If
is an integer and
is a permutation, then a
-noninversion in
is defined as a strictly increasing sequence
of elements of
satisfying
. (In other words, a
-noninversion in
can be regarded as a
-element subset of
on which
restricts to an increasing map.)
EXAMPLES:
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) []
TESTS:
sage: q = Permutation([]) sage: q.noninversions(1) []
-
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: Permutation([1,4,3,2]).number_of_descents() 2 sage: Permutation([1,4,3,2]).number_of_descents(final_descent=True) 3
-
number_of_fixed_points
()¶ Return the number of fixed points of
self
.EXAMPLES:
sage: Permutation([1,3,2,4]).number_of_fixed_points() 2 sage: Permutation([1,2,3,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: Permutation([1,4,3,2]).number_of_idescents() 2 sage: Permutation([1,4,3,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
with
and
.
REFERENCES:
EXAMPLES:
sage: Permutation([3, 2, 4, 1, 5]).number_of_inversions() 4 sage: Permutation([1, 2, 6, 4, 7, 3, 5]).number_of_inversions() 6
-
number_of_noninversions
(k)¶ Return the number of
k
-noninversions inself
.If
is an integer and
is a permutation, then a
-noninversion in
is defined as a strictly increasing sequence
of elements of
satisfying
. (In other words, a
-noninversion in
can be regarded as a
-element subset of
on which
restricts to an increasing map.)
The number of
-noninversions in
has been denoted by
in [RSW2011], where conjectures and results regarding this number have been stated.
REFERENCES:
[RSW2011] Victor Reiner, Franco Saliola, Volkmar Welker. Spectra of Symmetrized Shuffling Operators. Arxiv 1102.2460v2. EXAMPLES:
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
The number of
-noninversions of a permutation
is
minus its number of inversions:
sage: b = binomial(5, 2) sage: all( x.number_of_noninversions(2) == b - x.number_of_inversions() ....: for x in Permutations(5) ) True
We also check some corner cases:
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
-
number_of_peaks
()¶ Return the number of peaks of the permutation
self
.A peak of a permutation
is an integer
such that
and
.
EXAMPLES:
sage: Permutation([1,3,2,4,5]).number_of_peaks() 1 sage: Permutation([4,1,3,2,6,5]).number_of_peaks() 2
-
number_of_recoils
()¶ Return the number of recoils of the permutation
self
.EXAMPLES:
sage: Permutation([1,4,3,2]).number_of_recoils() 2
-
number_of_saliances
()¶ Return the number of saliances of
self
.A saliance of a permutation
is an integer
such that
for all
.
EXAMPLES:
sage: Permutation([2,3,1,5,4]).number_of_saliances() 2 sage: Permutation([5,4,3,2,1]).number_of_saliances() 5
-
pattern_positions
(patt)¶ Return the list of positions where the pattern
patt
appears in the permutationself
.EXAMPLES:
sage: Permutation([3,5,1,4,6,2]).pattern_positions([1,3,2]) [[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
is an integer
such that
and
.
EXAMPLES:
sage: Permutation([1,3,2,4,5]).peaks() [1] sage: Permutation([4,1,3,2,6,5]).peaks() [2, 4] sage: Permutation([]).peaks() []
-
permutation_poset
()¶ Return the permutation poset of
self
.The permutation poset of a permutation
is the poset with vertices
for
(where
is the size of
) and order inherited from
.
EXAMPLES:
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]) sage: P.permutation_poset().greene_shape() == P.RS_partition() # This should hold for any P. 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: 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]]
-
permutohedron_join
(other, side='right')¶ Return the join of the permutations
self
andother
in the right permutohedron order (or, ifside
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 permutationsand
in the symmetric group
is the permutation in
whose set of inversion is the transitive closure of the union of the set of inversions of
with the set of inversions of
.
See also
ALGORITHM:
It is enough to construct the join of any two permutations
and
in
with respect to the right weak order. (The join of
and
with respect to the left weak order is the inverse of the join of
and
with respect to the right weak order.) Start with an empty list
(denoted
xs
in the actual code). For(in this order), we insert
into this list in the rightmost possible position such that any letter in
which appears further right than
in either
or
(or both) must appear further right than
in the resulting list. After all numbers are inserted, we are left with a list which is precisely the join of
and
(in one-line notation). This algorithm is due to Markowsky, [Mark94] (Theorem 1 (a)).
REFERENCES:
[Mark94] George Markowsky. Permutation lattices revisited. Mathematical Social Sciences, 27 (1994), 59–72. AUTHORS:
Viviane Pons and Darij Grinberg, 18 June 2014.
EXAMPLES:
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]
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]
The universal property of the join operation is satisfied:
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
Border cases:
sage: p = Permutation([]) sage: p.permutohedron_join(p) [] sage: p = Permutation([1]) sage: p.permutohedron_join(p) [1]
The left permutohedron:
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]
-
permutohedron_lequal
(p2, side='right')¶ Return
True
ifself
is less 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.For every nonnegative integer
, 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
. It can be defined in various ways, including the following ones:
- Two permutations
and
in
satisfy
in the right (resp. left) permutohedron order if and only if the (Coxeter) length of the permutation
(resp. of the permutation
) equals the length of
minus the length of
. Here,
means the permutation obtained by applying
first and then
. (Recall that the Coxeter length of a permutation is its number of inversions.)
- Two permutations
and
in
satisfy
in the right (resp. left) permutohedron order if and only if every pair
of elements of
such that
and
(resp.
) also satisfies
(resp.
).
- A permutation
covers a permutation
in the right (resp. left) permutohedron order if and only if we have
(resp.
) for some
satisfying
(resp.
). Here, again,
means the permutation obtained by applying
first and then
.
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
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: 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
- Two permutations
-
permutohedron_meet
(other, side='right')¶ Return the meet of the permutations
self
andother
in the right permutohedron order (or, ifside
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: Ifand
are two permutations
and
in the symmetric group
, and if
denotes the permutation
, then
and
where
means meet and
means join.
See also
AUTHORS:
Viviane Pons and Darij Grinberg, 18 June 2014.
EXAMPLES:
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]
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]
The universal property of the meet operation is satisfied:
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
Border cases:
sage: p = Permutation([]) sage: p.permutohedron_meet(p) [] sage: p = Permutation([1]) sage: p.permutohedron_meet(p) [1]
The left permutohedron:
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]
-
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 andself
.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: 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]]
-
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: 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]]
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]]
-
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 andself
.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: p = Permutation([4,2,1,3]) sage: p.permutohedron_succ() [[4, 2, 3, 1]] sage: 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 containingself
. Ifself
is the first permutation, then it returnsFalse
.EXAMPLES:
sage: p = Permutation([1,2,3]) sage: p.prev() False sage: p = Permutation([1,3,2]) sage: p.prev() [1, 2, 3]
TESTS:
sage: p = Permutation([]) sage: p.prev() False
Check that trac ticket #16913 is fixed:
sage: Permutation([1,4,3,2]).prev() [1, 4, 2, 3]
-
rank
()¶ Return the rank of
self
in the lexicographic ordering on the symmetric group to whichself
belongs.EXAMPLES:
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 ] == range(factorial(6)) True
-
recoils
()¶ Return the list of the positions of the recoils of
self
.A recoil of a permutation
is an integer
such that
appears to the left of
in
. Here, the positions are being counted starting at
. (Note that it is the positions, not the recoils themselves, which are being listed.)
EXAMPLES:
sage: Permutation([1,4,3,2]).recoils() [2, 3] sage: Permutation([]).recoils() []
-
recoils_composition
()¶ Return the recoils composition of
self
.The recoils composition of a permutation
is the composition of
whose descent set is the set of the recoils of
(not their positions). In other words, this is the descents composition of
.
EXAMPLES:
sage: Permutation([1,3,2,4]).recoils_composition() [2, 2] sage: 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: 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() []
-
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: Permutation([3,4,2,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
is a nonnegative integer, we can define the transpositions
for all
, and every
can then be written as a product
for some sequence
of elements of
(here
denotes the empty set when
). Fixing a
, the sequences
of smallest length satisfying
are called the reduced words of
. (Their length is the Coxeter length of
, and can be computed using
length()
.)Note that the product of permutations is defined here in such a way that
for all permutations
and
and each
(this is the same convention as in
left_action_product()
, but not the default semantics of theoperator on permutations in Sage). Thus, for instance,
is the permutation obtained by first transposing
with
and then transposing
with
.
See also
EXAMPLES:
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() [[]]
-
remove_extra_fixed_points
()¶ Return the permutation obtained by removing any fixed points at the end of
self
.EXAMPLES:
sage: Permutation([2,1,3]).remove_extra_fixed_points() [2, 1] sage: Permutation([1,2,3,4]).remove_extra_fixed_points() [1]
See also
-
retract_direct_product
(m)¶ Return the direct-product retract of the permutation
self
to
, where
. If this retract is undefined, then
None
is returned.If
is a permutation, and
is a nonnegative integer less or equal to
, then the direct-product retract of
to
is defined only if
, where
denotes the interval
. In this case, it is defined as the permutation written
in one-line notation.
EXAMPLES:
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
See also
-
retract_okounkov_vershik
(m)¶ Return the Okounkov-Vershik retract of the permutation
self
to
, where
.
If
is a permutation, and
is a nonnegative integer less or equal to
, then the Okounkov-Vershik retract of
to
is defined as the permutation in
which sends every
to
, where
is the smallest positive integer
satisfying
.
In other words, the Okounkov-Vershik retract of
is the permutation whose disjoint cycle decomposition is obtained by removing all letters strictly greater than
from the decomposition of
into disjoint cycles (and removing all cycles which are emptied in the process).
When
, the Okounkov-Vershik retract (as a map
) is the map
introduced in Section 7 of [OkounkovVershik2], and appears as (3.20) in [CST10]. In the general case, the Okounkov-Vershik retract of a permutation in
to
can be obtained by first taking its Okounkov-Vershik retract to
, then that of the resulting permutation to
, etc. until arriving in
.
REFERENCES:
[OkounkovVershik2] A. M. Vershik, A. Yu. Okounkov. A New Approach to the Representation Thoery of the Symmetric Groups. 2. http://uk.arxiv.org/abs/math/0503040v3. [CST10] Tullio Ceccherini-Silberstein, Fabio Scarabotti, Filippo Tolli. Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras. CUP 2010. EXAMPLES:
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
See also
-
retract_plain
(m)¶ Return the plain retract of the permutation
self
into
, where
. If this retract is undefined, then
None
is returned.If
is a permutation, and
is a nonnegative integer less or equal to
, then the plain retract of
to
is defined only if every
satisfies
. In this case, it is defined as the permutation written
in one-line notation.
EXAMPLES:
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
-
reverse
()¶ Returns the permutation obtained by reversing the list.
EXAMPLES:
sage: Permutation([3,4,1,2]).reverse() [2, 1, 4, 3] sage: Permutation([1,2,3,4,5]).reverse() [5, 4, 3, 2, 1]
-
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 permutationon an integer
is denoted by
, then this should be denoted by
rp * self
in order to have associativity (i.e., in order to havefor all
,
and
). If, on the other hand, the value of a permutation
on an integer
is denoted by
, then this should be denoted by
self * rp
in order to have associativity (i.e., in order to havefor all
,
and
).
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]
-
right_permutohedron_interval
(other)¶ Return the list of the permutations belonging to the right permutohedron interval where
self
is the minimal element andother
the maximal element.See
permutohedron_lequal()
for the definition of the permutohedron orders.EXAMPLES:
sage: Permutation([2, 1, 4, 5, 3]).right_permutohedron_interval(Permutation([2, 5, 4, 1, 3])) [[2, 1, 4, 5, 3], [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]]
TESTS:
sage: Permutation([]).right_permutohedron_interval(Permutation([])) [[]] sage: Permutation([3, 1, 2]).right_permutohedron_interval(Permutation([3, 1, 2])) [[3, 1, 2]] sage: Permutation([1, 3, 2, 4]).right_permutohedron_interval(Permutation([3, 4, 2, 1])) [[1, 3, 2, 4], [1, 3, 4, 2], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1]] sage: Permutation([2, 1, 4, 5, 3]).right_permutohedron_interval(Permutation([2, 5, 4, 1, 3])) [[2, 1, 4, 5, 3], [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 4, 5, 1, 3], [2, 5, 1, 4, 3], [2, 5, 4, 1, 3]] sage: Permutation([2, 5, 4, 1, 3]).right_permutohedron_interval(Permutation([2, 1, 4, 5, 3])) Traceback (most recent call last): ... ValueError: [2, 5, 4, 1, 3] must be lower or equal than [2, 1, 4, 5, 3] for the right permutohedron order sage: Permutation([2, 4, 1, 3]).right_permutohedron_interval(Permutation([2, 1, 4, 5, 3])) Traceback (most recent call last): ... ValueError: len([2, 4, 1, 3]) and len([2, 1, 4, 5, 3]) must be equal
-
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 andother
the maximal element.See
permutohedron_lequal()
for the definition of the permutohedron orders.EXAMPLES:
sage: Permutation([2, 1, 4, 5, 3]).right_permutohedron_interval(Permutation([2, 5, 4, 1, 3])) # indirect doctest [[2, 1, 4, 5, 3], [2, 1, 5, 4, 3], [2, 4, 1, 5, 3], [2, 4, 5, 1, 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: Permutation([1,4,3,2]).right_tableau() [[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()
onself
(with the optional argumentcheck_standard=True
to return standard Young tableaux).EXAMPLES:
sage: Permutation([6,2,3,1,7,5,4]).robinson_schensted() [[[1, 3, 4], [2, 5], [6, 7]], [[1, 3, 5], [2, 6], [4, 7]]]
-
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:
a list of lists or a tuple of tuples
REFERENCES:
EXAMPLES:
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]]
The example from above:
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,))
The number of runs in a nonempty permutation equals its number of descents plus 1:
sage: all( len(p.runs()) == p.number_of_descents() + 1 ....: for p in Permutations(6) ) True
-
saliances
()¶ Return a list of the saliances of the permutation
self
.A saliance of a permutation
is an integer
such that
for all
.
EXAMPLES:
sage: Permutation([2,3,1,5,4]).saliances() [3, 4] sage: Permutation([5,4,3,2,1]).saliances() [0, 1, 2, 3, 4]
-
shifted_concatenation
(other, side='right')¶ Return the right (or left) shifted concatenation of
self
with a permutationother
. 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
– (default:"right"
) the string “left” or “right”.
OUTPUT:
If
side
is"right"
, the method returns the permutation obtained by concatenatingself
with the letters ofother
incremented by the size ofself
. This is what is calledside / other
in [LodRon0102066], and denoted as the “over” operation. Otherwise, i. e., whenside
is"left"
, the method returns the permutation obtained by concatenating the letters ofother
incremented by the size ofself
withself
. This is what is calledside \ other
in [LodRon0102066] (which seems to use theconvention for the product of permutations).
EXAMPLES:
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]
REFERENCES:
[LodRon0102066] (1, 2) Jean-Louis Loday and Maria O. Ronco. Order structure on the algebra of permutations and of planar binary trees. Arxiv math/0102066v1.
-
shifted_shuffle
(other)¶ Return the shifted shuffle of two permutations
self
andother
.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
andother
.EXAMPLES:
sage: Permutation([]).shifted_shuffle(Permutation([])) [[]] sage: Permutation([1, 2, 3]).shifted_shuffle(Permutation([1])) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [4, 1, 2, 3]] sage: Permutation([1, 2]).shifted_shuffle(Permutation([2, 1])) [[1, 2, 4, 3], [1, 4, 2, 3], [1, 4, 3, 2], [4, 1, 2, 3], [4, 1, 3, 2], [4, 3, 1, 2]] sage: Permutation([1]).shifted_shuffle([1]) [[1, 2], [2, 1]] sage: len(Permutation([3, 1, 5, 4, 2]).shifted_shuffle(Permutation([2, 1, 4, 3]))) 126
The shifted shuffle product is associative. We can test this on an admittedly toy example:
sage: all( all( all( sorted(flatten([abs.shifted_shuffle(c) ....: 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
The
shifted_shuffle
method on permutations gives the same permutations as theshifted_shuffle
method on words (but is faster):sage: all( all( sorted(p1.shifted_shuffle(p2)) ....: == sorted([Permutation(p) for p in ....: Word(p1).shifted_shuffle(Word(p2))]) ....: for p2 in Permutations(3) ) ....: for p1 in Permutations(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 elementto 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: Permutations(20).random_element().show(representation = "cycles") sage: Permutations(20).random_element().show(representation = "chord-diagram") sage: Permutations(20).random_element().show(representation = "braid") sage: Permutations(20).random_element().show(representation = "braid", orientation='portrait')
TESTS:
sage: Permutations(20).random_element().show(representation = "modern_art") Traceback (most recent call last): ... ValueError: The value of 'representation' must be equal to 'cycles', 'chord-diagram' or 'braid'
-
sign
()¶ Return the signature of the permutation
self
. This is, where
is the number of inversions of
self
.Note
sign()
can be used as an alias forsignature()
.EXAMPLES:
sage: Permutation([4, 2, 3, 1, 5]).signature() -1 sage: Permutation([1,3,2,5,4]).sign() 1 sage: Permutation([]).sign() 1
-
signature
()¶ Return the signature of the permutation
self
. This is, where
is the number of inversions of
self
.Note
sign()
can be used as an alias forsignature()
.EXAMPLES:
sage: Permutation([4, 2, 3, 1, 5]).signature() -1 sage: Permutation([1,3,2,5,4]).sign() 1 sage: Permutation([]).sign() 1
-
simion_schmidt
(avoid=[1, 2, 3])¶ Implements 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: 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: ....: s=p.simion_schmidt(q) ....: print 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: Permutation([3,4,1,2,5]).size() 5
-
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
of all permutations of
. It is defined as the smallest equivalence relation such that every permutation of the form
with
,
and
being words and
,
and
being letters satisfying
is equivalent to the permutation
. (Here, permutations are regarded as words by way of one-line notation.) This definition comes from [HNT05], Definition 8, where it is more generally applied to arbitrary words.
The equivalence class of a permutation
under sylvester congruence is called the sylvester class of
. It is an interval in the right permutohedron order (see
permutohedron_lequal()
) on.
This is related to the
sylvester_class()
method in that the equivalence class of a permutationunder sylvester congruence is the sylvester class of the right-to-left binary search tree of
. However, the present method yields permutations, while the method on labelled binary trees yields plain lists.
If the variable
left_to_right
is set toTrue
, the method instead iterates over the equivalence class ofself
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
:
sage: p = Permutation([3, 5, 1, 2, 4]) sage: sorted(p.sylvester_class()) [[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
contains
:
sage: all( p in p.sylvester_class() for p in Permutations(4) ) True
Small cases:
sage: list(Permutation([]).sylvester_class()) [[]] sage: list(Permutation([1]).sylvester_class()) [[1]]
The sylvester classes in
:
sage: [sorted(p.sylvester_class()) for p in Permutations(3)] [[[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
:
sage: [sorted(p.sylvester_class(left_to_right=True)) 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]]]
A left sylvester class in
:
sage: p = Permutation([4, 2, 1, 5, 3]) sage: sorted(p.sylvester_class(left_to_right=True)) [[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: m = Permutation([1,2,3]).to_alternating_sign_matrix(); m [1 0 0] [0 1 0] [0 0 1] sage: parent(m) Alternating sign matrices of size 3
-
to_cycles
(singletons=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.EXAMPLES:
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([4,1,5,2,6,3]).to_cycles() [(1, 4, 2), (3, 5, 6)]
The algorithm is of complexity
where
is the size of the given permutation.
TESTS:
sage: from sage.combinat.permutation import from_cycles sage: for n in range(1,6): ....: for p in Permutations(n): ....: if from_cycles(n, p.to_cycles()) != p: ....: print "There is a problem with ",p ....: break sage: size = 10000 sage: sample = (Permutations(size).random_element() for i in range(5)) sage: all(from_cycles(size, p.to_cycles()) == p for p in sample) True
Note: there is an alternative implementation called
_to_cycle_set
which could be slightly (10%) faster for some input (typically for permutations of size in the range [100, 10000]). You can run the following benchmarks. For small permutations:sage: for size in range(9): # not tested ....: print size ....: lp = Permutations(size).list() ....: timeit('[p.to_cycles(False) for p in lp]') ....: timeit('[p._to_cycles_set(False) for p in lp]') ....: timeit('[p._to_cycles_list(False) for p in lp]') ....: timeit('[p._to_cycles_orig(False) for p in lp]')
and larger ones:
sage: for size in [10, 20, 50, 75, 100, 200, 500, 1000, # not tested ....: 2000, 5000, 10000, 15000, 20000, 30000, ....: 50000, 80000, 100000]: ....: print(size) ....: lp = [Permutations(size).random_element() for i in range(20)] ....: timeit("[p.to_cycles() for p in lp]") ....: timeit("[p._to_cycles_set() for p in lp]") ....: timeit("[p._to_cycles_list() for p in lp]")
-
to_inversion_vector
()¶ Return the inversion vector of
self
.The inversion vector of a permutation
is defined as the vector
, where
is the number of elements larger than
that appear to the left of
in the permutation
.
The algorithm is of complexity
where
is the size of the given permutation.
EXAMPLES:
sage: Permutation([5,9,1,8,2,6,4,7,3]).to_inversion_vector() [2, 3, 6, 4, 0, 2, 2, 1, 0] sage: Permutation([8,7,2,1,9,4,6,5,10,3]).to_inversion_vector() [3, 2, 7, 3, 4, 3, 1, 0, 0, 0] sage: Permutation([3,2,4,1,5]).to_inversion_vector() [3, 1, 0, 0, 0]
TESTS:
sage: from sage.combinat.permutation import from_inversion_vector sage: all(from_inversion_vector(p.to_inversion_vector()) == p ....: for n in range(6) for p in Permutations(n)) True sage: P = Permutations(1000) sage: sample = (P.random_element() for i in range(5)) sage: all(from_inversion_vector(p.to_inversion_vector()) == p ....: for p in sample) True
-
to_lehmer_cocode
()¶ Return the Lehmer cocode of the permutation
self
.The Lehmer cocode of a permutation
is defined as the list
, where
is the number of
such that
.
EXAMPLES:
sage: p = Permutation([2,1,3]) sage: p.to_lehmer_cocode() [0, 1, 0] sage: q = Permutation([3,1,2]) sage: q.to_lehmer_cocode() [0, 1, 1]
-
to_lehmer_code
()¶ Return the Lehmer code of the permutation
self
.The Lehmer code of a permutation
is defined as the list
, where
is the number of
such that
.
EXAMPLES:
sage: p = Permutation([2,1,3]) sage: p.to_lehmer_code() [1, 0, 0] sage: q = Permutation([3,1,2]) sage: q.to_lehmer_code() [2, 0, 0] sage: Permutation([1]).to_lehmer_code() [0] sage: Permutation([]).to_lehmer_code() []
TESTS:
sage: from sage.combinat.permutation import from_lehmer_code sage: all(from_lehmer_code(p.to_lehmer_code()) == p ....: for n in range(6) for p in Permutations(n)) True sage: P = Permutations(1000) sage: sample = (P.random_element() for i in range(5)) sage: all(from_lehmer_code(p.to_lehmer_code()) == p ....: for p in sample) True
-
to_major_code
(final_descent=False)¶ Return the major code of the permutation
self
.The major code of a permutation
is defined as the sequence
, where
is the major index of the permutation obtained by erasing all letters smaller than
from
.
With the
final_descent
option, the last position of a non-empty permutation is also considered as a descent. This has an effect on the computation of major indices.REFERENCES:
- Carlitz, L. q-Bernoulli and Eulerian Numbers. Trans. Amer. Math. Soc. 76 (1954) 332-350. http://www.ams.org/journals/tran/1954-076-02/S0002-9947-1954-0060538-2/
- Skandera, M. An Eulerian Partner for Inversions. Sem. Lothar. Combin. 46 (2001) B46d. http://www.lehigh.edu/~mas906/papers/partner.ps
EXAMPLES:
sage: Permutation([9,3,5,7,2,1,4,6,8]).to_major_code() [5, 0, 1, 0, 1, 2, 0, 1, 0] sage: Permutation([2,8,4,3,6,7,9,5,1]).to_major_code() [8, 3, 3, 1, 4, 0, 1, 0, 0]
-
to_matrix
()¶ Return a matrix representing the permutation.
EXAMPLES:
sage: Permutation([1,2,3]).to_matrix() [1 0 0] [0 1 0] [0 0 1]
sage: Permutation([1,3,2]).to_matrix() [1 0 0] [0 0 1] [0 1 0]
Notice that matrix multiplication corresponds to permutation multiplication only when the permutation option mult=’r2l’
sage: PermutationOptions(mult='r2l') sage: p = Permutation([2,1,3]) sage: q = Permutation([3,1,2]) sage: (p*q).to_matrix() [0 0 1] [0 1 0] [1 0 0] sage: p.to_matrix()*q.to_matrix() [0 0 1] [0 1 0] [1 0 0] sage: PermutationOptions(mult='l2r') sage: (p*q).to_matrix() [1 0 0] [0 0 1] [0 1 0]
-
to_permutation_group_element
()¶ Returns a PermutationGroupElement equal to self.
EXAMPLES:
sage: Permutation([2,1,4,3]).to_permutation_group_element() (1,2)(3,4) sage: Permutation([1,2,3]).to_permutation_group_element() ()
-
to_tableau_by_shape
(shape)¶ Return a tableau of shape
shape
with the entries inself
. The tableau is such that the reading word (i. e., the word obtained by reading the tableau row by row, starting from the top row in English notation, with each row being read from left to right) isself
.EXAMPLES:
sage: Permutation([3,4,1,2,5]).to_tableau_by_shape([3,2]) [[1, 2, 5], [3, 4]] sage: Permutation([3,4,1,2,5]).to_tableau_by_shape([3,2]).reading_word_permutation() [3, 4, 1, 2, 5]
-
weak_excedences
()¶ Return all the numbers
self[i]
such thatself[i] >= i+1
.EXAMPLES:
sage: Permutation([1,4,3,2,5]).weak_excedences() [1, 4, 3, 5]
-
class
sage.combinat.permutation.
Permutations
¶ Bases:
sage.structure.parent.Parent
,sage.structure.unique_representation.UniqueRepresentation
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-partial permutation of
is defined as a
-tuple of pairwise distinct elements of
.
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 ofwith descents in the positions specified by
list
. This uses the slightly nonstandard convention that the images ofunder the permutation are regarded as positions
, so for example the presence of
in
list
signifies that the permutationsshould satisfy
. Note that
list
is supposed to be a list of positions of the descents, not the descents composition. The alternative syntaxPermutations(descents=list)
is deprecated. It used to boil downPermutations(descents=(list, max(list) + 2)
) (unless the listlist
is empty). 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() [[1, 3, 2, 4], [1, 4, 2, 3], [2, 3, 1, 4], [2, 4, 1, 3], [3, 4, 1, 2]]
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() [[1, 2, 3], [1, 3, 2], [3, 1, 2]]
sage: p = Permutations(recoils_fatter=[2,1]); p Standard permutations whose recoils composition is fatter than [2, 1] sage: p.list() [[1, 3, 2], [3, 1, 2], [3, 2, 1]]
sage: p = Permutations(recoils=[2,1]); p Standard permutations whose recoils composition is [2, 1] sage: p.list() [[1, 3, 2], [3, 1, 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]
-
Element
¶ alias of
Permutation
-
global_options
(*get_value, **set_value)¶ Set the global options for elements of the permutation class. The defaults are for permutations to be displayed in list notation and the multiplication done from left to right (like in GAP) – that is,
for all
.
Note
These options have no effect on permutation group elements.
OPTIONS:
display
– (default:list
) Specifies how the permutations should be printedcycle
– the permutations are displayed in cycle notation (i. e., as products of disjoint cycles)list
– the permutations are displayed in list notation (aka 1-line notation)reduced_expression
– alias forreduced_word
reduced_word
– the permutations are displayed as reduced wordssingleton
– the permutations are displayed in cycle notation with singleton cycles shown as wellword
– alias forreduced_word
generator_name
– (default:s
) the letter used in latexing the reduced wordlatex
– (default:list
) Specifies how the permutations should be latexedcycle
– latex in cycle notationlist
– latex as a list in one-line notationoneline
– alias forlist
reduced_expression
– alias forreduced_word
reduced_word
– latex as reduced wordssingleton
– latex in cycle notation with singleton cycles shown as welltwoline
– latex in two-line notationword
– alias forreduced_word
latex_empty_str
– (default:1
) The LaTeX representation of a reduced word when said word is emptymult
– (default:l2r
) The multiplication of permutationsl2r
– left to right:r2l
– right to left:
EXAMPLES:
sage: p213 = Permutation([2,1,3]) sage: p312 = Permutation([3,1,2]) sage: Permutations.global_options(mult='l2r', display='list') sage: Permutations.global_options['display'] 'list' sage: p213 [2, 1, 3] sage: Permutations.global_options(display='cycle') sage: p213 (1,2) sage: Permutations.global_options(display='singleton') sage: p213 (1,2)(3) sage: Permutations.global_options(display='list')
sage: Permutations.global_options['mult'] 'l2r' sage: p213*p312 [1, 3, 2] sage: Permutations.global_options(mult='r2l') sage: p213*p312 [3, 2, 1] sage: Permutations.global_options.reset()
See
GlobalOptions
for more features of these options.
-
-
class
sage.combinat.permutation.
PermutationsNK
(s, k)¶ Bases:
sage.combinat.permutation.Permutations_setk
This exists solely for unpickling
PermutationsNK
objects created with Sage <= 6.3.
-
class
sage.combinat.permutation.
Permutations_mset
(mset)¶ Bases:
sage.combinat.permutation.Permutations
Permutations of a multiset
.
A permutation of a multiset
is represented by a list that contains exactly the same elements as
(with the same multiplicities), but possibly in different order. If
is a proper set there are
such permutations. Otherwise, if the first element appears
times, the second element appears
times and so on, the number of permutations is
, which is sometimes called a multinomial coefficient.
-
class
Element
¶ Bases:
sage.structure.list_clone.ClonableArray
A permutation of an arbitrary multiset.
-
check
()¶ Verify that
self
is a valid permutation of the underlying multiset.EXAMPLES:
sage: S = Permutations(['c','a','c']) sage: elt = S(['c','c','a']) sage: elt.check()
-
-
Permutations_mset.
cardinality
()¶ EXAMPLES:
sage: Permutations([1,2,2]).cardinality() 3 sage: Permutations([1,1,2,2,2]).cardinality() 10
-
class
-
class
sage.combinat.permutation.
Permutations_msetk
(mset, k)¶ Bases:
sage.combinat.permutation.Permutations_mset
Length-
partial permutations of a multiset.
A length-
partial permutation of a multiset
is represented by a list of length
whose entries are elements of
, appearing in the list with a multiplicity not higher than their respective multiplicity in
.
-
class
sage.combinat.permutation.
Permutations_nk
(n, k)¶ Bases:
sage.combinat.permutation.Permutations
Length-
partial permutations of
.
-
class
Element
¶ Bases:
sage.structure.list_clone.ClonableArray
A length-
partial permutation of
.
-
check
()¶ Verify that
self
is a valid length-partial permutation of
.
EXAMPLES:
sage: S = Permutations(4, 2) sage: elt = S([3, 1]) sage: elt.check()
-
-
Permutations_nk.
cardinality
()¶ EXAMPLES:
sage: Permutations(3,0).cardinality() 1 sage: Permutations(3,1).cardinality() 3 sage: Permutations(3,2).cardinality() 6 sage: Permutations(3,3).cardinality() 6 sage: Permutations(3,4).cardinality() 0
-
Permutations_nk.
random_element
()¶ EXAMPLES:
sage: Permutations(3,2).random_element() [0, 1]
-
class
-
class
sage.combinat.permutation.
Permutations_set
(s)¶ Bases:
sage.combinat.permutation.Permutations
Permutations of an arbitrary given finite set.
Here, a “permutation of a finite set
” means a list of the elements of
in which every element of
occurs exactly once. This is not to be confused with bijections from
to
, which are also often called permutations in literature.
-
class
Element
¶ Bases:
sage.structure.list_clone.ClonableArray
A permutation of an arbitrary set.
-
check
()¶ Verify that
self
is a valid permutation of the underlying set.EXAMPLES:
sage: S = Permutations(['c','a','t']) sage: elt = S(['t','c','a']) sage: elt.check()
-
-
Permutations_set.
cardinality
()¶ EXAMPLES:
sage: Permutations([1,2,3]).cardinality() 6
-
Permutations_set.
random_element
()¶ EXAMPLES:
sage: Permutations([1,2,3]).random_element() [1, 2, 3]
-
class
-
class
sage.combinat.permutation.
Permutations_setk
(s, k)¶ Bases:
sage.combinat.permutation.Permutations_set
Length-
partial permutations of an arbitrary given finite set.
Here, a “length-
partial permutation of a finite set
” means a list of length
whose entries are pairwise distinct and all belong to
.
-
random_element
()¶ EXAMPLES:
sage: Permutations([1,2,3],2).random_element() [1, 2]
-
-
class
sage.combinat.permutation.
StandardPermutations_all
¶ Bases:
sage.combinat.permutation.Permutations
All standard permutations.
-
class
sage.combinat.permutation.
StandardPermutations_avoiding_12
(n)¶ Bases:
sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[1, 2]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[2, 1, 3]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[1, 3, 2]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[2, 1]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[2, 1, 3]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[2, 3, 1]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[3, 1, 2]) sage: TestSuite(P).run()
-
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
TESTS:
sage: P = Permutations(3, avoiding=[3, 2, 1]) sage: TestSuite(P).run()
-
cardinality
()¶ EXAMPLES:
sage: Permutations(5, avoiding=[3, 2, 1]).cardinality() 42 sage: len( Permutations(5, avoiding=[3, 2, 1]).list() ) 42
-
-
class
sage.combinat.permutation.
StandardPermutations_avoiding_generic
(n, a)¶ Bases:
sage.combinat.permutation.StandardPermutations_n_abstract
Generic class for subset of permutations avoiding a particular pattern.
-
cardinality
()¶ Return the cardinality of
self
.EXAMPLES:
sage: P = Permutations(3, avoiding=[[2, 1, 3],[1,2,3]]) sage: P.cardinality() 4
-
-
class
sage.combinat.permutation.
StandardPermutations_bruhat_greater
(p)¶ Bases:
sage.combinat.permutation.Permutations
Permutations of
that are greater than or equal to a permutation
in the Bruhat order.
-
class
sage.combinat.permutation.
StandardPermutations_bruhat_smaller
(p)¶ Bases:
sage.combinat.permutation.Permutations
Permutations of
that are less than or equal to a permutation
in the Bruhat order.
-
class
sage.combinat.permutation.
StandardPermutations_descents
(d, n)¶ Bases:
sage.combinat.permutation.StandardPermutations_n_abstract
Permutations of
with a fixed set of descents.
-
cardinality
()¶ Return the cardinality of
self
.EXAMPLES:
sage: P = Permutations(descents=([1,0,2],5)) sage: P.cardinality() 4
-
first
()¶ Return the first permutation with descents
.
EXAMPLES:
sage: Permutations(descents=([1,0,4,8],12)).first() [3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
-
last
()¶ Return the last permutation with descents
.
EXAMPLES:
sage: Permutations(descents=([1,0,4,8],12)).last() [12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
-
-
class
sage.combinat.permutation.
StandardPermutations_n
(n)¶ Bases:
sage.combinat.permutation.StandardPermutations_n_abstract
Permutations of the set
.
These are also called permutations of size
, or the elements of the
-th symmetric group.
Todo
Have a
reduced_word()
which works in both multiplication conventions.-
class
Element
(parent, l, check_input=True)¶ Bases:
sage.combinat.permutation.Permutation
Constructor. Checks that INPUT is not a mess, and calls
CombinatorialElement
. It should not, becauseCombinatorialElement
is deprecated.INPUT:
l
– a list ofint
variablescheck_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.
TESTS:
sage: Permutation([1,2,3]) [1, 2, 3] sage: Permutation([1,2,2,4]) Traceback (most recent call last): ... ValueError: An element appears twice in the input. It should not. sage: Permutation([1,2,4,-1]) Traceback (most recent call last): ... ValueError: the elements must be strictly positive integers sage: Permutation([1,2,4,5]) Traceback (most recent call last): ... ValueError: The permutation has length 4 but its maximal element is 5. Some element may be repeated, or an element is missing, but there is something wrong with its length.
-
has_left_descent
(i, mult=None)¶ Check if
i
is a left descent ofself
.A left descent of a permutation
means an index
such that
has smaller length than
. Here,
denotes the multiplication of
. How it is defined depends on the
mult
variable inPermutations.global_options()
. If this variable is set to'l2r'
, then the multiplication is defined by the rulefor
and
; then, a left descent of
is an index
satisfying
. If this variable is set to
'r2l'
, then the multiplication is defined by the rulefor
and
; then, a left descent of
is an index
satisfying
.
The optional parameter
mult
can be set to'l2r'
or'r2l'
; if so done, it is used instead of themult
variable inPermutations.global_options()
. Anyone using this method in a non-interactive environment is encouraged to do so in order to have code behave reliably.Warning
The methods
descents()
andidescents()
behave differently than their Weyl group counterparts. In particular, the indexing is 0-based. This could lead to errors. Instead, construct the descent set as in the example.Warning
The optional input
mult
might disappear once trac ticket #14881 is fixed.EXAMPLES:
sage: P = Permutations(4) sage: x = P([3, 2, 4, 1]) sage: x.descents() # known bug - different indices [1, 3] sage: [i for i in P.index_set() if x.has_left_descent(i)] [1, 3] sage: [i for i in P.index_set() if x.has_left_descent(i, mult="l2r")] [1, 3] sage: [i for i in P.index_set() if x.has_left_descent(i, mult="r2l")] [1, 2]
-
has_right_descent
(i, mult=None)¶ Check if
i
is a right descent ofself
.A right descent of a permutation
means an index
such that
has smaller length than
. Here,
denotes the multiplication of
. How it is defined depends on the
mult
variable inPermutations.global_options()
. If this variable is set to'l2r'
, then the multiplication is defined by the rulefor
and
; then, a right descent of
is an index
satisfying
. If this variable is set to
'r2l'
, then the multiplication is defined by the rulefor
and
; then, a right descent of
is an index
satisfying
.
The optional parameter
mult
can be set to'l2r'
or'r2l'
; if so done, it is used instead of themult
variable inPermutations.global_options()
. Anyone using this method in a non-interactive environment is encouraged to do so in order to have code behave reliably.Warning
The methods
descents()
andidescents()
behave differently than their Weyl group counterparts. In particular, the indexing is 0-based. This could lead to errors. Instead, construct the descent set as in the example.Warning
The optional input
mult
might disappear once trac ticket #14881 is fixed.EXAMPLES:
sage: P = Permutations(4) sage: x = P([3, 2, 4, 1]) sage: (~x).descents() # known bug - different indices [1, 2] sage: [i for i in P.index_set() if x.has_right_descent(i)] [1, 2] sage: [i for i in P.index_set() if x.has_right_descent(i, mult="l2r")] [1, 2] sage: [i for i in P.index_set() if x.has_right_descent(i, mult="r2l")] [1, 3]
-
inverse
()¶ Return the inverse of
self
.EXAMPLES:
sage: P = Permutations(4) sage: w0 = P([4,3,2,1]) sage: w0.inverse() == w0 True sage: w0.inverse().parent() is P True sage: P([3,2,4,1]).inverse() [4, 2, 1, 3]
-
StandardPermutations_n.
algebra
(base_ring, category=None)¶ Return the symmetric group algebra associated to
self
.INPUT:
base_ring
– a ringcategory
– a category (default: the category ofself
)
EXAMPLES:
sage: P = Permutations(4) sage: A = P.algebra(QQ); A Symmetric group algebra of order 4 over Rational Field sage: A.category() Join of Category of coxeter group algebras over Rational Field and Category of finite group algebras over Rational Field sage: A = P.algebra(QQ, category=Monoids()) sage: A.category() Category of finite dimensional monoid algebras over Rational Field
-
StandardPermutations_n.
cardinality
()¶ Return the number of permutations of size
, which is
.
EXAMPLES:
sage: Permutations(0).cardinality() 1 sage: Permutations(3).cardinality() 6 sage: Permutations(4).cardinality() 24
-
StandardPermutations_n.
cartan_type
()¶ Return the Cartan type of
self
.The symmetric group
is a Coxeter group of type
.
EXAMPLES:
sage: A = SymmetricGroup([2,3,7]); A.cartan_type() ['A', 2] sage: A = SymmetricGroup([]); A.cartan_type() ['A', 0]
-
StandardPermutations_n.
conjugacy_class
(g)¶ Return the conjugacy class of
g
inself
.INPUT:
g
– a partition or an element ofself
EXAMPLES:
sage: G = Permutations(5) sage: g = G([2,3,4,1,5]) sage: G.conjugacy_class(g) Conjugacy class of cycle type [4, 1] in Standard permutations of 5 sage: G.conjugacy_class(Partition([2, 1, 1, 1])) Conjugacy class of cycle type [2, 1, 1, 1] in Standard permutations of 5
-
StandardPermutations_n.
conjugacy_classes
()¶ Return a list of the conjugacy classes of
self
.EXAMPLES:
sage: G = Permutations(4) sage: G.conjugacy_classes() [Conjugacy class of cycle type [1, 1, 1, 1] in Standard permutations of 4, Conjugacy class of cycle type [2, 1, 1] in Standard permutations of 4, Conjugacy class of cycle type [2, 2] in Standard permutations of 4, Conjugacy class of cycle type [3, 1] in Standard permutations of 4, Conjugacy class of cycle type [4] in Standard permutations of 4]
-
StandardPermutations_n.
conjugacy_classes_iterator
()¶ Iterate over the conjugacy classes of
self
.EXAMPLES:
sage: G = Permutations(4) sage: list(G.conjugacy_classes_iterator()) == G.conjugacy_classes() True
-
StandardPermutations_n.
conjugacy_classes_representatives
()¶ Return a complete list of representatives of conjugacy classes in
self
.Let
be the symmetric group on
letters. The conjugacy classes are indexed by partitions
of
. The ordering of the conjugacy classes is reverse lexicographic order of the partitions.
EXAMPLES:
sage: G = Permutations(5) sage: G.conjugacy_classes_representatives() [[1, 2, 3, 4, 5], [2, 1, 3, 4, 5], [2, 1, 4, 3, 5], [2, 3, 1, 4, 5], [2, 3, 1, 5, 4], [2, 3, 4, 1, 5], [2, 3, 4, 5, 1]]
TESTS:
Check some border cases:
sage: S = Permutations(0) sage: S.conjugacy_classes_representatives() [[]] sage: S = Permutations(1) sage: S.conjugacy_classes_representatives() [[1]]
-
StandardPermutations_n.
element_in_conjugacy_classes
(nu)¶ Return a permutation with cycle type
nu
.If the size of
nu
is smaller than the size of permutations inself
, then some fixed points are added.EXAMPLES:
sage: PP = Permutations(5) sage: PP.element_in_conjugacy_classes([2,2]) [2, 1, 4, 3, 5]
-
StandardPermutations_n.
identity
()¶ Return the identity permutation of size
.
EXAMPLES:
sage: Permutations(4).identity() [1, 2, 3, 4] sage: Permutations(0).identity() []
-
StandardPermutations_n.
index_set
()¶ Return the index set for the descents of the symmetric group
self
.This is
, where
self
is.
EXAMPLES:
sage: P = Permutations(8) sage: P.index_set() (1, 2, 3, 4, 5, 6, 7)
-
StandardPermutations_n.
one
()¶ Return the identity permutation of size
.
EXAMPLES:
sage: Permutations(4).identity() [1, 2, 3, 4] sage: Permutations(0).identity() []
-
StandardPermutations_n.
random_element
()¶ EXAMPLES:
sage: Permutations(4).random_element() [1, 2, 4, 3]
-
StandardPermutations_n.
rank
(p)¶ EXAMPLES:
sage: SP3 = Permutations(3) sage: map(SP3.rank, SP3) [0, 1, 2, 3, 4, 5] sage: SP0 = Permutations(0) sage: map(SP0.rank, SP0) [0]
-
StandardPermutations_n.
simple_reflection
(i)¶ For
in the index set of
self
(that is, forin
, where
self
is), this returns the elementary transposition
.
EXAMPLES:
sage: P = Permutations(4) sage: P.simple_reflection(2) [1, 3, 2, 4] sage: P.simple_reflections() Finite family {1: [2, 1, 3, 4], 2: [1, 3, 2, 4], 3: [1, 2, 4, 3]}
-
StandardPermutations_n.
unrank
(r)¶ EXAMPLES:
sage: SP3 = Permutations(3) sage: l = map(SP3.unrank, range(6)) sage: l == SP3.list() True sage: SP0 = Permutations(0) sage: l = map(SP0.unrank, range(1)) sage: l == SP0.list() True
-
class
-
class
sage.combinat.permutation.
StandardPermutations_n_abstract
(n, category=None)¶ Bases:
sage.combinat.permutation.Permutations
Abstract base class for subsets of permutations of the set
.
Warning
Anyone inheriting from this class should override the
__contains__
method.
-
class
sage.combinat.permutation.
StandardPermutations_recoils
(recoils)¶ Bases:
sage.combinat.permutation.Permutations
Permutations of
with a fixed recoils composition.
-
class
sage.combinat.permutation.
StandardPermutations_recoilsfatter
(recoils)¶ Bases:
sage.combinat.permutation.Permutations
TESTS:
sage: P = Permutations(recoils_fatter=[2,2]) sage: TestSuite(P).run()
-
class
sage.combinat.permutation.
StandardPermutations_recoilsfiner
(recoils)¶ Bases:
sage.combinat.permutation.Permutations
TESTS:
sage: P = Permutations(recoils_finer=[2,2]) sage: TestSuite(P).run()
-
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
. 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-module ( where
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
is bistochastic if there exists
such that
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.
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]) [[2, 1, 4, 3, 5], [2, 1, 5, 3, 4], [3, 1, 4, 2, 5], [3, 1, 5, 2, 4], [4, 1, 3, 2, 5], [5, 1, 3, 2, 4], [4, 1, 5, 2, 3], [5, 1, 4, 2, 3], [3, 2, 4, 1, 5], [3, 2, 5, 1, 4], [4, 2, 3, 1, 5], [5, 2, 3, 1, 4], [4, 2, 5, 1, 3], [5, 2, 4, 1, 3], [4, 3, 5, 1, 2], [5, 3, 4, 1, 2]]
-
sage.combinat.permutation.
from_cycles
(n, cycles, parent=None)¶ Return the permutation in the
-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
). 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 negative 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
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. 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]
TESTS:
sage: permutation.from_major_code([]) [] sage: all( permutation.from_major_code(p.to_major_code()) == p ....: for p in Permutations(5) ) True
-
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
with lexicographic rank
rank
. This is the permutation whose Lehmer code is the factoradic representation ofrank
. In particular, the permutation with rankis 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 fromto
. When outside this interval, it acts as its residue modulo
.
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)¶ Return a standard permutation corresponding to the list
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([]) []
TESTS:
Does not mutate the list:
sage: a = [1,2,4] sage: permutation.to_standard(a) [1, 2, 3] sage: a [1, 2, 4]