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 CombinatorialObject 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.
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. |
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 ![]() |
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 ![]() ![]() |
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:
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 from mset, but maybe in a different order.
Arrangements returns the combinatorial class of arrangements of the multiset mset that contain k elements.
EXAMPLES:
sage: mset = [1,1,2,3,4,4,5]
sage: Arrangements(mset,2).list()
[[1, 1],
[1, 2],
[1, 3],
[1, 4],
[1, 5],
[2, 1],
[2, 3],
[2, 4],
[2, 5],
[3, 1],
[3, 2],
[3, 4],
[3, 5],
[4, 1],
[4, 2],
[4, 3],
[4, 4],
[4, 5],
[5, 1],
[5, 2],
[5, 3],
[5, 4]]
sage: Arrangements(mset,2).cardinality()
22
sage: Arrangements( ["c","a","t"], 2 ).list()
[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
sage: Arrangements( ["c","a","t"], 3 ).list()
[['c', 'a', 't'],
['c', 't', 'a'],
['a', 'c', 't'],
['a', 't', 'c'],
['t', 'c', 'a'],
['t', 'a', 'c']]
Return the cardinality of self.
EXAMPLES:
sage: A = Arrangements([1,1,2,3,4,4,5], 2)
sage: A.cardinality()
22
Bases: sage.combinat.permutation.Arrangements, sage.combinat.permutation.Permutations_msetk
Arrangements of length of a multiset
.
Bases: sage.combinat.permutation.Arrangements, sage.combinat.permutation.Permutations_setk
Arrangements of length of a set
.
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:
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]]
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]]
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]]
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]]]
Bases: sage.structure.list_clone.ClonableArray
A cyclic permutation of a partition.
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()
AUTHORS:
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]]]
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]]]
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]]
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]
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...>
Bases: sage.combinat.combinat.CombinatorialObject, sage.structure.element.Element
A permutation.
Converts l to a permutation on .
INPUT:
l – Can be any one of the following:
the function down, but ensures that nothing bad happens. This is set to True by default.
Warning
Since trac ticket #13742 the input is checked for correctness : it is not
accepted unless actually is a permutation on . It
means that some Permutation() objects cannot be created anymore
without setting check_input = False, as there is no certainty that
its functions can handle them, and this should be fixed in a much
better way ASAP (the functions should be rewritten to handle those
cases, and new tests be added).
Warning
There are two possible conventions for multiplying permutations, and
the one currently enabled in Sage by default is the one which has
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 methods
left_action_product() and right_action_product() for
multiplying permutations (these methods don’t depend on the setting).
See trac ticket #14885 for more details.
Note
The bruhat* methods refer to the strong Bruhat order. To use the weak Bruhat order, look under permutohedron*.
EXAMPLES:
sage: Permutation([2,1])
[2, 1]
sage: Permutation([2, 1, 4, 5, 3])
[2, 1, 4, 5, 3]
sage: Permutation('(1,2)')
[2, 1]
sage: Permutation('(1,2)(3,4,5)')
[2, 1, 4, 5, 3]
sage: Permutation( ((1,2),(3,4,5)) )
[2, 1, 4, 5, 3]
sage: Permutation( [(1,2),(3,4,5)] )
[2, 1, 4, 5, 3]
sage: Permutation( ((1,2)) )
[2, 1]
sage: Permutation( (1,2) )
[2, 1]
sage: Permutation( ((1,2),) )
[2, 1]
sage: Permutation( ((1,),) )
[1]
sage: Permutation( (1,) )
[1]
sage: Permutation( () )
[]
sage: Permutation( ((),) )
[]
sage: p = Permutation((1, 2, 5)); p
[2, 5, 3, 4, 1]
sage: type(p)
<class 'sage.combinat.permutation.StandardPermutations_all_with_category.element_class'>
Construction from a string in cycle notation:
sage: p = Permutation( '(4,5)' ); p
[1, 2, 3, 5, 4]
The size of the permutation is the maximum integer appearing; add a 1-cycle to increase this:
sage: p2 = Permutation( '(4,5)(10)' ); p2
[1, 2, 3, 5, 4, 6, 7, 8, 9, 10]
sage: len(p); len(p2)
5
10
We construct a Permutation from a PermutationGroupElement:
sage: g = PermutationGroupElement([2,1,3])
sage: Permutation(g)
[2, 1, 3]
From a pair of tableaux of the same shape. This uses the inverse of the Robinson-Schensted algorithm:
sage: p = [[1, 4, 7], [2, 5], [3], [6]]
sage: q = [[1, 2, 5], [3, 6], [4], [7]]
sage: P = Tableau(p)
sage: Q = Tableau(q)
sage: Permutation( (p, q) )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( [p, q] )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( (P, Q) )
[3, 6, 5, 2, 7, 4, 1]
sage: Permutation( [P, Q] )
[3, 6, 5, 2, 7, 4, 1]
TESTS:
sage: Permutation([()])
[]
sage: Permutation('()')
[]
sage: Permutation(())
[]
sage: Permutation( [1] )
[1]
From a pair of empty tableaux
sage: Permutation( ([], []) )
[]
sage: Permutation( [[], []] )
[]
Return the permutation obtained by composing self with rp in such an order that self is applied first and rp is applied afterwards.
This is usually denoted by either self * rp or rp * self
depending on the conventions used by the author. If the value
of a permutation on an integer
is denoted by
, then this
should be denoted by rp * self in order to have
associativity (i.e., in order to have
for 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 have
for 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]
Return the permutation obtained by composing self with lp in such an order that lp is applied first and self is applied afterwards.
This is usually denoted by either self * lp or lp * self
depending on the conventions used by the author. If the value
of a permutation on an integer
is denoted by
, then this
should be denoted by self * lp in order to have
associativity (i.e., in order to have
for 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 have
for 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]
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]
Return the action of the permutation self on a list a.
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]
Test whether the permutation self avoids the pattern patt.
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
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 word
is being traversed from left to right.
A permutation is regarded as a word (using one-line notation), and thus a binary search tree associated to a permutation is defined.
If the optional keyword variable left_to_right is set to
False, the word is 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()
.
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)
[[., .], [., [., .]]]
Returns the combinatorial class of permutations greater than or equal to self in the Bruhat order (on the symmetric group containing self).
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: 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]]
Return the list of inversions of self such that the application of this inversion to self decreases its number of inversions by exactly 1.
Equivalently, it returns the list of pairs 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]]
Return the iterator for the inversions of self such that the application of this inversion to self decreases its number of inversions by exactly 1.
EXAMPLES:
sage: 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]]
Return True if self is less or equal to p2 in the Bruhat order.
The Bruhat order (also called strong Bruhat order or Chevalley
order) on the symmetric group 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 and p2 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
Return a list of the permutations strictly smaller than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: 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]]
An iterator for the permutations strictly smaller than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: [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]]
Return the combinatorial class of permutations smaller than or equal to self in the Bruhat order (on the symmetric group containing self).
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: 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]]
Return a list of the permutations strictly greater than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: 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]]
An iterator for the permutations that are strictly greater than self in the Bruhat order (on the symmetric group containing self) such that there is no permutation between one of those and self.
See bruhat_lequal() for the definition of the Bruhat order.
EXAMPLES:
sage: [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]]
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]
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)'
Return the permutation self as a list of disjoint cycles.
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)]
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]") # not tested
Return a partition of len(self) corresponding to the cycle type of self. This is a non-increasing sequence of the cycle lengths of self.
EXAMPLES:
sage: Permutation([3,1,2,4]).cycle_type()
[3, 1]
Return the descent polynomial of the permutation self.
The descent polynomial of a permutation is the product of
all the z[p[i]] where i ranges over the descents of
p.
A descent of a permutation p is an integer i such that
p[i] > p[i+1]. Here, Python’s indexing convention is used,
so p[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).
Return the list of the descents of self.
A descent of a permutation p is an integer i such that
p[i] > p[i+1]. Here, Python’s indexing convention is used,
so p[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]
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 at
instead 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()
[]
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
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]
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]
Test whether the permutation self contains the pattern patt.
EXAMPLES:
sage: Permutation([3,5,1,4,6,2]).has_pattern([1,3,2])
True
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. |
Return a list of the idescents of self, that is the list of the descents of self‘s inverse.
A descent of a permutation p is an integer i such that
p[i] > p[i+1]. Here, Python’s indexing convention is used,
so p[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]
Return the list obtained as follows: Each position in self
is mapped to if 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]
Return the inverse major index of the permutation self, which is the major index of the inverse of self.
The major index of a permutation 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
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[., .]], .]
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)
[[[., .], [., .]], .]
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]
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)]
Return True if the permutation self is even and False otherwise.
EXAMPLES:
sage: Permutation([1,2,3]).is_even()
True
sage: Permutation([2,1,3]).is_even()
False
Return the i-shift of self. If an i-shift of self can’t be performed, then self 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]
Return the i-switch of self. If an i-switch of self can’t be performed, then self 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]
Return the permutation obtained by composing self with lp in such an order that lp is applied first and self is applied afterwards.
This is usually denoted by either self * lp or lp * self
depending on the conventions used by the author. If the value
of a permutation on an integer
is denoted by
, then this
should be denoted by self * lp in order to have
associativity (i.e., in order to have
for 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 have
for 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]
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]]
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
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
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]]
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
Return the permutation that follows self in lexicographic order on the symmetric group containing self. If self is the last permutation, then next returns False.
EXAMPLES:
sage: p = Permutation([1, 3, 2])
sage: p.next()
[2, 1, 3]
sage: p = Permutation([4,3,2,1])
sage: p.next()
False
TESTS:
sage: p = Permutation([])
sage: p.next()
False
Return the list of all k-noninversions in self.
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)
[]
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
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
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
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
Return the number of k-noninversions in self.
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
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
Return the number of recoils of the permutation self.
EXAMPLES:
sage: Permutation([1,4,3,2]).number_of_recoils()
2
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
Return the list of positions where the pattern patt appears in the permutation self.
EXAMPLES:
sage: Permutation([3,5,1,4,6,2]).pattern_positions([1,3,2])
[[0, 1, 3], [2, 3, 5], [2, 4, 5]]
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()
[]
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
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]]
Return True if self is less or equal to p2 in the permutohedron order.
By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.
For every nonnegative integer , 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:
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
Return a list of the permutations strictly smaller than self in the permutohedron order such that there is no permutation between any of those and self.
By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.
See permutohedron_lequal() for the definition of the permutohedron orders.
EXAMPLES:
sage: 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]]
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]]
Return a list of the permutations strictly greater than self in the permutohedron order such that there is no permutation between any of those and self.
By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.
See permutohedron_lequal() for the definition of the permutohedron orders.
EXAMPLES:
sage: p = Permutation([4,2,1,3])
sage: p.permutohedron_succ()
[[4, 2, 3, 1]]
sage: p.permutohedron_succ(side='left')
[[4, 3, 1, 2]]
Return the permutation that comes directly before self in lexicographic order on the symmetric group containing self. If self is the first permutation, then it returns False.
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]
Return the rank of self in the lexicographic ordering on the symmetric group to which self 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
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()
[]
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()
[]
Return a 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,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()
[]
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()
[]
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 the
operator 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()
[[]]
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
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
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
Return the plain retract of the permutation self in
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 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
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]
Return the permutation obtained by composing self with rp in such an order that self is applied first and rp is applied afterwards.
This is usually denoted by either self * rp or rp * self
depending on the conventions used by the author. If the value
of a permutation on an integer
is denoted by
, then this
should be denoted by rp * self in order to have
associativity (i.e., in order to have
for 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 have
for 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]
Return the list of the permutations belonging to the right permutohedron interval where self is the minimal element and other the maximal element.
See permutohedron_lequal() for the definition of the permutohedron orders.
EXAMPLES:
sage: 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
Return an iterator on the permutations (represented as integer lists) belonging to the right permutohedron interval where self is the minimal element and other the maximal element.
See permutohedron_lequal() for the definition of the permutohedron orders.
EXAMPLES:
sage: 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]]
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]]
Return the pair of standard tableaux obtained by running the Robinson-Schensted algorithm on self.
This can also be done by running RSK() on self (with the optional argument check_standard=True to return standard Young tableaux).
EXAMPLES:
sage: Permutation([6,2,3,1,7,5,4]).robinson_schensted()
[[[1, 3, 4], [2, 5], [6, 7]], [[1, 3, 5], [2, 6], [4, 7]]]
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.
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]]
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
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]
Return the right (or left) shifted concatenation of self with a permutation other. These operations are also known as the Loday-Ronco over and under operations.
INPUT:
OUTPUT:
If side is "right", the method returns the permutation
obtained by concatenating self with the letters of other
incremented by the size of self. This is what is called
side / other in [LodRon0102066], and denoted as the “over”
operation.
Otherwise, i. e., when side is "left", the method
returns the permutation obtained by concatenating the letters
of other incremented by the size of self with self.
This is what is called side \ other in [LodRon0102066]
(which seems to use the
convention 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. |
Return the shifted shuffle of two permutations self and other.
INPUT:
OUTPUT:
The list of the permutations appearing in the shifted shuffle of the permutations self and other.
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 the shifted_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
Display the permutation as a drawing.
INPUT:
representation – different kinds of drawings are available
"cycles" (default) – the permutation is displayed as a collection of directed cycles
"braid" – the permutation is displayed as segments linking
each element to its image on a parallel line.
When using this drawing, it is also possible to display the permutation horizontally (orientation = "landscape", default option) or vertically (orientation = "portrait").
"chord-diagram" – the permutation is displayed as a directed graph, all of its vertices being located on a circle.
All additional arguments are forwarded to the show subcalls.
EXAMPLES:
sage: 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'
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 for signature().
EXAMPLES:
sage: Permutation([4, 2, 3, 1, 5]).signature()
-1
sage: Permutation([1,3,2,5,4]).sign()
1
sage: Permutation([]).sign()
1
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 for signature().
EXAMPLES:
sage: Permutation([4, 2, 3, 1, 5]).signature()
-1
sage: Permutation([1,3,2,5,4]).sign()
1
sage: Permutation([]).sign()
1
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:
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
Return the size of self.
EXAMPLES:
sage: Permutation([3,4,1,2,5]).size()
5
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 permutation under
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 to True, the method instead iterates over the equivalence class of self with respect to the left sylvester congruence. The left sylvester congruence is easiest to define by saying that two permutations are equivalent under it if and only if their reverses (reverse()) are equivalent under (standard) sylvester congruence.
EXAMPLES:
The sylvester class of a permutation in :
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]]
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
Return the permutation self as a list of disjoint cycles.
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)]
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]") # not tested
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
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]
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
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:
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]
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]
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()
()
Return a tableau of shape shape with the entries in self. 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) is self.
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]
Return all the numbers self[i] such that self[i] >= i+1.
EXAMPLES:
sage: Permutation([1,4,3,2,5]).weak_excedences()
[1, 4, 3, 5]
Bases: sage.structure.parent.Parent, sage.structure.unique_representation.UniqueRepresentation
Permutations.
Permutations(n) returns the class of permutations of n, if n is an integer, list, set, or string.
Permutations(n, k) returns the class of length-k partial
permutations of n (where n is any of the above things); k
must be a nonnegative integer. A length- 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 or k along with a keyword.
Permutations(descents=(list,n)) returns the class of permutations of
with descents in the positions specified by list. This uses the
slightly nonstandard convention that the images of
under the
permutation are regarded as positions
, so for example the
presence of
in list signifies that the permutations
should
satisfy
.
Note that list is supposed to be a list of positions of the descents,
not the descents composition.
The alternative syntax Permutations(descents=list) is deprecated. It
used to boil down Permutations(descents=(list, max(list) + 2))
(unless the list list is empty). It does not return the class of
permutations with descents composition list.
Permutations(bruhat_smaller=p) and Permutations(bruhat_greater=p) return the class of permutations smaller-or-equal or greater-or-equal, respectively, than the given permutation p in the Bruhat order. (The Bruhat order is defined in bruhat_lequal(). It is also referred to as the strong Bruhat order.)
Permutations(recoils=p) returns the class of permutations whose recoils composition is p. Unlike the descents=(list, n) syntax, this actually takes a composition as input.
Permutations(recoils_fatter=p) and Permutations(recoils_finer=p) return the class of permutations whose recoils composition is fatter or finer, respectively, than the given composition p.
Permutations(n, avoiding=P) returns the class of permutations of n avoiding P. Here P may be a single permutation or a list of permutations; the returned class will avoid all patterns in P.
EXAMPLES:
sage: p = Permutations(3); p
Standard permutations of 3
sage: p.list()
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: p = Permutations(3, 2); p
Permutations of {1,...,3} of length 2
sage: p.list()
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
sage: p = Permutations(['c', 'a', 't']); p
Permutations of the set ['c', 'a', 't']
sage: p.list()
[['c', 'a', 't'],
['c', 't', 'a'],
['a', 'c', 't'],
['a', 't', 'c'],
['t', 'c', 'a'],
['t', 'a', 'c']]
sage: p = Permutations(['c', 'a', 't'], 2); p
Permutations of the set ['c', 'a', 't'] of length 2
sage: p.list()
[['c', 'a'], ['c', 't'], ['a', 'c'], ['a', 't'], ['t', 'c'], ['t', 'a']]
sage: p = Permutations([1,1,2]); p
Permutations of the multi-set [1, 1, 2]
sage: p.list()
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]
sage: p = Permutations([1,1,2], 2); p
Permutations of the multi-set [1, 1, 2] of length 2
sage: p.list()
[[1, 1], [1, 2], [2, 1]]
sage: p = Permutations(descents=([1], 4)); p
Standard permutations of 4 with descents [1]
sage: p.list()
[[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()
[1, 3, 5, 4, 2]
alias of Permutation
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:
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.
Bases: sage.combinat.permutation.Permutations_setk
This exists solely for unpickling PermutationsNK objects created with Sage <= 6.3.
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.
Bases: sage.structure.list_clone.ClonableArray
A permutation of an arbitrary multiset.
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()
EXAMPLES:
sage: Permutations([1,2,2]).cardinality()
3
sage: Permutations([1,1,2,2,2]).cardinality()
10
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
.
Bases: sage.combinat.permutation.Permutations
Length- partial permutations of
.
Bases: sage.structure.list_clone.ClonableArray
A length- partial permutation of
.
Verify that self is a valid length- partial
permutation of
.
EXAMPLES:
sage: S = Permutations(4, 2)
sage: elt = S([3, 1])
sage: elt.check()
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
EXAMPLES:
sage: Permutations(3,2).random_element()
[0, 1]
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.
Bases: sage.structure.list_clone.ClonableArray
A permutation of an arbitrary set.
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()
EXAMPLES:
sage: Permutations([1,2,3]).cardinality()
6
EXAMPLES:
sage: Permutations([1,2,3]).random_element()
[1, 2, 3]
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
.
EXAMPLES:
sage: Permutations([1,2,3],2).random_element()
[1, 2]
Bases: sage.combinat.permutation.Permutations
All standard permutations.
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[1, 2])
sage: TestSuite(P).run()
Return the cardinality of self.
EXAMPLES:
sage: P = Permutations(3, avoiding=[1, 2])
sage: P.cardinality()
1
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[2, 1, 3])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[1, 2, 3]).cardinality()
42
sage: len( Permutations(5, avoiding=[1, 2, 3]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[1, 3, 2])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[1, 3, 2]).cardinality()
42
sage: len( Permutations(5, avoiding=[1, 3, 2]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[2, 1])
sage: TestSuite(P).run()
Return the cardinality of self.
EXAMPLES:
sage: P = Permutations(3, avoiding=[2, 1])
sage: P.cardinality()
1
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[2, 1, 3])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[2, 1, 3]).cardinality()
42
sage: len( Permutations(5, avoiding=[2, 1, 3]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[2, 3, 1])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[2, 3, 1]).cardinality()
42
sage: len( Permutations(5, avoiding=[2, 3, 1]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[3, 1, 2])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[3, 1, 2]).cardinality()
42
sage: len( Permutations(5, avoiding=[3, 1, 2]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_avoiding_generic
TESTS:
sage: P = Permutations(3, avoiding=[3, 2, 1])
sage: TestSuite(P).run()
EXAMPLES:
sage: Permutations(5, avoiding=[3, 2, 1]).cardinality()
42
sage: len( Permutations(5, avoiding=[3, 2, 1]).list() )
42
Bases: sage.combinat.permutation.StandardPermutations_n
Generic class for subset of permutations avoiding a particular pattern.
Return the cardinality of self.
EXAMPLES:
sage: P = Permutations(3, avoiding=[[2, 1, 3],[1,2,3]])
sage: P.cardinality()
4
Bases: sage.combinat.permutation.Permutations
Permutations of that are greater than or equal to a
permutation
in the Bruhat order.
Bases: sage.combinat.permutation.Permutations
Permutations of that are less than or equal to a
permutation
in the Bruhat order.
Bases: sage.combinat.permutation.StandardPermutations_n
Permutations of with a fixed set of descents.
Return the cardinality of self.
EXAMPLES:
sage: P = Permutations(descents=([1,0,2],5))
sage: P.cardinality()
4
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]
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]
Bases: sage.combinat.permutation.Permutations
Permutations of the set .
These are also called permutations of size .
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
Return a permutation with cycle type nu.
If the size of nu is smaller than the size of permutations in self, then some fixed points are added.
EXAMPLES
sage: PP = Permutations(5)
sage: PP.element_in_conjugacy_classes([2,2])
[2, 1, 4, 3, 5]
Return the identity permutation of size .
EXAMPLES:
sage: Permutations(4).identity()
[1, 2, 3, 4]
sage: Permutations(0).identity()
[]
EXAMPLES:
sage: Permutations(4).random_element()
[1, 2, 4, 3]
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]
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
Bases: sage.combinat.permutation.Permutations
Permutations of with a fixed recoils composition.
Bases: sage.combinat.permutation.Permutations
TESTS:
sage: P = Permutations(recoils_fatter=[2,2])
sage: TestSuite(P).run()
Bases: sage.combinat.permutation.Permutations
TESTS:
sage: P = Permutations(recoils_finer=[2,2])
sage: TestSuite(P).run()
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:
OUTPUT:
Note
See also
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
Return True if p1 is less than p2 in the Bruhat order.
Algorithm from mupad-combinat.
EXAMPLES:
sage: import sage.combinat.permutation as permutation
sage: permutation.bruhat_lequal([2,4,3,1],[3,4,2,1])
True
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]
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]
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]]
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
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([])
[]
Return the permutation with Lehmer code lehmer.
EXAMPLES:
sage: import sage.combinat.permutation as permutation
sage: Permutation([2,1,5,4,3]).to_lehmer_code()
[1, 0, 2, 1, 0]
sage: permutation.from_lehmer_code(_)
[2, 1, 5, 4, 3]
Return the permutation with major code mc.
The major code of a permutation is defined in to_major_code().
Warning
This function creates illegal permutations (i.e. Permutation([9]),
and this is dangerous as the Permutation() class is only designed
to handle permutations on . 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:
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
Return a Permutation given a PermutationGroupElement pge.
EXAMPLES:
sage: import sage.combinat.permutation as permutation
sage: pge = PermutationGroupElement([(1,2),(3,4)])
sage: permutation.from_permutation_group_element(pge)
[2, 1, 4, 3]
Return the permutation of the set with lexicographic
rank rank. This is the permutation whose Lehmer code is the
factoradic representation of rank. In particular, the
permutation with rank
is the identity permutation.
The permutation is computed without iterating through all of the permutations with lower rank. This makes it efficient for large permutations.
Note
The variable rank is not checked for being in the interval
from to
. 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]
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([])
[]
Return True if p1 is less than or equal to p2 in the permutohedron order.
By default, the computations are done in the right permutohedron. If you pass the option side='left', then they will be done in the left permutohedron.
EXAMPLES:
sage: import sage.combinat.permutation as permutation
sage: permutation.permutohedron_lequal(Permutation([3,2,1,4]),Permutation([4,2,1,3]))
False
sage: permutation.permutohedron_lequal(Permutation([3,2,1,4]),Permutation([4,2,1,3]), side='left')
True
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]