18.20 Permutations

Module: sage.combinat.permutation

Permutations

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

Author Log:

Module-level Functions

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.

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).count()
 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']]

CyclicPermutations( mset)

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

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

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.

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

Permutation( l)

Convert l to a Permutation, where l is a list of integers, tuple of integers, tuple of tuples of integers, list of tuples of integers, or a string in cycle notation. Tuples are interpreted as cycles; lists of integers as one-line permutation notation. Returns a member of the Permutation class.

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

PermutationOptions( )

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.

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')

Permutations( [n=None], [k=None])

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.

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,3]); p
Standard permutations of 4 with descents [1, 3]
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, 3, 2],
 [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, 3, 2, 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.count()
88
sage: p.random_element()
[5, 1, 2, 4, 3]

bruhat_lequal( p1, p2)

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

Algorithm from mupad-combinat.

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

descents_composition_first( dc)

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

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]

descents_composition_last( dc)

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

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]

descents_composition_list( dc)

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

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

from_cycles( n, cycles)

Returns the permutation corresponding to cycles.

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

from_inversion_vector( iv)

Returns the permutation corresponding to inversion vector iv.

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]

from_lehmer_code( lehmer)

Returns the permutation with Lehmer code lehmer.

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]

from_major_code( mc, [final_descent=False])

Returns the permutation corresponding to major code mc.

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

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]

from_permutation_group_element( pge)

Returns a Permutation give a PermutationGroupElement pge.

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]

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 iteratiing through all of the permutations with lower rank. This makes it efficient for large permutations.

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]

from_reduced_word( rw)

Returns the permutation corresponding to the reduced word rw.

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

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.

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

to_standard( p)

Returns a standard permutation corresponding to the permutation p.

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]

Class: Arrangements_msetk

class Arrangements_msetk

Special Functions: __repr__

__repr__( self)

TESTS:

sage: repr(Arrangements([1,2,2],2))
'Arrangements of the multi-set [1, 2, 2] of length 2'

Class: Arrangements_setk

class Arrangements_setk

Special Functions: __repr__

__repr__( self)

TESTS:

sage: repr(Arrangements([1,2,3],2))
'Arrangements of the set [1, 2, 3] of length 2'

Class: CyclicPermutations_mset

class CyclicPermutations_mset
CyclicPermutations_mset( self, mset)

TESTS:

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

Functions: iterator,$ \,$ list

iterator( self, [distinct=False])

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( self, [distinct=False])

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(CyclicPermutations(range(4)))
'Cyclic permutations of [0, 1, 2, 3]'

Class: CyclicPermutationsOfPartition_partition

class CyclicPermutationsOfPartition_partition
CyclicPermutationsOfPartition_partition( self, partition)

TESTS:

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

Functions: iterator,$ \,$ list

iterator( self, [distinct=False])

Author: Robert Miller

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( self, [distinct=False])

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(CyclicPermutationsOfPartition([[1,2,3,4],[5,6,7]]))
'Cyclic permutations of partition [[1, 2, 3, 4], [5, 6, 7]]'

Class: PatternAvoider

class PatternAvoider
PatternAvoider( self, n, patterns)

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

Special Functions: __init__,$ \,$ _rec

_rec( self, obj, state)

sage: from sage.combinat.permutation import PatternAvoider
sage: p = PatternAvoider(4, [[1,2]])
sage: list(p._rec([1], 2))
[([2, 1], 3, False)]

Class: Permutation_class

class Permutation_class

Functions: action,$ \,$ avoids,$ \,$ bruhat_greater,$ \,$ bruhat_inversions,$ \,$ bruhat_inversions_iterator,$ \,$ bruhat_lequal,$ \,$ bruhat_pred,$ \,$ bruhat_pred_iterator,$ \,$ bruhat_smaller,$ \,$ bruhat_succ,$ \,$ bruhat_succ_iterator,$ \,$ complement,$ \,$ cycle_string,$ \,$ cycle_type,$ \,$ descent_polynomial,$ \,$ descents,$ \,$ descents_composition,$ \,$ dict,$ \,$ fixed_points,$ \,$ has_pattern,$ \,$ idescents,$ \,$ idescents_signature,$ \,$ imajor_index,$ \,$ inverse,$ \,$ inversions,$ \,$ is_even,$ \,$ ishift,$ \,$ iswitch,$ \,$ left_tableau,$ \,$ length,$ \,$ longest_increasing_subsequence,$ \,$ major_index,$ \,$ next,$ \,$ number_of_descents,$ \,$ number_of_fixed_points,$ \,$ number_of_idescents,$ \,$ number_of_inversions,$ \,$ number_of_peaks,$ \,$ number_of_recoils,$ \,$ number_of_saliances,$ \,$ pattern_positions,$ \,$ peaks,$ \,$ permutohedron_greater,$ \,$ permutohedron_lequal,$ \,$ permutohedron_pred,$ \,$ permutohedron_smaller,$ \,$ permutohedron_succ,$ \,$ prev,$ \,$ rank,$ \,$ recoils,$ \,$ recoils_composition,$ \,$ reduced_word,$ \,$ reduced_word_lexmin,$ \,$ reduced_words,$ \,$ remove_extra_fixed_points,$ \,$ reverse,$ \,$ right_tableau,$ \,$ robinson_schensted,$ \,$ runs,$ \,$ saliances,$ \,$ signature,$ \,$ to_cycles,$ \,$ to_inversion_vector,$ \,$ to_lehmer_cocode,$ \,$ to_lehmer_code,$ \,$ to_major_code,$ \,$ to_matrix,$ \,$ to_permutation_group_element,$ \,$ to_tableau_by_shape,$ \,$ weak_excedences

action( self, a)

Return the action of the permutation on a list.

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( self, patt)

Returns True if the permutation avoid the pattern patt and False otherwise.

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

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

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

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

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

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

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( self, p2)

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

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

bruhat_pred( self)

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.

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

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.

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

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

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

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.

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

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.

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

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

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

cycle_string( self, [singletons=False])

Returns a string of the permutation in cycle notation.

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

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_type( self)

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.

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

descent_polynomial( self)

Returns the descent polynomial of the permutation p.

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

REFERENCES: Garsia and Stanton 1984

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

descents( self, [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.

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

descents_composition( self)

Returns the composition corresponding to the descents of the permutation.

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

dict( self)

Returns a dictionary corresponding to the permutation.

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

fixed_points( self)

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

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

has_pattern( self, patt)

Returns the boolean answering the question 'Is patt a patter appearing in permutation p?'

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

idescents( self, [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.

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

idescents_signature( self, [final_descent=False])

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

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

imajor_index( self, [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.

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

Returns the inverse of a permutation

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

Returns a list of the inversions of permutation p.

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

is_even( self)

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

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

ishift( self, 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.

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( self, 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.

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

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

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

length( self)

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

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

longest_increasing_subsequence( self)

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

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

major_index( self, [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.

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

Returns the permutation that follows p in lexicographic order. If p is the last permutation, then next returns false.

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( self, [final_descent=False])

Returns the number of descents of the permutation p.

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

Returns the number of fixed points of the permutation p.

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( self, [final_descent=False])

Returns the number of descents of the permutation p.

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

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: http://mathworld.wolfram.com/PermutationInversion.html

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

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

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

Returns the number of recoils of the permutation p.

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

number_of_saliances( self)

Returns the number of saliances of the permutation p.

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

pattern_positions( self, patt)

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

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

peaks( self)

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

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

permutohedron_greater( self, [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.

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( self, 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.

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( self, [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.

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( self, [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.

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( self, [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.

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

Returns the permutation that comes directly before p in lexicographic order. If p is the first permutation, then it returns False.

sage: p = Permutation([1,2,3])
sage: p.prev()
False
sage: p = Permutation([1,3,2])
sage: p.prev()
[1, 2, 3]

rank( self)

Returns the rank of a permutation in lexicographic ordering.

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

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.

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

recoils_composition( self)

Returns the composition corresponding to recoils of the permutation.

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

reduced_word( self)

Returns the reduced word of a permutation.

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

reduced_word_lexmin( self)

Returns a lexicographically minimal reduced word of a permutation.

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

reduced_words( self)

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

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

Returns the permutation obtained by removing any fixed points at the end of self.

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

reverse( self)

Returns the permutation obtained by reversing the list.

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

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

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

robinson_schensted( self)

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

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

runs( self)

Returns a list of the runs in the permutation p.

REFERENCES: http://mathworld.wolfram.com/PermutationRun.html

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

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.

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

signature( p)

Returns the signature of a permutation.

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

to_cycles( self, [singletons=True])

Returns the permutation p as a list of disjoint cycles.

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

to_inversion_vector( self)

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.

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]

to_lehmer_cocode( self)

Returns the Lehmer cocode of p.

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

Returns the Lehmer code of the permutation p.

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]

to_major_code( self, [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.

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

Returns a matrix representing the permutation.

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

Returns a PermutationGroupElement equal to self.

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( self, shape)

Returns a tableau of shape shape with the entries in self.

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

Returns all the numbers self[i] such that self[i] >= i+1.

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

Special Functions: __mul__,$ \,$ __repr__,$ \,$ __rmul__,$ \,$ __str__,$ \,$ _icondition,$ \,$ _left_to_right_multiply_on_left,$ \,$ _left_to_right_multiply_on_right

__mul__( self, rp)

TESTS:

sage: p213 = Permutation([2,1,3])
sage: p312 = Permutation([3,1,2])
sage: PermutationOptions(mult='l2r')
sage: p213*p312
[1, 3, 2]
sage: PermutationOptions(mult='r2l')
sage: p213*p312
[3, 2, 1]
sage: PermutationOptions(mult='l2r')

__repr__( self)

TESTS:

sage: PermutationOptions(display='list')
sage: p = Permutation([2,1,3])
sage: repr(p)
'[2, 1, 3]'
sage: PermutationOptions(display='cycle')
sage: repr(p)
'(1,2)'
sage: PermutationOptions(display='singleton')
sage: repr(p)
'(1,2)(3)'
sage: PermutationOptions(display='list')

__rmul__( self, lp)

TESTS:

sage: p213 = Permutation([2,1,3])
sage: p312 = Permutation([3,1,2])
sage: PermutationOptions(mult='l2r')
sage: p213*p312
[1, 3, 2]
sage: PermutationOptions(mult='r2l')
sage: p213*p312
[3, 2, 1]
sage: PermutationOptions(mult='l2r')

__str__( self)

TESTS:

sage: PermutationOptions(display='list')
sage: p = Permutation([2,1,3])
sage: str(p)
'[2, 1, 3]'
sage: PermutationOptions(display='cycle')
sage: str(p)
'(1,2)'
sage: PermutationOptions(display='singleton')
sage: str(p)
'(1,2)(3)'
sage: PermutationOptions(display='list')

_icondition( self, i)

Returns a string which shows the relative positions of i-1,i,i+1 in self. Note that i corresponds to a 2 in the string.

NOTE: An imove can only be applied when the relative positions are one of '213', '132', '231', or '312'. None is returned in the other cases to signal that an imove cannot be applied.

sage: Permutation([2,1,3])._icondition(2)
('213', 1, 0, 2)
sage: Permutation([1,3,2])._icondition(2)
('132', 0, 2, 1)
sage: Permutation([2,3,1])._icondition(2)
('231', 2, 0, 1)
sage: Permutation([3,1,2])._icondition(2)
('312', 1, 2, 0)
sage: Permutation([1,2,3])._icondition(2)
(None, 0, 1, 2)
sage: Permutation([1,3,2,4])._icondition(3)
('213', 2, 1, 3)
sage: Permutation([2,1,3])._icondition(3)
Traceback (most recent call last):
...
ValueError: i (= 3) must be between 2 and n-1

_left_to_right_multiply_on_left( self, lp)

sage: p = Permutation([2,1,3])
sage: q = Permutation([3,1,2])
sage: p._left_to_right_multiply_on_left(q)
[3, 2, 1]
sage: q._left_to_right_multiply_on_left(p)
[1, 3, 2]

_left_to_right_multiply_on_right( self, rp)

sage: p = Permutation([2,1,3])
sage: q = Permutation([3,1,2])
sage: p._left_to_right_multiply_on_right(q)
[1, 3, 2]
sage: q._left_to_right_multiply_on_right(p)
[3, 2, 1]

Class: Permutations_mset

class Permutations_mset
Permutations_mset( self, mset)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations([1,2,2]).count()
3

iterator( self)

Algorithm based on: http://marknelson.us/2002/03/01/next-permutation/

sage: [ p for p in Permutations(['c','t','t'])] # indirect doctest
[['c', 't', 't'], ['t', 'c', 't'], ['t', 't', 'c']]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(['c','a','c']))
"Permutations of the multi-set ['c', 'a', 'c']"

Class: Permutations_msetk

class Permutations_msetk
Permutations_msetk( self, mset, k)

TESTS:

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

Functions: list

list( self)

sage: Permutations([1,2,2],2).list()
[[1, 2], [2, 1], [2, 2]]

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: p = Permutations([1,2,2],2)
sage: [1,2,2] in p
False
sage: [2,2] in p
True
sage: [1,1] in p
False
sage: [2,1] in p
True

__repr__( self)

TESTS:

sage: repr(Permutations([1,2,2],2))
'Permutations of the multi-set [1, 2, 2] of length 2'

Class: Permutations_nk

class Permutations_nk
Permutations_nk( self, n, k)

TESTS:

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

Functions: count,$ \,$ iterator,$ \,$ random_element

count( self)

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

iterator( self)

sage: [p for p in Permutations(3,2)] # indirect doctest
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
sage: [p for p in Permutations(3,0)]
[[]]
sage: [p for p in Permutations(3,4)]
[]

random_element( self)

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

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: [1,2] in Permutations(3,2)
True
sage: [1,1] in Permutations(3,2)
False
sage: [3,2,1] in Permutations(3,2)
False
sage: [3,1] in Permutations(3,2)
True

__repr__( self)

TESTS:

sage: repr(Permutations(3,2))
'Permutations of {1,...,3} of length 2'

Class: Permutations_set

class Permutations_set
Permutations_set( self, s)

TESTS:

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

Functions: count,$ \,$ iterator,$ \,$ random_element

count( self)

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

iterator( self)

Algorithm based on: http://marknelson.us/2002/03/01/next-permutation/

sage: [ p for p in Permutations(['c','a','t'])] # indirect doctest
[['c', 'a', 't'],
 ['c', 't', 'a'],
 ['a', 'c', 't'],
 ['a', 't', 'c'],
 ['t', 'c', 'a'],
 ['t', 'a', 'c']]

random_element( self)

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(['c','a','t']))
"Permutations of the set ['c', 'a', 't']"

Class: Permutations_setk

class Permutations_setk
Permutations_setk( self, s, k)

TESTS:

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

Functions: iterator,$ \,$ random_element

iterator( self)

sage: [i for i in Permutations([1,2,3],2)] # indirect doctest
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

random_element( self)

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

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

sage: p = Permutations([1,2,3],2)
sage: [1,2,3] in p
False
sage: [2,2] in p
False
sage: [1,3] in p
True
sage: [2,1] in p
True

__repr__( self)

TESTS:

sage: repr(Permutations([1,2,3],2))
'Permutations of the set [1, 2, 3] of length 2'

Class: StandardPermutations_all

class StandardPermutations_all
StandardPermutations_all( self)

TESTS:

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

Functions: list

list( self)

sage: Permutations().list()
Traceback (most recent call last):
...
NotImplementedError

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: [] in Permutations()
False
sage: [1] in Permutations()
True
sage: [2] in Permutations()
False
sage: [1,2] in Permutations()
True
sage: [2,1] in Permutations()
True
sage: [1,2,2] in Permutations()
False
sage: [3,1,5,2] in Permutations()
False
sage: [3,4,1,5,2] in Permutations()
True

__repr__( self)

TESTS:

sage: repr(Permutations())
'Standard permutations'

Class: StandardPermutations_avoiding_12

class StandardPermutations_avoiding_12
StandardPermutations_avoiding_12( self, n)

TESTS:

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

Functions: list

list( self)

sage: Permutations(3, avoiding=[1,2]).list()
[[3, 2, 1]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[1,2]))
'Standard permutations of 3 avoiding [1, 2]'

Class: StandardPermutations_avoiding_123

class StandardPermutations_avoiding_123
StandardPermutations_avoiding_123( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[1, 2, 3]).count()
42
sage: len( Permutations(5, avoiding=[1, 2, 3]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[1, 2, 3]).list() # indirect doctest
 [[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: Permutations(2, avoiding=[1, 2, 3]).list()
[[1, 2], [2, 1]]
sage: Permutations(3, avoiding=[1, 2, 3]).list()
[[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[1, 2, 3]))
'Standard permutations of 3 avoiding [1, 2, 3]'

Class: StandardPermutations_avoiding_132

class StandardPermutations_avoiding_132
StandardPermutations_avoiding_132( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[1, 3, 2]).count()
42
sage: len( Permutations(5, avoiding=[1, 3, 2]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[1,3,2]).list() # indirect doctest
[[1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
sage: Permutations(4, avoiding=[1,3,2]).list()
[[4, 1, 3, 2],
 [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, 3, 2, 4],
 [2, 1, 3, 4],
 [2, 3, 1, 4],
 [3, 1, 2, 4],
 [3, 2, 1, 4]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[1,3,2]))
'Standard permutations of 3 avoiding [1, 3, 2]'

Class: StandardPermutations_avoiding_21

class StandardPermutations_avoiding_21
StandardPermutations_avoiding_21( self, n)

TESTS:

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

Functions: list

list( self)

sage: Permutations(3, avoiding=[2,1]).list()
[[1, 2, 3]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[2,1]))
'Standard permutations of 3 avoiding [2, 1]'

Class: StandardPermutations_avoiding_213

class StandardPermutations_avoiding_213
StandardPermutations_avoiding_213( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[2, 1, 3]).count()
42
sage: len( Permutations(5, avoiding=[2, 1, 3]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[2, 1, 3]).list()
[[2, 1, 3], [1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[2, 1, 3]))
'Standard permutations of 3 avoiding [2, 1, 3]'

Class: StandardPermutations_avoiding_231

class StandardPermutations_avoiding_231
StandardPermutations_avoiding_231( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[2, 3, 1]).count()
42
sage: len( Permutations(5, avoiding=[2, 3, 1]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[2, 3, 1]).list()
[[2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[2, 3, 1]))
'Standard permutations of 3 avoiding [2, 3, 1]'

Class: StandardPermutations_avoiding_312

class StandardPermutations_avoiding_312
StandardPermutations_avoiding_312( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[3, 1, 2]).count()
42
sage: len( Permutations(5, avoiding=[3, 1, 2]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[3, 1, 2]).list()
[[3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[3, 1, 2]))
'Standard permutations of 3 avoiding [3, 1, 2]'

Class: StandardPermutations_avoiding_321

class StandardPermutations_avoiding_321
StandardPermutations_avoiding_321( self, n)

TESTS:

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

Functions: count,$ \,$ iterator

count( self)

sage: Permutations(5, avoiding=[3, 2, 1]).count()
42
sage: len( Permutations(5, avoiding=[3, 2, 1]).list() )
42

iterator( self)

sage: Permutations(3, avoiding=[3, 2, 1]).list() #indirect doctest
[[2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(3, avoiding=[3, 2, 1]))
'Standard permutations of 3 avoiding [3, 2, 1]'

Class: StandardPermutations_avoiding_generic

class StandardPermutations_avoiding_generic
StandardPermutations_avoiding_generic( self, n, a)

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

Functions: iterator

iterator( self)

sage: Permutations(3, avoiding=[[2, 1, 3],[1,2,3]]).list()
[[1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

sage: P = Permutations(3, avoiding=[[2, 1, 3],[1,2,3]])
sage: P.__repr__()
'Standard permutations of 3 avoiding [[2, 1, 3], [1, 2, 3]]'

Class: StandardPermutations_bruhat_greater

class StandardPermutations_bruhat_greater
StandardPermutations_bruhat_greater( self, p)

TESTS:

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

Functions: list

list( self)

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

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(bruhat_greater=[3,2,1]))
'Standard permutations that are greater than or equal to [3, 2, 1] in the
Bruhat order'

Class: StandardPermutations_bruhat_smaller

class StandardPermutations_bruhat_smaller
StandardPermutations_bruhat_smaller( self, p)

TESTS:

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

Functions: list

list( self)

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

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(bruhat_smaller=[3,2,1]))
'Standard permutations that are less than or equal to [3, 2, 1] in the
Bruhat order'

Class: StandardPermutations_descents

class StandardPermutations_descents
StandardPermutations_descents( self, d, n)

TESTS:

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

Functions: first,$ \,$ last,$ \,$ list

first( self)

Returns the first permutation with descents d.

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

last( self)

Returns the last permutation with descents d.

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

list( self)

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

sage: Permutations(descents=([2,4,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]]

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(descents=([1,0,4,8],12)))
'Standard permutations of 12 with descents [1, 0, 4, 8]'

Class: StandardPermutations_n

class StandardPermutations_n
StandardPermutations_n( self, n)

TESTS:

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

Functions: count,$ \,$ identity,$ \,$ iterator,$ \,$ random_element,$ \,$ rank,$ \,$ unrank

count( self)

sage: Permutations(3).count()
6
sage: Permutations(4).count()
24

identity( self)

Returns the identity permutation of length n.

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

iterator( self)

sage: [p for p in Permutations(3)] # indirect doctest
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

random_element( self)

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

rank( self, p)

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

unrank( self, r)

sage: SP3 = Permutations(3)
sage: l = map(SP3.unrank, range(6))
sage: l == SP3.list()
True

Special Functions: __contains__,$ \,$ __init__,$ \,$ __repr__

__contains__( self, x)

TESTS:

sage: [1,2] in Permutations(2)
True
sage: [1,2] in Permutations(3)
False
sage: [3,2,1] in Permutations(3)
True

__repr__( self)

TESTS:

sage: repr(Permutations(3))
'Standard permutations of 3'

Class: StandardPermutations_recoils

class StandardPermutations_recoils
StandardPermutations_recoils( self, recoils)

TESTS:

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

Functions: list

list( self)

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

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(recoils=[2,2]))
'Standard permutations whose recoils composition is [2, 2]'

Class: StandardPermutations_recoilsfatter

class StandardPermutations_recoilsfatter
StandardPermutations_recoilsfatter( self, recoils)

TESTS:

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

Functions: list

list( self)

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

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(recoils_fatter=[2,2]))
'Standard permutations whose recoils composition is fatter than [2, 2]'

Class: StandardPermutations_recoilsfiner

class StandardPermutations_recoilsfiner
StandardPermutations_recoilsfiner( self, recoils)

TESTS:

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

Functions: list

list( self)

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

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

Special Functions: __init__,$ \,$ __repr__

__repr__( self)

TESTS:

sage: repr(Permutations(recoils_finer=[2,2]))
'Standard permutations whose recoils composition is finer than [2, 2]'

See About this document... for information on suggesting changes.