Labelled permutations

A labelled (generalized) permutation is better suited to study the dynamic of a translation surface than a reduced one (see the module sage.combinat.iet.reduced). The latter is more adapted to the study of strata. This kind of permutation was introduced by Yoccoz [Yoc05] (see also [MMY03]).

In fact, there is a geometric counterpart of labelled permutations. They correspond to translation surface with marked outgoing separatrices (i.e. we fi a label for each of them).

Remarks that Rauzy diagram of reduced objects are significantly smaller than the one for labelled object (for the permutation a b d b e / e d c a c the labelled Rauzy diagram contains 8760 permutations, and the reduced only 73). But, as it is in geometrical way, the labelled Rauzy diagram is a covering of the reduced Rauzy diagram.

AUTHORS:

• Vincent Delecroix (2009-09-29) : initial version

TESTS:

sage: from sage.combinat.iet.labelled import LabelledPermutationIET
sage: LabelledPermutationIET([['a', 'b', 'c'], ['c', 'b', 'a']])
a b c
c b a
sage: LabelledPermutationIET([[1,2,3,4],[4,1,2,3]]) 
1 2 3 4
4 1 2 3
sage: from sage.combinat.iet.labelled import LabelledPermutationLI
sage: LabelledPermutationLI([[1,1],[2,2,3,3,4,4]])
1 1
2 2 3 3 4 4
sage: LabelledPermutationLI([['a','a','b','b','c','c'],['d','d']])
a a b b c c
d d
sage: from sage.combinat.iet.labelled import FlippedLabelledPermutationIET
sage: FlippedLabelledPermutationIET([[1,2,3],[3,2,1]],flips=[1,2])
-1 -2  3
 3 -2 -1
sage: FlippedLabelledPermutationIET([['a','b','c'],['b','c','a']],flips='b')
 a -b  c
-b  c  a
sage: from sage.combinat.iet.labelled import FlippedLabelledPermutationLI
sage: FlippedLabelledPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4])
-1 -1
 2  2  3  3 -4 -4
sage: FlippedLabelledPermutationLI([['a','a','b','b'],['c','c']],flips='ac')
-a -a  b  b
-c -c
sage: from sage.combinat.iet.labelled import LabelledRauzyDiagram
sage: p = LabelledPermutationIET([[1,2,3],[3,2,1]])
sage: d1 = LabelledRauzyDiagram(p)
sage: p = LabelledPermutationIET([['a','b'],['b','a']])
sage: d = p.rauzy_diagram()
sage: g1 = d.path(p, 'top', 'bottom')
sage: g1.matrix()
[1 1]
[1 2]
sage: g2 = d.path(p, 'bottom', 'top')
sage: g2.matrix()
[2 1]
[1 1]
sage: p = LabelledPermutationIET([['a','b','c','d'],['d','c','b','a']])
sage: d = p.rauzy_diagram()
sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b')
sage: g
Path of length 8 in a Rauzy diagram
sage: g.is_loop()
True
sage: g.is_full()
True
sage: s1 = g.orbit_substitution()
sage: print s1
WordMorphism: a->adbd, b->adbdbd, c->adccd, d->adcd
sage: s2 = g.interval_substitution()
sage: print s2
WordMorphism: a->abcd, b->bab, c->cdc, d->dcbababcd
sage: s1.incidence_matrix() == s2.incidence_matrix().transpose()
True

REFERENCES:

[Yoc05]

Jean-Cristophe Yoccoz “Echange d’Intervalles”, Cours au college de France

[MMY03]

Jean-Cristophe Yoccoz, Stefano Marmi and Pierre Moussa “On the cohomological equation for interval exchange maps”, arXiv:math/0304469v1

class sage.combinat.iet.labelled.FlippedLabelledPermutation(intervals=None, alphabet=None, flips=None)

Bases: sage.combinat.iet.labelled.LabelledPermutation

General template for labelled objects

Warning

Internal class! Do not use directly!

list(flips=False)

Returns a list associated to the permutation.

INPUT:

• flips - boolean (default: False)

OUTPUT:

list – two lists of labels

EXAMPLES:

sage: p = iet.GeneralizedPermutation('0 0 1 2 2 1', '3 3', flips='1')
sage: p.list(flips=True)
[[('0', 1), ('0', 1), ('1', -1), ('2', 1), ('2', 1), ('1', -1)], [('3', 1), ('3', 1)]]
sage: p.list(flips=False)
[['0', '0', '1', '2', '2', '1'], ['3', '3']]

The list can be used to reconstruct the permutation

sage: p = iet.Permutation('a b c','c b a',flips='ab')
sage: p == iet.Permutation(p.list(), flips=p.flips())
True

sage: p = iet.GeneralizedPermutation('a b b c','c d d a',flips='ad')
sage: p == iet.GeneralizedPermutation(p.list(),flips=p.flips())
True

class sage.combinat.iet.labelled.FlippedLabelledPermutationIET(intervals=None, alphabet=None, flips=None)

Bases: sage.combinat.iet.labelled.FlippedLabelledPermutation, sage.combinat.iet.template.FlippedPermutationIET, sage.combinat.iet.labelled.LabelledPermutationIET

Flipped labelled permutation from iet.

EXAMPLES:

Reducibility testing (does not depends of flips):

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: p.is_irreducible()
True
sage: q = iet.Permutation('a b c d', 'b a d c', flips='bc')
sage: q.is_irreducible()
False

Rauzy movability and Rauzy move:

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: print p
-a  b  c
 c  b -a
sage: print p.rauzy_move(1)
-c -a  b
-c  b -a
sage: print p.rauzy_move(0)
-a  b  c
 c -a  b

Rauzy diagrams:

sage: d = iet.RauzyDiagram('a b c d','d a b c',flips='a')

AUTHORS:

• Vincent Delecroix (2009-09-29): initial version

rauzy_diagram(**kargs)

Returns the Rauzy diagram associated to this permutation.

For more information, try help(iet.RauzyDiagram)

OUTPUT:

RauzyDiagram – the Rauzy diagram of self

EXAMPLES:

sage: p = iet.Permutation('a b c', 'c b a',flips='a')
sage: p.rauzy_diagram()
Rauzy diagram with 3 permutations

rauzy_move(winner=None, side=None)

Returns the Rauzy move.

INPUT:

• winner - ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)
• side - (default: ‘right’) ‘right’ (or ‘r’) or ‘left’ (or ‘l’)

OUTPUT:

permutation – the Rauzy move of self

EXAMPLES:

sage: p = iet.Permutation('a b','b a',flips='a')
sage: p.rauzy_move('top')
-a  b
 b -a
sage: p.rauzy_move('bottom')
-b -a
-b -a

sage: p = iet.Permutation('a b c','c b a',flips='b')
sage: p.rauzy_move('top')
 a -b  c
 c  a -b
sage: p.rauzy_move('bottom')
 a  c -b
 c -b  a

reduced()

The associated reduced permutation.

OUTPUT:

permutation – the associated reduced permutation

EXAMPLE:

sage: p = iet.Permutation('a b c','c b a',flips='a')
sage: q = iet.Permutation('a b c','c b a',flips='a',reduced=True)
sage: p.reduced() == q
True

class sage.combinat.iet.labelled.FlippedLabelledPermutationLI(intervals=None, alphabet=None, flips=None)

Bases: sage.combinat.iet.labelled.FlippedLabelledPermutation, sage.combinat.iet.template.FlippedPermutationLI, sage.combinat.iet.labelled.LabelledPermutationLI

Flipped labelled quadratic (or generalized) permutation.

EXAMPLES:

Reducibility testing:

sage: p = iet.GeneralizedPermutation('a b b', 'c c a', flips='a')
sage: p.is_irreducible()
True

Reducibility testing with associated decomposition:

sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c', flips='ab')
sage: p.is_irreducible()
False
sage: test, decomp = p.is_irreducible(return_decomposition = True)
sage: print test
False
sage: print decomp
(['a'], ['c', 'a'], [], ['c'])

Rauzy movability and Rauzy move:

sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d', flips='d')
sage: p.has_rauzy_move(0)
False
sage: p.has_rauzy_move(1)
True
sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
sage: p.has_rauzy_move(0)
True
sage: p.has_rauzy_move(1)
True

left_rauzy_move(winner)

Perform a Rauzy move on the left.

INPUT:

• winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)

OUTPUT:

– a permutation

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.left_rauzy_move(0)
a a b b
c c
sage: p.left_rauzy_move(1)
a a b
b c c

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.left_rauzy_move(0)
a b b
c c a
sage: p.left_rauzy_move(1)
b b
c c a a

rauzy_diagram(**kargs)

Returns the associated Rauzy diagram.

For more information, try help(RauzyDiagram)

OUTPUT :

– a RauzyDiagram

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a b b a', 'c d c d')
sage: d = p.rauzy_diagram()

reduced()

The associated reduced permutation.

OUTPUT:

permutation – the associated reduced permutation

EXAMPLE:

sage: p = iet.GeneralizedPermutation('a a','b b c c',flips='a')
sage: q = iet.GeneralizedPermutation('a a','b b c c',flips='a',reduced=True)
sage: p.reduced() == q
True

right_rauzy_move(winner)

Perform a Rauzy move on the right (the standard one).

INPUT:

• winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)

OUTPUT:

permutation – the Rauzy move of self

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
sage: p.right_rauzy_move(0)
 a  a  b
-c  b -c
sage: p.right_rauzy_move(1)
 a  a
-b -c -b -c

sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='ab')
sage: p.right_rauzy_move(0)
 a -b  a -b
 c  c
sage: p.right_rauzy_move(1)
 b -a  b
 c  c -a

class sage.combinat.iet.labelled.FlippedLabelledRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)

Bases: sage.combinat.iet.template.FlippedRauzyDiagram, sage.combinat.iet.labelled.LabelledRauzyDiagram

Rauzy diagram of flipped labelled permutations

class sage.combinat.iet.labelled.LabelledPermutation(intervals=None, alphabet=None)

Bases: sage.structure.sage_object.SageObject

General template for labelled objects.

Warning

Internal class! Do not use directly!

erase_letter(letter)

Return the permutation with the specified letter removed.

OUTPUT:

permutation – the resulting permutation

EXAMPLES:

sage: p = iet.Permutation('a b c d','c d b a')
sage: p.erase_letter('a')
b c d
c d b
sage: p.erase_letter('b')
a c d
c d a
sage: p.erase_letter('c')
a b d
d b a
sage: p.erase_letter('d')
a b c
c b a

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.erase_letter('a')
b b
c c

Beware, there is no validity check for permutation from linear involutions:

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.erase_letter('b')
a
c c a

length(interval=None)

Returns a 2-uple of lengths.

p.length() is identical to (p.length_top(), p.length_bottom()) If an interval is specified, it returns the length of the specified interval.

INPUT:

• interval - None, ‘top’ or ‘bottom’

OUTPUT:

tuple – a 2-uple of integers

EXAMPLES:

sage: iet.Permutation('a b c','c b a').length()
(3, 3)
sage: iet.GeneralizedPermutation('a a','b b c c').length()
(2, 4)
sage: iet.GeneralizedPermutation('a a b b','c c').length()
(4, 2)

length_bottom()

Returns the number of intervals in the bottom segment.

OUTPUT:

integer – number of intervals

EXAMPLES:

sage: iet.Permutation('a b','b a').length_bottom()
2
sage: iet.GeneralizedPermutation('a a','b b c c').length_bottom()
4
sage: iet.GeneralizedPermutation('a a b b','c c').length_bottom()
2

length_top()

Returns the number of intervals in the top segment.

OUTPUT:

integer – number of intervals

EXAMPLES:

sage: iet.Permutation('a b c','c b a').length_top()
3
sage: iet.GeneralizedPermutation('a a','b b c c').length_top()
2
sage: iet.GeneralizedPermutation('a a b b','c c').length_top()
4

list()

Returns a list of two lists corresponding to the intervals.

OUTPUT:

list – two lists of labels

EXAMPLES:

The list of an permutation from iet:

sage: p1 = iet.Permutation('1 2 3', '3 1 2')
sage: p1.list()
[['1', '2', '3'], ['3', '1', '2']]
sage: p1.alphabet("abc")
sage: p1.list()
[['a', 'b', 'c'], ['c', 'a', 'b']]

Recovering the permutation from this list (and the alphabet):

sage: q1 = iet.Permutation(p1.list(),alphabet=p1.alphabet())
sage: p1 == q1
True

The list of a quadratic permutation:

sage: p2 = iet.GeneralizedPermutation('g o o', 'd d g')
sage: p2.list()
[['g', 'o', 'o'], ['d', 'd', 'g']]

Recovering the permutation:

sage: q2 = iet.GeneralizedPermutation(p2.list(),alphabet=p2.alphabet())
sage: p2 == q2
True

rauzy_move_loser(winner=None, side=None)

Returns the loser of a Rauzy move

INPUT:

• winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)
• side - either ‘left’ or ‘right’ (‘l’ or ‘r’ for short)

OUTPUT:

– a label

EXAMPLES:

sage: p = iet.Permutation('a b c d','b d a c')
sage: p.rauzy_move_loser('top','right')
'c'
sage: p.rauzy_move_loser('bottom','right')
'd'
sage: p.rauzy_move_loser('top','left')
'b'
sage: p.rauzy_move_loser('bottom','left')
'a'

rauzy_move_matrix(winner=None, side='right')

Returns the Rauzy move matrix.

This matrix corresponds to the action of a Rauzy move on the vector of lengths. By convention (to get a positive matrix), the matrix is define as the inverse transformation on the length vector.

OUTPUT:

matrix – a square matrix of positive integers

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: p.rauzy_move_matrix('t')
[1 0]
[1 1]
sage: p.rauzy_move_matrix('b')
[1 1]
[0 1]

sage: p = iet.Permutation('a b c d','b d a c')
sage: q = p.left_right_inverse()
sage: m0 = p.rauzy_move_matrix(winner='top',side='right') 
sage: n0 = q.rauzy_move_matrix(winner='top',side='left')
sage: m0 == n0
True
sage: m1 = p.rauzy_move_matrix(winner='bottom',side='right')
sage: n1 = q.rauzy_move_matrix(winner='bottom',side='left')
sage: m1 == n1
True

rauzy_move_winner(winner=None, side=None)

Returns the winner of a Rauzy move.

INPUT:

• winner - either ‘top’ or ‘bottom’ (‘t’ or ‘b’ for short)
• side - either ‘left’ or ‘right’ (‘l’ or ‘r’ for short)

OUTPUT:

– a label

EXAMPLES:

sage: p = iet.Permutation('a b c d','b d a c')
sage: p.rauzy_move_winner('top','right')
'd'
sage: p.rauzy_move_winner('bottom','right')
'c'
sage: p.rauzy_move_winner('top','left')
'a'
sage: p.rauzy_move_winner('bottom','left')
'b'

sage: p = iet.GeneralizedPermutation('a b b c','d c a e d e')
sage: p.rauzy_move_winner('top','right')
'c'
sage: p.rauzy_move_winner('bottom','right')
'e'
sage: p.rauzy_move_winner('top','left')
'a'
sage: p.rauzy_move_winner('bottom','left')
'd'

class sage.combinat.iet.labelled.LabelledPermutationIET(intervals=None, alphabet=None)

Bases: sage.combinat.iet.labelled.LabelledPermutation, sage.combinat.iet.template.PermutationIET

Labelled permutation for iet

EXAMPLES:

Reducibility testing:

sage: p = iet.Permutation('a b c', 'c b a')
sage: p.is_irreducible()
True

sage: q = iet.Permutation('a b c d', 'b a d c')
sage: q.is_irreducible()
False

Rauzy movability and Rauzy move:

sage: p = iet.Permutation('a b c', 'c b a')
sage: p.has_rauzy_move('top')
True
sage: print p.rauzy_move('bottom')
a c b 
c b a
sage: p.has_rauzy_move('top')
True
sage: print p.rauzy_move('top')
a b c
c a b

Rauzy diagram:

sage: p = iet.Permutation('a b c', 'c b a')
sage: d = p.rauzy_diagram()
sage: p in d
True

has_rauzy_move(winner=None, side=None)

Returns True if you can perform a Rauzy move.

INPUT:

• winner - the winner interval (‘top’ or ‘bottom’)
• side - (default: ‘right’) the side (‘left’ or ‘right’)

OUTPUT:

bool – True if self has a Rauzy move

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: p.has_rauzy_move()
True

sage: p = iet.Permutation('a b c','b a c')
sage: p.has_rauzy_move()
False

is_identity()

Returns True if self is the identity.

OUTPUT:

bool – True if self corresponds to the identity

EXAMPLES:

sage: iet.Permutation("a b","a b").is_identity()
True
sage: iet.Permutation("a b","b a").is_identity()
False

rauzy_diagram(**args)

Returns the associated Rauzy diagram.

For more information try help(iet.RauzyDiagram).

OUTPUT:

Rauzy diagram – the Rauzy diagram of the permutation

EXAMPLES:

sage: p = iet.Permutation('a b c', 'c b a')
sage: d = p.rauzy_diagram()

rauzy_move(winner=None, side=None, iteration=1)

Returns the Rauzy move.

INPUT:

• winner - the winner interval (‘top’ or ‘bottom’)
• side - (default: ‘right’) the side (‘left’ or ‘right’)

OUTPUT:

permutation – the Rauzy move of the permutation

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: p.rauzy_move('t','right')
a b
b a
sage: p.rauzy_move('b','right')
a b
b a

sage: p = iet.Permutation('a b c','c b a')
sage: p.rauzy_move('t','right')
a b c
c a b
sage: p.rauzy_move('b','right')
a c b
c b a

sage: p = iet.Permutation('a b','b a')
sage: p.rauzy_move('t','left')
a b
b a
sage: p.rauzy_move('b','left')
a b
b a

sage: p = iet.Permutation('a b c','c b a')
sage: p.rauzy_move('t','left')
a b c
b c a
sage: p.rauzy_move('b','left')
b a c
c b a

rauzy_move_interval_substitution(winner=None, side=None)

Returns the interval substitution associated.

INPUT:

• winner - the winner interval (‘top’ or ‘bottom’)
• side - (default: ‘right’) the side (‘left’ or ‘right’)

OUTPUT:

WordMorphism – a substitution on the alphabet of the permutation

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: print p.rauzy_move_interval_substitution('top','right')
WordMorphism: a->a, b->ba
sage: print p.rauzy_move_interval_substitution('bottom','right')
WordMorphism: a->ab, b->b
sage: print p.rauzy_move_interval_substitution('top','left')
WordMorphism: a->ba, b->b
sage: print p.rauzy_move_interval_substitution('bottom','left')
WordMorphism: a->a, b->ab

rauzy_move_orbit_substitution(winner=None, side=None)

Return the action fo the rauzy_move on the orbit.

INPUT:

• i - integer
• winner - the winner interval (‘top’ or ‘bottom’)
• side - (default: ‘right’) the side (‘right’ or ‘left’)

OUTPUT:

WordMorphism – a substitution on the alphabet of self

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: print p.rauzy_move_orbit_substitution('top','right')
WordMorphism: a->ab, b->b
sage: print p.rauzy_move_orbit_substitution('bottom','right')
WordMorphism: a->a, b->ab
sage: print p.rauzy_move_orbit_substitution('top','left')
WordMorphism: a->a, b->ba
sage: print p.rauzy_move_orbit_substitution('bottom','left')
WordMorphism: a->ba, b->b

reduced()

Returns the associated reduced abelian permutation.

OUTPUT:

a reduced permutation – the underlying reduced permutation

EXAMPLES:

sage: p = iet.Permutation(“a b c d”,”d c a b”) sage: q = iet.Permutation(“a b c d”,”d c a b”,reduced=True) sage: p.reduced() == q True

class sage.combinat.iet.labelled.LabelledPermutationLI(intervals=None, alphabet=None)

Bases: sage.combinat.iet.labelled.LabelledPermutation, sage.combinat.iet.template.PermutationLI

Labelled quadratic (or generalized) permutation

EXAMPLES:

Reducibility testing:

sage: p = iet.GeneralizedPermutation('a b b', 'c c a')
sage: p.is_irreducible()
True

Reducibility testing with associated decomposition:

sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c')
sage: p.is_irreducible()
False
sage: test, decomposition = p.is_irreducible(return_decomposition = True)
sage: print test
False
sage: print decomposition
(['a'], ['c', 'a'], [], ['c'])

Rauzy movability and Rauzy move:

sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d')
sage: p.has_rauzy_move(0)
False
sage: p.has_rauzy_move(1)
True
sage: q = p.rauzy_move(1)
sage: print q
a a b b c
c d d
sage: q.has_rauzy_move(0)
True
sage: q.has_rauzy_move(1)
True

Rauzy diagrams:

sage: p = iet.GeneralizedPermutation('0 0 1 1','2 2')
sage: r = p.rauzy_diagram()
sage: p in r
True

has_right_rauzy_move(winner)

Test of Rauzy movability with a specified winner)

A quadratic (or generalized) permutation is rauzy_movable type depending on the possible length of the last interval. It’s dependent of the length equation.

INPUT:

• winner - ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

bool – True if self has a Rauzy move

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a','b b')
sage: p.has_right_rauzy_move('top')
False
sage: p.has_right_rauzy_move('bottom')
False

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.has_right_rauzy_move('top')
True
sage: p.has_right_rauzy_move('bottom')
True

sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: p.has_right_rauzy_move('top')
True
sage: p.has_right_rauzy_move('bottom')
False

sage: p = iet.GeneralizedPermutation('a a b b','c c')
sage: p.has_right_rauzy_move('top')
False
sage: p.has_right_rauzy_move('bottom')
True

left_rauzy_move(winner)

Perform a Rauzy move on the left.

INPUT:

• winner - ‘top’ or ‘bottom’

OUTPUT:

permutation – the Rauzy move of self

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.left_rauzy_move(0)
a a b b
c c
sage: p.left_rauzy_move(1)
a a b
b c c

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.left_rauzy_move(0)
a b b
c c a
sage: p.left_rauzy_move(1)
b b
c c a a

TESTS:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: q = p.top_bottom_inverse()
sage: q = q.left_rauzy_move(0)
sage: q = q.top_bottom_inverse()
sage: q == p.left_rauzy_move(1)
True
sage: q = p.top_bottom_inverse()
sage: q = q.left_rauzy_move(1)
sage: q = q.top_bottom_inverse()
sage: q == p.left_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.right_rauzy_move(0)
sage: q = q.left_right_inverse()
sage: q == p.left_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.right_rauzy_move(1)
sage: q = q.left_right_inverse()
sage: q == p.left_rauzy_move(1)
True

rauzy_diagram(**kargs)

Returns the associated RauzyDiagram.

OUTPUT:

Rauzy diagram – the Rauzy diagram of the permutation

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a b c b', 'c d d a')
sage: d = p.rauzy_diagram()
sage: p in d
True

For more information, try help(iet.RauzyDiagram)

reduced()

Returns the associated reduced quadratic permutations.

OUTPUT:

permutation – the underlying reduced permutation

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a','b b c c')
sage: q = p.reduced()
sage: q
a a 
b b c c
sage: p.rauzy_move(0).reduced() == q.rauzy_move(0)
True

right_rauzy_move(winner)

Perform a Rauzy move on the right (the standard one).

INPUT:

• winner - ‘top’ (or ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

boolean – True if self has a Rauzy move

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: p.right_rauzy_move(0)
a a b
b c c
sage: p.right_rauzy_move(1)
a a
b b c c

sage: p = iet.GeneralizedPermutation('a b b','c c a')
sage: p.right_rauzy_move(0)
a a b b
c c
sage: p.right_rauzy_move(1)
a b b
c c a

TESTS:

sage: p = iet.GeneralizedPermutation('a a b','b c c')
sage: q = p.top_bottom_inverse()
sage: q = q.right_rauzy_move(0)
sage: q = q.top_bottom_inverse()
sage: q == p.right_rauzy_move(1)
True
sage: q = p.top_bottom_inverse()
sage: q = q.right_rauzy_move(1)
sage: q = q.top_bottom_inverse()
sage: q == p.right_rauzy_move(0)
True
sage: p = p.left_right_inverse()
sage: q = q.left_rauzy_move(0)
sage: q = q.left_right_inverse()
sage: q == p.right_rauzy_move(0)
True
sage: q = p.left_right_inverse()
sage: q = q.left_rauzy_move(1)
sage: q = q.left_right_inverse()
sage: q == p.right_rauzy_move(1)
True

sage.combinat.iet.labelled.LabelledPermutationsIET_iterator(nintervals=None, irreducible=True, alphabet=None)

Returns an iterator over labelled permutations.

INPUT:

• nintervals - integer or None
• irreducible - boolean (default: True)
• alphabet - something that should be converted to an alphabet of at least nintervals letters

OUTPUT:

iterator – an iterator over permutations

TESTS:

sage: for p in iet.Permutations_iterator(2, alphabet="ab"):
...       print p, "\n****"   #indirect doctest
a b
b a
****
b a
a b
****
sage: for p in iet.Permutations_iterator(3, alphabet="abc"):
...       print p, "\n*****"   #indirect doctest
a b c
b c a
*****
a b c
c a b
*****
a b c
c b a
*****
a c b
b a c
*****
a c b
b c a
*****
a c b
c b a
*****
b a c
a c b
*****
b a c
c a b
*****
b a c
c b a
*****
b c a
a b c
*****
b c a
a c b
*****
b c a
c a b
*****
c a b
a b c
*****
c a b
b a c
*****
c a b
b c a
*****
c b a
a b c
*****
c b a
a c b
*****
c b a
b a c
*****

class sage.combinat.iet.labelled.LabelledRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)

Bases: sage.combinat.iet.template.RauzyDiagram

Template for Rauzy diagrams of labelled permutations.

...DO NOT USE...

class Path(parent, *data)

Bases: sage.combinat.iet.template.Path

Path in Labelled Rauzy diagram.

dual_substitution()

Returns the substitution of intervals obtained.

OUTPUT:

WordMorphism – the word morphism corresponding to the interval

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: p0 = r.path(p,0)
sage: s0 = p0.interval_substitution()
sage: print s0
WordMorphism: a->a, b->ba
sage: p1 = r.path(p,1)
sage: s1 = p1.interval_substitution()
sage: print s1
WordMorphism: a->ab, b->b
sage: (p0 + p1).interval_substitution() == s1 * s0
True
sage: (p1 + p0).interval_substitution() == s0 * s1
True

interval_substitution()

Returns the substitution of intervals obtained.

OUTPUT:

WordMorphism – the word morphism corresponding to the interval

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: p0 = r.path(p,0)
sage: s0 = p0.interval_substitution()
sage: print s0
WordMorphism: a->a, b->ba
sage: p1 = r.path(p,1)
sage: s1 = p1.interval_substitution()
sage: print s1
WordMorphism: a->ab, b->b
sage: (p0 + p1).interval_substitution() == s1 * s0
True
sage: (p1 + p0).interval_substitution() == s0 * s1
True

is_full()

Tests the fullness.

A path is full if all intervals win at least one time.

OUTPUT:

boolean – True if the path is full and False else

EXAMPLE:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: g0 = r.path(p,'t','b','t')
sage: g1 = r.path(p,'b','t','b')
sage: g0.is_full()
False
sage: g1.is_full()
False
sage: (g0 + g1).is_full()
True
sage: (g1 + g0).is_full()
True

matrix()

Returns the matrix associated to a path.

The matrix associated to a Rauzy induction, is the linear application that allows to recover the lengths of self from the lengths of the induced.

OUTPUT:

matrix – a square matrix of integers

EXAMPLES:

sage: p = iet.Permutation('a1 a2','a2 a1')
sage: d = p.rauzy_diagram()
sage: g = d.path(p,'top')
sage: g.matrix()
[1 0]
[1 1]
sage: g = d.path(p,'bottom')
sage: g.matrix()
[1 1]
[0 1]

sage: p = iet.Permutation('a b c','c b a')
sage: d = p.rauzy_diagram()
sage: g = d.path(p)
sage: g.matrix() == identity_matrix(3)
True
sage: g = d.path(p,'top')
sage: g.matrix()
[1 0 0]
[0 1 0]
[1 0 1]
sage: g = d.path(p,'bottom')
sage: g.matrix()
[1 0 1]
[0 1 0]
[0 0 1]

orbit_substitution()

Returns the substitution on the orbit of the left extremity.

OUTPUT:

WordMorhpism – the word morphism corresponding to the orbit

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: d = p.rauzy_diagram()
sage: g0 = d.path(p,'top')
sage: s0 = g0.orbit_substitution()
sage: print s0
WordMorphism: a->ab, b->b
sage: g1 = d.path(p,'bottom')
sage: s1 = g1.orbit_substitution()
sage: print s1
WordMorphism: a->a, b->ab
sage: (g0 + g1).orbit_substitution() == s0 * s1
True
sage: (g1 + g0).orbit_substitution() == s1 * s0
True

substitution()

Returns the substitution on the orbit of the left extremity.

OUTPUT:

WordMorhpism – the word morphism corresponding to the orbit

EXAMPLES:

sage: p = iet.Permutation('a b','b a')
sage: d = p.rauzy_diagram()
sage: g0 = d.path(p,'top')
sage: s0 = g0.orbit_substitution()
sage: print s0
WordMorphism: a->ab, b->b
sage: g1 = d.path(p,'bottom')
sage: s1 = g1.orbit_substitution()
sage: print s1
WordMorphism: a->a, b->ab
sage: (g0 + g1).orbit_substitution() == s0 * s1
True
sage: (g1 + g0).orbit_substitution() == s1 * s0
True

LabelledRauzyDiagram.edge_to_interval_substitution(p=None, edge_type=None)

Returns the interval substitution associated to an edge

OUTPUT:

WordMorphism – the WordMorphism corresponding to the edge

EXAMPLE:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: print r.edge_to_interval_substitution(None,None)
WordMorphism: a->a, b->b, c->c
sage: print r.edge_to_interval_substitution(p,0)
WordMorphism: a->a, b->b, c->ca
sage: print r.edge_to_interval_substitution(p,1)
WordMorphism: a->ac, b->b, c->c

LabelledRauzyDiagram.edge_to_orbit_substitution(p=None, edge_type=None)

Returns the interval substitution associated to an edge

OUTPUT:

WordMorphism – the word morphism corresponding to the edge

EXAMPLE:

sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: print r.edge_to_orbit_substitution(None,None)
WordMorphism: a->a, b->b, c->c
sage: print r.edge_to_orbit_substitution(p,0)
WordMorphism: a->ac, b->b, c->c
sage: print r.edge_to_orbit_substitution(p,1)
WordMorphism: a->a, b->b, c->ac

LabelledRauzyDiagram.full_loop_iterator(start=None, max_length=1)

Returns an iterator over all full path starting at start.

INPUT:

• start - the start point
• max_length - a limit on the length of the paths

OUTPUT:

iterator – iterator over full loops

EXAMPLE:

sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: for g in r.full_loop_iterator(p,2):
...       print g.matrix(), "\n*****"
[1 1]
[1 2]
*****
[2 1]
[1 1]
*****

LabelledRauzyDiagram.full_nloop_iterator(start=None, length=1)

Returns an iterator over all full loops of given length.

INPUT:

• start - the initial permutation
• length - the length to consider

OUTPUT:

iterator – an iterator over the full loops of given length

EXAMPLE:

sage: p = iet.Permutation('a b','b a')
sage: d = p.rauzy_diagram()
sage: for g in d.full_nloop_iterator(p,2):
...       print g.matrix(), "\n*****"
[1 1]
[1 2]
*****
[2 1]
[1 1]
*****