Reduced permutations

A reduced (generalized) permutation is better suited to study strata of Abelian (or quadratic) holomorphic forms on Riemann surfaces. The Rauzy diagram is an invariant of such a component. Corentin Boissy proved the identification of Rauzy diagrams with connected components of stratas. But the geometry of the diagram and the relation with the strata is not yet totally understood.

AUTHORS:

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

TESTS:

sage: from sage.combinat.iet.reduced import ReducedPermutationIET
sage: ReducedPermutationIET([['a','b'],['b','a']])
a b
b a
sage: ReducedPermutationIET([[1,2,3],[3,1,2]])
1 2 3
3 1 2
sage: from sage.combinat.iet.reduced import ReducedPermutationLI
sage: ReducedPermutationLI([[1,1],[2,2,3,3,4,4]])
1 1
2 2 3 3 4 4
sage: ReducedPermutationLI([['a','a','b','b','c','c'],['d','d']])
a a b b c c
d d
sage: from sage.combinat.iet.reduced import FlippedReducedPermutationIET
sage: FlippedReducedPermutationIET([[1,2,3],[3,2,1]],flips=[1,2])
-1 -2  3
 3 -2 -1
sage: FlippedReducedPermutationIET([['a','b','c'],['b','c','a']],flips='b')
 a -b  c
-b  c  a
sage: from sage.combinat.iet.reduced import FlippedReducedPermutationLI
sage: FlippedReducedPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4])
-1 -1
 2  2  3  3 -4 -4
sage: FlippedReducedPermutationLI([['a','a','b','b'],['c','c']],flips='ac')
-a -a  b  b
-c -c
sage: from sage.combinat.iet.reduced import ReducedRauzyDiagram
sage: p = ReducedPermutationIET([[1,2,3],[3,2,1]])
sage: d = ReducedRauzyDiagram(p)

class sage.combinat.iet.reduced.FlippedReducedPermutation(intervals=None, flips=None, alphabet=None)

Bases: sage.combinat.iet.reduced.ReducedPermutation

Flipped Reduced Permutation.

Warning

Internal class! Do not use directly!

INPUT:

• intervals - a list of two lists
• flips - the flipped letters
• alphabet - an alphabet

right_rauzy_move(winner)

Performs a Rauzy move on the right.

EXAMPLE:

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

class sage.combinat.iet.reduced.FlippedReducedPermutationIET(intervals=None, flips=None, alphabet=None)

Bases: sage.combinat.iet.reduced.FlippedReducedPermutation, sage.combinat.iet.template.FlippedPermutationIET, sage.combinat.iet.reduced.ReducedPermutationIET

Flipped Reduced Permutation from iet

EXAMPLES

sage: p = iet.Permutation('a b c', 'c b a', flips=['a'], reduced=True)
sage: p.rauzy_move(1)
-a -b  c
-a  c -b

TESTS:

sage: p = iet.Permutation('a b','b a',flips=['a'])
sage: p == loads(dumps(p))
True

list(flips=False)

Returns a list representation of self.

INPUT:

• flips - boolean (default: False) if True the output contains

  2-uple of (label, flip)

EXAMPLES:

::

sage: p = iet.Permutation(‘a b’,’b a’,reduced=True,flips=’b’) sage: p.list(flips=True) [[(‘a’, 1), (‘b’, -1)], [(‘b’, -1), (‘a’, 1)]] sage: p.list(flips=False) [[‘a’, ‘b’], [‘b’, ‘a’]] sage: p.alphabet([0,1]) sage: p.list(flips=True) [[(0, 1), (1, -1)], [(1, -1), (0, 1)]] sage: p.list(flips=False) [[0, 1], [1, 0]]

One can recover the initial permutation from this list:

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

rauzy_diagram(**kargs)

Returns the associated Rauzy diagram.

EXAMPLES:

sage: p = iet.Permutation('a b','b a',reduced=True,flips='a')
sage: r = p.rauzy_diagram()
sage: p in r
True

class sage.combinat.iet.reduced.FlippedReducedPermutationLI(intervals=None, flips=None, alphabet=None)

Bases: sage.combinat.iet.reduced.FlippedReducedPermutation, sage.combinat.iet.template.FlippedPermutationLI, sage.combinat.iet.reduced.ReducedPermutationLI

Flipped Reduced Permutation from li

EXAMPLES:

Creation using the GeneralizedPermutation function:

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

list(flips=False)

Returns a list representation of self.

INPUT:

• flips - boolean (default: False) return the list with flips

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True,flips='a')
sage: p.list(flips=True)
[[('a', -1), ('a', -1)], [('b', 1), ('b', 1)]]
sage: p.list(flips=False)
[['a', 'a'], ['b', 'b']]

sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True,flips='abc')
sage: p.list(flips=True)
[[('a', -1), ('a', -1), ('b', -1)], [('b', -1), ('c', -1), ('c', -1)]]
sage: p.list(flips=False)
[['a', 'a', 'b'], ['b', 'c', 'c']]

one can rebuild the permutation from the list:

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

rauzy_diagram(**kargs)

Returns the associated Rauzy diagram.

For more explanation and a list of arguments try help(iet.RauzyDiagram)

EXAMPLES:

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

class sage.combinat.iet.reduced.FlippedReducedRauzyDiagram(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.reduced.ReducedRauzyDiagram

Rauzy diagram of flipped reduced permutations.

class sage.combinat.iet.reduced.ReducedPermutation(intervals=None, alphabet=None)

Bases: sage.structure.sage_object.SageObject

Template for reduced objects.

Warning

Internal class! Do not use directly!

INPUT:

• intervals - a list of two list of labels
• alphabet - (default: None) any object that can be used to initialize an Alphabet or None. In this latter case, the letter of the intervals are used to generate one.

erase_letter(letter)

Erases a letter.

INPUT:

• letter - a letter which is a label of an interval of self

EXAMPLES:

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

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

left_rauzy_move(winner)

Performs a Rauzy move on the left.

EXAMPLES:

sage: p = iet.Permutation('a b c','c b a',reduced=True)
sage: p.left_rauzy_move(0)
a b c
b c a
sage: p.right_rauzy_move(1)
a b c
b c a

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

length(interval=None)

Returns the 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 ‘t’ or 0) or ‘bottom’ (or ‘b’ or 1)

OUTPUT:

integer or 2-uple of integers – the corresponding lengths

EXAMPLES:

sage: p = iet.Permutation('a b c','c b a')
sage: p.length()
(3, 3)
sage: p = iet.GeneralizedPermutation('a a b','c d c b d')
sage: p.length()
(3, 5)

length_bottom()

Returns the number of intervals in the bottom segment.

OUTPUT:

integer – the length of the bottom segment

EXAMPLES:

sage: p = iet.Permutation('a b c','c b a')
sage: p.length_bottom()
3
sage: p = iet.GeneralizedPermutation('a a b','c d c b d')
sage: p.length_bottom()
5

length_top()

Returns the number of intervals in the top segment.

OUTPUT:

integer – the length of the top segment

EXAMPLES:

sage: p = iet.Permutation('a b c','c b a')
sage: p.length_top()
3
sage: p = iet.GeneralizedPermutation('a a b','c d c b d')
sage: p.length_top()
3
sage: p = iet.GeneralizedPermutation('a b c b d c d', 'e a e')
sage: p.length_top()
7

right_rauzy_move(winner)

Performs a Rauzy move on the right.

EXAMPLES:

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

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

class sage.combinat.iet.reduced.ReducedPermutationIET(intervals=None, alphabet=None)

Bases: sage.combinat.iet.reduced.ReducedPermutation, sage.combinat.iet.template.PermutationIET

Reduced permutation from iet

Permutation from iet without numerotation of intervals. For initialization, you should use GeneralizedPermutation which is the class factory for all permutation types.

EXAMPLES:

Equality testing (no equality of letters but just of ordering):

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

Reducibility testing:

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

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

Rauzy movability and Rauzy move:

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

Rauzy diagrams:

sage: p = iet.Permutation('a b c d', 'd a b c')
sage: p_red = iet.Permutation('a b c d', 'd a b c', reduced = True)
sage: d = p.rauzy_diagram()
sage: d_red = p_red.rauzy_diagram()
sage: p.rauzy_move(0) in d
True
sage: print d.cardinality(), d_red.cardinality()
12 6

has_rauzy_move(winner, side='right')

Tests if the permutation is rauzy_movable on the left.

EXAMPLES:

sage: p = iet.Permutation('a b c','a c b',reduced=True)
sage: p.has_rauzy_move(0,'right')
True
sage: p.has_rauzy_move(0,'left')
False
sage: p.has_rauzy_move(1,'right')
True
sage: p.has_rauzy_move(1,'left')
False

sage: p = iet.Permutation('a b c d','c a b d',reduced=True)
sage: p.has_rauzy_move(0,'right')
False
sage: p.has_rauzy_move(0,'left')
True
sage: p.has_rauzy_move(1,'right')
False
sage: p.has_rauzy_move(1,'left')
True

is_identity()

Returns True if self is the identity.

EXAMPLES:

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

list()

Returns a list of two list that represents the permutation.

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a b','b a',reduced=True)
sage: p.list() == [p[0], p[1]]
True
sage: p.list() == [['a', 'b'], ['b', 'a']]
True

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

rauzy_diagram(**kargs)

Returns the associated Rauzy diagram.

OUTPUT:

A Rauzy diagram

EXAMPLES:

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

For more information, try help RauzyDiagram

rauzy_move_relabel(winner, side='right')

Returns the relabelization obtained from this move.

EXAMPLE:

sage: p = iet.Permutation('a b c d','d c b a')
sage: q = p.reduced()
sage: p_t = p.rauzy_move('t')
sage: q_t = q.rauzy_move('t')
sage: s_t = q.rauzy_move_relabel('t')
sage: print s_t
WordMorphism: a->a, b->b, c->c, d->d
sage: map(s_t, p_t[0]) == map(Word, q_t[0])
True
sage: map(s_t, p_t[1]) == map(Word, q_t[1])
True
sage: p_b = p.rauzy_move('b')
sage: q_b = q.rauzy_move('b')
sage: s_b = q.rauzy_move_relabel('b')
sage: print s_b
WordMorphism: a->a, b->d, c->b, d->c
sage: map(s_b, q_b[0]) == map(Word, p_b[0])
True
sage: map(s_b, q_b[1]) == map(Word, p_b[1])
True

class sage.combinat.iet.reduced.ReducedPermutationLI(intervals=None, alphabet=None)

Bases: sage.combinat.iet.reduced.ReducedPermutation, sage.combinat.iet.template.PermutationLI

Reduced quadratic (or generalized) permutation.

EXAMPLES:

Reducibility testing:

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

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

Rauzy movavability and Rauzy move:

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

Rauzy diagrams:

sage: p_red = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: d_red = p_red.rauzy_diagram()
sage: d_red.cardinality()
4

list()

The permutations as a list of two lists.

EXAMPLES:

sage: p = iet.GeneralizedPermutation('a b b', 'c c a', reduced = True)
sage: list(p)
[['a', 'b', 'b'], ['c', 'c', 'a']]

rauzy_diagram(**kargs)

Returns the associated Rauzy diagram.

The Rauzy diagram of a permutation corresponds to all permutations that we could obtain from this one by Rauzy move. The set obtained is a labelled Graph. The label of vertices being 0 or 1 depending on the type.

OUTPUT:

Rauzy diagram – the graph of permutations obtained by rauzy induction

EXAMPLES:

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

sage.combinat.iet.reduced.ReducedPermutationsIET_iterator(nintervals=None, irreducible=True, alphabet=None)

Returns an iterator over reduced permutations

INPUT:

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

TESTS:

sage: for p in iet.Permutations_iterator(3,reduced=True,alphabet="abc"):
...    print p  #indirect doctest
a b c
b c a
a b c
c a b
a b c
c b a

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

Bases: sage.combinat.iet.template.RauzyDiagram

Rauzy diagram of reduced permutations

sage.combinat.iet.reduced.alphabetized_atwin(twin, alphabet)

Alphabetization of a twin of iet.

TESTS:

sage: from sage.combinat.iet.reduced import alphabetized_atwin

sage: twin = [[0,1],[0,1]]
sage: alphabet = Alphabet("ab")
sage: alphabetized_atwin(twin, alphabet)
[['a', 'b'], ['a', 'b']]

sage: twin = [[1,0],[1,0]]
sage: alphabet = Alphabet([0,1])
sage: alphabetized_atwin(twin, alphabet)
[[0, 1], [1, 0]]

sage: twin = [[1,2,3,0],[3,0,1,2]]
sage: alphabet = Alphabet("abcd")
sage: alphabetized_atwin(twin,alphabet)
[['a', 'b', 'c', 'd'], ['d', 'a', 'b', 'c']]

sage.combinat.iet.reduced.alphabetized_qtwin(twin, alphabet)

Alphabetization of a qtwin.

TESTS:

sage: from sage.combinat.iet.reduced import alphabetized_qtwin

sage: twin = [[(1,0),(1,1)],[(0,0),(0,1)]]
sage: alphabet = Alphabet("ab")
sage: print alphabetized_qtwin(twin,alphabet)
[['a', 'b'], ['a', 'b']]

sage: twin = [[(1,1), (1,0)],[(0,1), (0,0)]]
sage: alphabet=Alphabet("AB")
sage: alphabetized_qtwin(twin,alphabet)
[['A', 'B'], ['B', 'A']]
sage: alphabet=Alphabet("BA")
sage: alphabetized_qtwin(twin,alphabet)
[['B', 'A'], ['A', 'B']]

sage: twin = [[(0,1),(0,0)],[(1,1),(1,0)]]
sage: alphabet=Alphabet("ab")
sage: print alphabetized_qtwin(twin,alphabet)
[['a', 'a'], ['b', 'b']]

sage: twin = [[(0,2),(1,1),(0,0)],[(1,2),(0,1),(1,0)]]
sage: alphabet=Alphabet("abc")
sage: print alphabetized_qtwin(twin,alphabet)
[['a', 'b', 'a'], ['c', 'b', 'c']]

sage.combinat.iet.reduced.labelize_flip(couple)

Returns a string from a 2-uple couple of the form (name, flip).

TESTS:

sage: from sage.combinat.iet.reduced import labelize_flip
sage: labelize_flip((4,1))
' 4'
sage: labelize_flip(('a',-1))
'-a'