Permutations

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

Warning

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

What does this file define ?

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

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

Methods of Permutations objects

size() Returns the size of the permutation ‘self’.
cycle_string() Returns a string of the permutation in cycle notation.
next() Returns the permutation that follows p in lexicographic order.
prev() Returns the permutation that comes directly before p in lexicographic order.
to_tableau_by_shape() Returns a tableau of shape shape with the entries in self.
to_cycles() Returns the permutation p as a list of disjoint cycles.
to_permutation_group_element() Returns a PermutationGroupElement equal to self.
signature() Returns the signature of a permutation.
is_even() Returns True if the permutation p is even and false otherwise.
to_matrix() Returns a matrix representing the permutation.
rank() Returns the rank of a permutation in lexicographic ordering.
to_inversion_vector() Returns the inversion vector of a permutation p.
inversions() Returns a list of the inversions of permutation p.
show() Displays the permutation as a drawing.
number_of_inversions() Returns the number of inversions in the permutation p.
length() Returns the Coxeter length of a permutation p.
inverse() Returns the inverse of a permutation
ishift() Returns an the i-shift of self.
iswitch() Returns an the i-switch of self.
runs() Returns a list of the runs in the permutation p.
longest_increasing_subsequence_length() Returns the length of the longest increasing subsequences
longest_increasing_subsequences() Returns the list of the longest increasing subsequences
cycle_type() Returns a partition of len(p) corresponding to the cycle type of p.
to_lehmer_code() Returns the Lehmer code of the permutation p.
to_lehmer_cocode() Returns the Lehmer cocode of p.
reduced_word() Returns the reduced word of a permutation.
reduced_words() Returns a list of the reduced words of the permutation p.
reduced_word_lexmin() Returns a lexicographically minimal reduced word of a permutation.
fixed_points() Returns a list of the fixed points of the permutation p.
number_of_fixed_points() Returns the number of fixed points of the permutation p.
recoils() Returns the list of the positions of the recoils of the permutation
number_of_recoils() Returns the number of recoils of the permutation p.
recoils_composition() Returns the composition corresponding to recoils
descents() Returns the list of the descents of the permutation p.
idescents() Returns a list of the idescents of self
idescents_signature() Each position in self is mapped to -1 if it is an idescent and 1 if it is not an idescent.
number_of_descents() Returns the number of descents of the permutation p.
number_of_idescents() Returns the number of descents of the permutation p.
descents_composition() Returns the composition corresponding to the descents.
descent_polynomial() Returns the descent polynomial of the permutation p.
major_index() Returns the major index of the permutation p.
imajor_index() Returns the inverse major index of the permutation self.
to_major_code() Returns the major code of the permutation p.
peaks() Returns a list of the peaks of the permutation p.
number_of_peaks() Returns the number of peaks of the permutation p.
saliances() Returns a list of the saliances of the permutation p.
number_of_saliances() Returns the number of saliances of the permutation p.
bruhat_lequal() Returns True if self is less than 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 p such that the application of this inversion to p decrements its number of inversions.
bruhat_inversions_iterator() Returns an iterator over Bruhat inversions
bruhat_succ() Returns a list of the permutations strictly greater than p in the Bruhat order such that there is no permutation between one of those and p.
bruhat_succ_iterator() An iterator for the permutations that are strictly greater than p in the Bruhat order such that there is no permutation between one of those and p.
bruhat_pred() Returns a list of the permutations strictly smaller than p in the Bruhat order such that there is no permutation between one of those and p.
bruhat_pred_iterator() An iterator for the permutations strictly smaller than p in the Bruhat order such that there is no permutation between one of those and p.
bruhat_smaller() Returns a the combinatorial class of permutations smaller than or equal to p in the Bruhat order.
bruhat_greater() Returns the combinatorial class of permutations greater than or equal to p in the Bruhat order.
permutohedron_lequal() Returns True if self is less than p2 in the permutohedron order.
permutohedron_succ() Returns a list of the permutations strictly greater than p in the permutohedron order such that there is no permutation between one of those and p.
permutohedron_pred() Returns a list of the permutations strictly smaller than p in the permutohedron order such that there is no permutation between one of those and p.
permutohedron_smaller() Returns a list of permutations smaller than or equal to p in the permutohedron order.
permutohedron_greater() Returns a list of permutations greater than or equal to p in the permutohedron order.
has_pattern() Tests whether the permutation matches the pattern.
avoids() Tests whether the permutation avoids the pattern.
pattern_positions() Returns the list of positions where the pattern patt appears in p.
reverse() Returns the permutation obtained by reversing the list.
complement() Returns the complement of the permutation which is obtained by replacing each value x in the list with n - x + 1
dict() Returns a dictionary corresponding to the permutation.
action() Returns the action of the permutation on a list.
robinson_schensted() Returns the pair of standard tableaux obtained by running the Robinson-Schensted Algorithm on self.
left_tableau() Returns the right standard tableau after performing the RSK
right_tableau() Returns the right standard tableau after performing the RSK
remove_extra_fixed_points() Returns the permutation obtained by removing any fixed points at the end of self.
hyperoctahedral_double_coset_type() Returns the coset-type of self as a partition.

Other classes defined in this file

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

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. The
from_inversion_vector() Returns the permutation corresponding to inversion vector iv.
from_cycles() Returns the permutation corresponding to cycles.
from_lehmer_code() Returns the permutation with Lehmer code lehmer.
from_reduced_word() Returns the permutation corresponding to the reduced word rw.
robinson_schensted_inverse() Returns the permutation corresponding to the pair of tableaux (p,q)
bistochastic_as_sum_of_permutations() Returns the matrix as a linear combination of permutations.
descents_composition_list() Returns a list of all the permutations that have a descent
descents_composition_first() Computes the smallest element of a descent class having a descent
descents_composition_last() Returns the largest element of a descent class having a descent
bruhat_lequal() Returns True if p1 is less than p2 in the Bruhat order.
permutohedron_lequal() Returns True if p1 is less than p2 in the permutohedron order.
to_standard() Returns a standard permutation corresponding to the permutation p.

AUTHORS:

  • Mike Hansen
  • Dan Drake (2008-04-07): allow Permutation() to take lists of tuples
  • Sebastien Labbe (2009-03-17): added robinson_schensted_inverse
  • Travis Scrimshaw (2012-08-16): to_standard() no longer modifies input

Classes and methods

sage.combinat.permutation.Arrangements(mset, k)

An arrangement of mset is an ordered selection without repetitions and 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']]
class sage.combinat.permutation.Arrangements_msetk(mset, k)

Bases: sage.combinat.permutation.Permutations_msetk

TESTS:

sage: P = Permutations([1,2,2],2)
sage: P == loads(dumps(P))
True
class sage.combinat.permutation.Arrangements_setk(s, k)

Bases: sage.combinat.permutation.Permutations_setk

TESTS:

sage: P = Permutations([1,2,3],2)
sage: P == loads(dumps(P))
True
sage.combinat.permutation.CyclicPermutations(mset)

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

EXAMPLES:

sage: CyclicPermutations(range(4)).list()
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
sage: CyclicPermutations([1,1,1]).list()
[[1, 1, 1]]
sage.combinat.permutation.CyclicPermutationsOfPartition(partition)

Returns the combinatorial class of all combinations of cyclic permutations of each cell of the partition. This is the same as a Cartesian product of necklaces.

EXAMPLES:

sage: CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]).list()
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]
sage: CyclicPermutationsOfPartition([[1,2,3,4],[4,4,4]]).list()
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]
class sage.combinat.permutation.CyclicPermutationsOfPartition_partition(partition)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: CP = CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]])
sage: CP == loads(dumps(CP))
True
iterator(distinct=False)

AUTHORS:

  • Robert Miller

EXAMPLES:

sage: CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]).list() # indirect doctest
[[[1, 2, 3, 4], [5, 6, 7]],
 [[1, 2, 4, 3], [5, 6, 7]],
 [[1, 3, 2, 4], [5, 6, 7]],
 [[1, 3, 4, 2], [5, 6, 7]],
 [[1, 4, 2, 3], [5, 6, 7]],
 [[1, 4, 3, 2], [5, 6, 7]],
 [[1, 2, 3, 4], [5, 7, 6]],
 [[1, 2, 4, 3], [5, 7, 6]],
 [[1, 3, 2, 4], [5, 7, 6]],
 [[1, 3, 4, 2], [5, 7, 6]],
 [[1, 4, 2, 3], [5, 7, 6]],
 [[1, 4, 3, 2], [5, 7, 6]]]
sage: CyclicPermutationsOfPartition([[1,2,3,4],[4,4,4]]).list()
[[[1, 2, 3, 4], [4, 4, 4]],
 [[1, 2, 4, 3], [4, 4, 4]],
 [[1, 3, 2, 4], [4, 4, 4]],
 [[1, 3, 4, 2], [4, 4, 4]],
 [[1, 4, 2, 3], [4, 4, 4]],
 [[1, 4, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]
list(distinct=False)

EXAMPLES:

sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list()
[[[1, 2, 3], [4, 4, 4]], [[1, 3, 2], [4, 4, 4]]]
sage: CyclicPermutationsOfPartition([[1,2,3],[4,4,4]]).list(distinct=True)
[[[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]],
 [[1, 2, 3], [4, 4, 4]],
 [[1, 3, 2], [4, 4, 4]]]
class sage.combinat.permutation.CyclicPermutations_mset(mset)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: CP = CyclicPermutations(range(4))
sage: CP == loads(dumps(CP))
True
iterator(distinct=False)

EXAMPLES:

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

EXAMPLES:

sage: CyclicPermutations(range(4)).list()
[[0, 1, 2, 3],
 [0, 1, 3, 2],
 [0, 2, 1, 3],
 [0, 2, 3, 1],
 [0, 3, 1, 2],
 [0, 3, 2, 1]]
class sage.combinat.permutation.PatternAvoider(n, patterns)

Bases: sage.combinat.backtrack.GenericBacktracker

EXAMPLES:

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

Converts l to a permutation on 1...n

INPUT:

  • an instance of Permutation_class,

  • list of integers, viewed as one-line permutation notation,

  • string, expressing the permutation in cycle notation,

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

  • a PermutationGroupElement

  • a pair of two tableaux of the same shape, where the second one is standard. This uses the inverse of Robinson Schensted algorithm.

  • check_input (boolean) – whether to check that input is correct. Slows

    the function down, but ensures that nothing bad happens. This is set to True by default.

Warning

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

OUTPUT:

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: p = Permutation((1, 2, 5)); p
[2, 5, 3, 4, 1]
sage: type(p)
<class 'sage.combinat.permutation.Permutation_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 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([()])
[1]
sage: Permutation('()')
[1]
sage: Permutation(())
[1]

From a pair of empty tableaux

sage: Permutation( ([], []) )
[]
sage: Permutation( [[], []] )
[]
sage.combinat.permutation.PermutationOptions(**kwargs)

Sets 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).

display: ‘list’ - the permutations are displayed in list notation ‘cycle’ - the permutations are displayed in cycle notation ‘singleton’ - the permutations are displayed in cycle notation with singleton cycles shown as well.

mult: ‘l2r’ - the multiplication of permutations is done like composition of functions from left to right. That is, if we think of the permutations p1 and p2 as functions, then (p1*p2)(x) = p2(p1(x)). This is the default in multiplication in GAP. ‘r2l’ - the multiplication of permutations is done right to left so that (p1*p2)(x) = p1(p2(x))

If no parameters are set, then the function returns a copy of the options dictionary.

Note that these options have no effect on PermutationGroupElements.

EXAMPLES:

sage: p213 = Permutation([2,1,3])
sage: p312 = Permutation([3,1,2])
sage: PermutationOptions(mult='l2r', display='list')
sage: po = PermutationOptions()
sage: po['display']
'list'
sage: p213
[2, 1, 3]
sage: PermutationOptions(display='cycle')
sage: p213
(1,2)
sage: PermutationOptions(display='singleton')
sage: p213
(1,2)(3)
sage: PermutationOptions(display='list')
sage: po['mult']
'l2r'
sage: p213*p312
[1, 3, 2]
sage: PermutationOptions(mult='r2l')
sage: p213*p312
[3, 2, 1]
sage: PermutationOptions(mult='l2r')
class sage.combinat.permutation.Permutation_class(l, check_input=True)

Bases: sage.combinat.combinat.CombinatorialObject

Constructor. Checks that INPUT is not a mess, and calls CombinatorialObject. It should not, because CombinatorialObject is deprecated.

INPUT:

  • l – a list of int variables.

  • check_input (boolean) – whether to check that input is correct. Slows the function down, but ensures that nothing bad happens.

    This is set to True by default.

TESTS:

sage: from sage.combinat.permutation import Permutation_class
sage: Permutation_class([1,2,3])
[1, 2, 3]
sage: Permutation_class([1,2,2,4])
Traceback (most recent call last):
...
ValueError: An element appears twice in the input. It should not.
sage: Permutation_class([1,2,4,-1])
Traceback (most recent call last):
...
ValueError: The elements must be strictly positive integers.
sage: Permutation_class([1,2,4,5])
Traceback (most recent call last):
...
ValueError: The permutation has length 4 but its maximal element is
5. Some element may be repeated, or an element is missing, but there
is something wrong with its length.
RS_partition(*args, **kwds)

Returns the partition corresponding to the tableaux of the RSK algorithm.

EXAMPLES:

sage: Permutation([1,4,3,2]).RS_partition()
[2, 1, 1]
action(a)

Returns the action of the permutation on a list.

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)
avoids(patt)

Tests whether the permutation avoids the pattern.

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
bruhat_greater()

Returns the combinatorial class of permutations greater than or equal to p in the Bruhat order.

EXAMPLES:

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

Returns the list of inversions of p such that the application of this inversion to p decrements its number of inversions.

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

EXAMPLES:

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

Returns the iterator for the inversions of p such that the application of this inversion to p decrements its number of inversions.

EXAMPLES:

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

Returns True if self is less than p2 in the Bruhat order.

EXAMPLES:

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

Returns a list of the permutations strictly smaller than p in the Bruhat order such that there is no permutation between one of those and p.

EXAMPLES:

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

An iterator for the permutations strictly smaller than p in the Bruhat order such that there is no permutation between one of those and p.

EXAMPLES:

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

Returns a the combinatorial class of permutations smaller than or equal to p in the Bruhat order.

EXAMPLES:

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

Returns a list of the permutations strictly greater than p in the Bruhat order such that there is no permutation between one of those and p.

EXAMPLES:

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

An iterator for the permutations that are strictly greater than p in the Bruhat order such that there is no permutation between one of those and p.

EXAMPLES:

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

Returns the complement of the permutation which is obtained by replacing each value x in the list with n - x + 1.

EXAMPLES:

sage: Permutation([1,2,3]).complement()
[3, 2, 1]
sage: Permutation([1, 3, 2]).complement()
[3, 1, 2]
cycle_string(singletons=False)

Returns a string of the permutation in cycle notation.

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

EXAMPLES:

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

Returns the permutation p as a list of disjoint cycles.

If singletons=False is given, don’t returns the singletons in the list of 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 O(n) where n 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 one:

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
cycle_type()

Returns a partition of len(p) corresponding to the cycle type of p. This is a non-increasing sequence of the cycle lengths of p.

EXAMPLES:

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

Returns the descent polynomial of the permutation p.

The descent polynomial of p is the product of all the z[p[i]] where i ranges over the descents of p.

REFERENCES:

  • Garsia and Stanton 1984

EXAMPLES:

sage: Permutation([2,1,3]).descent_polynomial()
z1
sage: Permutation([4,3,2,1]).descent_polynomial()
z1*z2^2*z3^3
descents(final_descent=False)

Returns the list of the descents of the permutation p.

A descent of a permutation is an integer i such that p[i] > p[i+1]. 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]).descents()
[1, 2]
sage: Permutation([1,4,3,2]).descents(final_descent=True)
[1, 2, 3]
descents_composition(*args, **kwds)

Returns the composition corresponding to the descents of the permutation.

EXAMPLES:

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

Returns a dictionary corresponding to the permutation.

EXAMPLES:

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

Returns a list of the fixed points of the permutation p.

EXAMPLES:

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

Tests whether the permutation matches the pattern.

EXAMPLES:

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

Returns the coset-type of self as a partition.

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

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

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 (chapter VII).
idescents(final_descent=False)

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

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(final_descent=True)
[1, 2, 3]
idescents_signature(final_descent=False)

Each position in self is mapped to -1 if it is an idescent and 1 if it is not an idescent.

EXAMPLES:

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

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

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

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
inverse(*args, **kwds)

Returns the inverse of a permutation

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]
inversions()

Returns a list of the inversions of permutation p.

EXAMPLES:

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

Returns True if the permutation p is even and false otherwise.

EXAMPLES:

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

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

An i-shift can be applied when i is not in between i-1 and i+1. The i-shift moves i to the other side, and leaves the relative positions of i-1 and i+1 in place.

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

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

Note that the movement is done in place:

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

Since 2 is between 1 and 3 in [1,2,3], an 2-shift cannot be applied.

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

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

An i-shift can be applied when i is not in between i-1 and i+1. The i-shift moves i to the other side, and switches the relative positions of i-1 and i+1 in place.

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

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

Note that the movement is done in place:

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

Since 2 is between 1 and 3 in [1,2,3], an 2-switch cannot be applied.

sage: Permutation([1,2,3]).iswitch(2) 
[1, 2, 3]
left_tableau(*args, **kwds)

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

EXAMPLES:

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

Returns the Coxeter length of a permutation p. The length is given by the number of inversions of p.

EXAMPLES:

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

Returns the length of the longest increasing subsequences of the permutation p.

EXAMPLES:

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

Returns the list of the longest increasing subsequences of the permutation p.

Note

The algorithm is not optimal.

EXAMPLES:

sage: Permutation([2,3,4,1]).longest_increasing_subsequences()
[[2, 3, 4]]
sage: Permutation([5, 7, 1, 2, 6, 4, 3]).longest_increasing_subsequences()
[[1, 2, 6], [1, 2, 4], [1, 2, 3]]
major_index(final_descent=False)

Returns the major index of the permutation p.

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

EXAMPLES:

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

Returns the permutation that follows p in lexicographic order. If p 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
number_of_descents(final_descent=False)

Returns the number of descents of the permutation p.

EXAMPLES:

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

Returns the number of fixed points of the permutation p.

EXAMPLES:

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

Returns the number of descents of the permutation p.

EXAMPLES:

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

Returns the number of inversions in the permutation p.

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

REFERENCES:

EXAMPLES:

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

Returns the number of peaks of the permutation p.

A peak of a permutation is an integer i such that p[i-1] < p[i] and p[i] > p[i+1].

EXAMPLES:

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

Returns the number of recoils of the permutation p.

EXAMPLES:

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

Returns the number of saliances of the permutation p.

EXAMPLES:

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

Returns the list of positions where the pattern patt appears in p.

EXAMPLES:

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

Returns a list of the peaks of the permutation p.

A peak of a permutation is an integer i such that p[i-1] < p[i] and p[i] > p[i+1].

EXAMPLES:

sage: Permutation([1,3,2,4,5]).peaks()
[1]
sage: Permutation([4,1,3,2,6,5]).peaks()
[2, 4]
permutohedron_greater(side='right')

Returns a list of permutations greater than or equal to p 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: Permutation([4,2,1,3]).permutohedron_greater()
[[4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1]]
sage: Permutation([4,2,1,3]).permutohedron_greater(side='left')
[[4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]
permutohedron_lequal(p2, side='right')

Returns True if self is less than 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: 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
permutohedron_pred(side='right')

Returns a list of the permutations strictly smaller than p in the permutohedron order such that there is no permutation between one of those and p.

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: p = Permutation([4,2,1,3])
sage: p.permutohedron_pred()            
[[2, 4, 1, 3], [4, 1, 2, 3]]
sage: p.permutohedron_pred(side='left')
[[4, 1, 2, 3], [3, 2, 1, 4]]
permutohedron_smaller(side='right')

Returns a list of permutations smaller than or equal to p 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: Permutation([4,2,1,3]).permutohedron_smaller()
[[1, 2, 3, 4],
 [1, 2, 4, 3],
 [1, 4, 2, 3],
 [2, 1, 3, 4],
 [2, 1, 4, 3],
 [2, 4, 1, 3],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]
sage: Permutation([4,2,1,3]).permutohedron_smaller(side='left')
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [2, 1, 3, 4],
 [2, 3, 1, 4],
 [3, 1, 2, 4],
 [3, 2, 1, 4],
 [4, 1, 2, 3],
 [4, 2, 1, 3]]
permutohedron_succ(side='right')

Returns a list of the permutations strictly greater than p in the permutohedron order such that there is no permutation between one of those and p.

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: p = Permutation([4,2,1,3])
sage: p.permutohedron_succ()
[[4, 2, 3, 1]]
sage: p.permutohedron_succ(side='left')
[[4, 3, 1, 2]]
prev()

Returns the permutation that comes directly before p in lexicographic order. If p 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]
rank()

Returns the rank of a permutation in lexicographic ordering.

EXAMPLES:

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

Returns the list of the positions of the recoils of the permutation p.

A recoil of a permutation is an integer i such that i+1 is to the left of it.

EXAMPLES:

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

Returns the composition corresponding to recoils of the permutation.

EXAMPLES:

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

Returns the reduced word of a permutation.

EXAMPLES:

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

Returns a lexicographically minimal reduced word of a permutation.

EXAMPLES:

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

Returns a list of the reduced words of the permutation p.

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]]
remove_extra_fixed_points()

Returns 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]
reverse(*args, **kwds)

Returns the permutation obtained by reversing the list.

EXAMPLES:

sage: Permutation([3,4,1,2]).reverse()
[2, 1, 4, 3]
sage: Permutation([1,2,3,4,5]).reverse()
[5, 4, 3, 2, 1]
right_tableau(*args, **kwds)

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

EXAMPLES:

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

Returns the pair of standard tableaux obtained by running the Robinson-Schensted Algorithm on self.

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]]]

Warning

The following example does not check their input. This is wrong. See trac ticket #13742.

It also works in the case of repeated letters. In this case only the second tableau is standard:

sage: Permutation([2,3,3,2,1,3,2,3], check_input = False).robinson_schensted()
[[[1, 2, 2, 3, 3], [2, 3], [3]], [[1, 2, 3, 6, 8], [4, 7], [5]]]

TESTS:

The empty permutation:

sage: p = Permutation([])
sage: p.robinson_schensted()
[[], []]
runs()

Returns a list of the runs in the permutation p.

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]]
saliances()

Returns a list of the saliances of the permutation p.

A saliance of a permutation p is an integer i such that p[i] > p[j] for all j > i.

EXAMPLES:

sage: Permutation([2,3,1,5,4]).saliances()
[3, 4]
sage: Permutation([5,4,3,2,1]).saliances()
[0, 1, 2, 3, 4]
show(representation='cycles', orientation='landscape', **args)

Displays the permutation as a drawing.

INPUT:

  • representation – different kinds of drawings are available

    • "cycles" (default) – the permutation is displayed as a collection of directed cycles

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

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

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

All additional arguments are forwarded to the show subcalls.

EXAMPLES:

sage: 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-digraph' or 'braid'
sign(p)

Returns the signature of a permutation.

Note

sign may be used as an alias to signature.

EXAMPLES:

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

Returns the signature of a permutation.

Note

sign may be used as an alias to signature.

EXAMPLES:

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

Returns the size of the permutation ‘self’.

EXAMPLES:

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

Returns the permutation p as a list of disjoint cycles.

If singletons=False is given, don’t returns the singletons in the list of 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 O(n) where n 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 one:

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
to_inversion_vector()

Returns the inversion vector of a permutation p.

If iv is the inversion vector, then iv[i] is the number of elements larger than i that appear to the left of i in the permutation.

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

EXAMPLES:

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

TESTS:

sage: from sage.combinat.permutation import from_inversion_vector
sage: all(from_inversion_vector(p.to_inversion_vector()) == p
...     for n in range(6) for p in Permutations(n))
True

sage: P = Permutations(1000)
sage: sample = (P.random_element() for i in range(5))
sage: all(from_inversion_vector(p.to_inversion_vector()) == p
...     for p in sample) 
True 
to_lehmer_cocode()

Returns the Lehmer cocode of p.

EXAMPLES:

sage: p = Permutation([2,1,3])
sage: p.to_lehmer_cocode()
[0, 1, 0]
sage: q = Permutation([3,1,2])
sage: q.to_lehmer_cocode()
[0, 1, 1]
to_lehmer_code()

Returns the Lehmer code of the permutation p. c[i] is the number of j>i such that p(j)<p(i).

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]

TESTS:

sage: from sage.combinat.permutation import from_lehmer_code
sage: all(from_lehmer_code(p.to_lehmer_code()) == p
...     for n in range(6) for p in Permutations(n))
True

sage: P = Permutations(1000)
sage: sample = (P.random_element() for i in range(5))
sage: all(from_lehmer_code(p.to_lehmer_code()) == p
...     for p in sample) 
True 
to_major_code(final_descent=False)

Returns the major code of the permutation p, which is defined as the list [m1-m2, m2-m3,..,mn] where mi := maj(pi) is the major indices of the permutation math obtained by erasing the letters smaller than math in p.

REFERENCES:

  • Carlitz, L. ‘q-Bernoulli and Eulerian Numbers’ Trans. Amer. Math. Soc. 76 (1954) 332-350 Skandera, M. ‘An Eulerian Partner for Inversions’, Sem. Lothar. Combin. 46 (2001) B46d.

EXAMPLES:

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

Returns a matrix representing the permutation.

EXAMPLES:

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

Notice that matrix multiplication corresponds to permutation multiplication only when the permutation option mult=’r2l’

sage: PermutationOptions(mult='r2l')
sage: p = Permutation([2,1,3])
sage: q = Permutation([3,1,2])
sage: (p*q).to_matrix()
[0 0 1]
[0 1 0]
[1 0 0]
sage: p.to_matrix()*q.to_matrix()
[0 0 1]
[0 1 0]
[1 0 0]
sage: PermutationOptions(mult='l2r')
sage: (p*q).to_matrix()
[1 0 0]
[0 0 1]
[0 1 0]
to_permutation_group_element()

Returns a PermutationGroupElement equal to self.

EXAMPLES:

sage: Permutation([2,1,4,3]).to_permutation_group_element()
(1,2)(3,4)
sage: Permutation([1,2,3]).to_permutation_group_element()
()
to_tableau_by_shape(shape)

Returns a tableau of shape shape with the entries in 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]).to_permutation()
[3, 4, 1, 2, 5]
weak_excedences()

Returns 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]
sage.combinat.permutation.Permutations(n=None, k=None, **kwargs)

Returns a combinatorial class of 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 permutations of n (where n is any of the above things) of length k; k must be an integer.

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) returns the class of permutations with descents in the positions specified by ‘list’.

Permutations(bruhat_smaller,greater=p) returns the class of permutations smaller or greater, respectively, than the given permutation in Bruhat order.

Permutations(recoils=p) returns the class of permutations whose recoils composition is p.

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

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()
[5, 1, 2, 4, 3]
class sage.combinat.permutation.Permutations_mset(mset)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: S = Permutations(['c','a','c'])
sage: S == loads(dumps(S))
True
cardinality()

EXAMPLES:

sage: Permutations([1,2,2]).cardinality()
3
class sage.combinat.permutation.Permutations_msetk(mset, k)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations([1,2,2],2)
sage: P == loads(dumps(P))
True
list()

EXAMPLES:

sage: Permutations([1,2,2],2).list()
[[1, 2], [2, 1], [2, 2]]
class sage.combinat.permutation.Permutations_nk(n, k)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(3,2)
sage: P == loads(dumps(P))
True
cardinality()

EXAMPLES:

sage: Permutations(3,0).cardinality()
1
sage: Permutations(3,1).cardinality()
3
sage: Permutations(3,2).cardinality()
6
sage: Permutations(3,3).cardinality()
6
sage: Permutations(3,4).cardinality()
0
random_element()

EXAMPLES:

sage: Permutations(3,2).random_element()
[0, 1]
class sage.combinat.permutation.Permutations_set(s)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: S = Permutations(['c','a','t'])
sage: S == loads(dumps(S))
True
cardinality()

EXAMPLES:

sage: Permutations([1,2,3]).cardinality()
6
random_element()

EXAMPLES:

sage: Permutations([1,2,3]).random_element()
[1, 2, 3]
class sage.combinat.permutation.Permutations_setk(s, k)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations([1,2,3],2)
sage: P == loads(dumps(P))
True
random_element()

EXAMPLES:

sage: Permutations([1,2,3],2).random_element()
[1, 2]
class sage.combinat.permutation.StandardPermutations_all

Bases: sage.combinat.combinat.InfiniteAbstractCombinatorialClass

TESTS:

sage: SP = Permutations()
sage: SP == loads(dumps(SP))
True
Element

alias of Permutation_class

class sage.combinat.permutation.StandardPermutations_avoiding_12(n)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[1,2])
sage: p == loads(dumps(p))
True
list()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[1, 2, 3])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[1,3,2])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[2,1])
sage: p == loads(dumps(p))
True
list()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[2, 1, 3])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[2, 3, 1])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[3, 1, 2])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: p = Permutations(3, avoiding=[3, 2, 1])
sage: p == loads(dumps(p))
True
cardinality()

EXAMPLES:

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

Bases: sage.combinat.combinat.CombinatorialClass

EXAMPLES:

sage: P = Permutations(3, avoiding=[[2, 1, 3],[1,2,3]])
sage: P == loads(dumps(P))
True
sage: type(P)
<class 'sage.combinat.permutation.StandardPermutations_avoiding_generic'>
class sage.combinat.permutation.StandardPermutations_bruhat_greater(p)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(bruhat_greater=[3,2,1])
sage: P == loads(dumps(P))
True
list()

Returns a list of permutations greater than or equal to p in the Bruhat order.

EXAMPLES:

sage: Permutations(bruhat_greater=[4,1,2,3]).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]]
class sage.combinat.permutation.StandardPermutations_bruhat_smaller(p)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(bruhat_smaller=[3,2,1])
sage: P == loads(dumps(P))
True
list()

Returns a list of permutations smaller than or equal to p in the Bruhat order.

EXAMPLES:

sage: Permutations(bruhat_smaller=[4,1,2,3]).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]]
class sage.combinat.permutation.StandardPermutations_descents(d, n)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(descents=([1,0,4,8],12))
sage: P == loads(dumps(P))
True
Element

alias of Permutation_class

first()

Returns the first permutation with descents d.

EXAMPLES:

sage: Permutations(descents=([1,0,4,8],12)).first()
[3, 2, 1, 4, 6, 5, 7, 8, 10, 9, 11, 12]
last()

Returns the last permutation with descents d.

EXAMPLES:

sage: Permutations(descents=([1,0,4,8],12)).last()
[12, 11, 8, 9, 10, 4, 5, 6, 7, 1, 2, 3]
list()

Returns a list of all the permutations that have the descents d.

EXAMPLES:

sage: Permutations(descents=([2,0],5)).list()
[[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]]
class sage.combinat.permutation.StandardPermutations_n(n)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: SP = Permutations(3)
sage: SP == loads(dumps(SP))
True
Element

alias of Permutation_class

cardinality()

EXAMPLES:

sage: Permutations(0).cardinality()
1
sage: Permutations(3).cardinality()
6
sage: Permutations(4).cardinality()
24
element_in_conjugacy_classes(nu)

Returns 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]
identity()

Returns the identity permutation of length n.

EXAMPLES:

sage: Permutations(4).identity()
[1, 2, 3, 4]
sage: Permutations(0).identity()
[]
random_element()

EXAMPLES:

sage: Permutations(4).random_element()
[1, 2, 4, 3]
rank(p)

EXAMPLES:

sage: SP3 = Permutations(3)
sage: map(SP3.rank, SP3)
[0, 1, 2, 3, 4, 5]
sage: SP0 = Permutations(0)
sage: map(SP0.rank, SP0)
[0]
unrank(r)

EXAMPLES:

sage: SP3 = Permutations(3)
sage: l = map(SP3.unrank, range(6))
sage: l == SP3.list()
True
sage: SP0 = Permutations(0)
sage: l = map(SP0.unrank, range(1))
sage: l == SP0.list()
True
class sage.combinat.permutation.StandardPermutations_recoils(recoils)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(recoils=[2,2])
sage: P == loads(dumps(P))
True
Element

alias of Permutation_class

list()

Returns a list of all of the permutations whose recoils composition is equal to recoils.

EXAMPLES:

sage: Permutations(recoils=[2,2]).list()
[[1, 3, 2, 4], [1, 3, 4, 2], [3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2]]
class sage.combinat.permutation.StandardPermutations_recoilsfatter(recoils)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(recoils_fatter=[2,2])
sage: P == loads(dumps(P))
True
Element

alias of Permutation_class

list()

Returns a list of all of the permutations whose recoils composition is fatter than recoils.

EXAMPLES:

sage: Permutations(recoils_fatter=[2,2]).list()
[[1, 3, 2, 4],
 [1, 3, 4, 2],
 [1, 4, 3, 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],
 [4, 1, 3, 2],
 [4, 3, 1, 2],
 [4, 3, 2, 1]]
class sage.combinat.permutation.StandardPermutations_recoilsfiner(recoils)

Bases: sage.combinat.combinat.CombinatorialClass

TESTS:

sage: P = Permutations(recoils_finer=[2,2])
sage: P == loads(dumps(P))
True
Element

alias of Permutation_class

list()

Returns a list of all of the permutations whose recoils composition is finer than recoils.

EXAMPLES:

sage: Permutations(recoils_finer=[2,2]).list()
[[1, 2, 3, 4],
 [1, 3, 2, 4],
 [1, 3, 4, 2],
 [3, 1, 2, 4],
 [3, 1, 4, 2],
 [3, 4, 1, 2]]
sage.combinat.permutation.bistochastic_as_sum_of_permutations(M, check=True)

Returns the positive sum of permutations corresponding to the bistochastic matrix.

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

According to the Birkhoff-von Neumann Theorem, any bistochastic matrix can be written as a positive sum 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 sum of permutations, this theorem is an equivalence.

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

INPUT:

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

OUTPUT:

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

Note

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

EXAMPLE:

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

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

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

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

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

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

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

Algorithm from mupad-combinat.

EXAMPLES:

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

Computes the smallest element of a descent class having a descent decomposition dc.

EXAMPLES:

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

Returns the largest element of a descent class having a descent decomposition dc.

EXAMPLES:

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

Returns a list of all the permutations that have a descent compositions dc.

EXAMPLES:

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

Returns the permutation corresponding to cycles.

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

Warning

It assumes that the elements are of int type.

EXAMPLES:

sage: import sage.combinat.permutation as permutation
sage: permutation.from_cycles(4, [[1,2]])
[2, 1, 3, 4]

Bad input (see trac ticket #13742):

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

Returns the permutation corresponding to inversion vector iv.

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.combinat.permutation.from_lehmer_code(lehmer)

Returns 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]
sage.combinat.permutation.from_major_code(mc, final_descent=False)

Returns the permutation corresponding to major code mc.

Warning

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

REFERENCES:

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

EXAMPLES:

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

Returns a Permutation give a PermutationGroupElement pge.

EXAMPLES:

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

Returns the permutation with the specified lexicographic rank. The permutation is of the set [1,...,n].

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

EXAMPLES:

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

Returns the permutation corresponding to the reduced word rw.

EXAMPLES:

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

Returns True if p1 is less than p2in the permutohedron order.

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

EXAMPLES:

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

Returns the permutation corresponding to the pair of tableaux (p,q) using the inverse of Robinson-Schensted algorithm.

Warning

This function uses the Permutation_class class in a way it is NOT MEANT to be used (i.e. the permutations are not permutations of integers). Do not trust it. See trac ticket #13742.

INPUT:

  • p, q: two tableaux of the same shape and where q is standard.

EXAMPLES:

sage: from sage.combinat.permutation import robinson_schensted_inverse
sage: t1 = Tableau([[1, 2, 5], [3], [4]])
sage: t2 = Tableau([[1, 2, 3], [4], [5]])
sage: robinson_schensted_inverse(t1, t2)
[1, 4, 5, 3, 2]
sage: robinson_schensted_inverse(t1, t1)
[1, 4, 3, 2, 5]
sage: robinson_schensted_inverse(t2, t2)
[1, 2, 5, 4, 3]
sage: robinson_schensted_inverse(t2, t1)
[1, 5, 4, 2, 3]

If the first tableau is semistandard:

sage: p = Tableau([[1,2,2]]); q = Tableau([[1,2,3]])
sage: robinson_schensted_inverse(p, q)
[1, 2, 2]
sage: _.robinson_schensted()
[[[1, 2, 2]], [[1, 2, 3]]]

Note that currently the constructor of Tableau accept as input lists that are not even tableaux but only filling of a partition diagram. This feature should not be used with robinson_schensted_inverse.

TESTS:

From empty tableaux:

sage: robinson_schensted_inverse(Tableau([]), Tableau([]))
[]

This function is the inverse of robinson_shensted:

sage: f = lambda p: robinson_schensted_inverse(*p.robinson_schensted())
sage: all(p == f(p) for n in range(7) for p in Permutations(n))
True

sage: n = ZZ.random_element(200)
sage: p = Permutations(n).random_element()
sage: is_fine = True if p == f(p) else p ; is_fine
True

Both tableaux must be of the same shape:

sage: robinson_schensted_inverse(Tableau([[1,2,3]]), Tableau([[1,2]]))
Traceback (most recent call last):
...
ValueError: p(=[[1, 2, 3]]) and q(=[[1, 2]]) must have the same shape

The second tableau must be standard:

sage: robinson_schensted_inverse(Tableau([[1,2,3]]), Tableau([[1,3,2]]))
Traceback (most recent call last):
...
ValueError: q(=[[1, 3, 2]]) must be standard
sage.combinat.permutation.to_standard(p)

Returns a standard permutation corresponding to the permutation 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]

Table Of Contents

Previous topic

Partition tuples

Next topic

Perfect matchings

This Page