# Reduced permutations¶

Warning

This module is deprecated. You are advised to install and use the surface_dynamics package instead available at https://pypi.python.org/pypi/surface_dynamics/

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
class sage.dynamics.interval_exchanges.reduced.FlippedReducedPermutation(intervals=None, flips=None, alphabet=None)

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.

EXAMPLES:

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.dynamics.interval_exchanges.reduced.FlippedReducedPermutationIET(intervals=None, flips=None, alphabet=None)

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

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.dynamics.interval_exchanges.reduced.FlippedReducedPermutationLI(intervals=None, flips=None, alphabet=None)

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.dynamics.interval_exchanges.reduced.FlippedReducedRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)

Rauzy diagram of flipped reduced permutations.

class sage.dynamics.interval_exchanges.reduced.ReducedPermutation(intervals=None, alphabet=None)

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.dynamics.interval_exchanges.reduced.ReducedPermutationIET(intervals=None, alphabet=None)

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


rauzy_move_relabel(winner, side='right')

Returns the relabelization obtained from this move.

EXAMPLES:

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: s_t
WordMorphism: a->a, b->b, c->c, d->d
sage: list(map(s_t, p_t[0])) == list(map(Word, q_t[0]))
True
sage: list(map(s_t, p_t[1])) == list(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: s_b
WordMorphism: a->a, b->d, c->b, d->c
sage: list(map(s_b, q_b[0])) == list(map(Word, p_b[0]))
True
sage: list(map(s_b, q_b[1])) == list(map(Word, p_b[1]))
True

class sage.dynamics.interval_exchanges.reduced.ReducedPermutationLI(intervals=None, alphabet=None)

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 movability 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.dynamics.interval_exchanges.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
class sage.dynamics.interval_exchanges.reduced.ReducedRauzyDiagram(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)

Rauzy diagram of reduced permutations

sage.dynamics.interval_exchanges.reduced.alphabetized_atwin(twin, alphabet)

Alphabetization of a twin of iet.

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.dynamics.interval_exchanges.reduced.alphabetized_qtwin(twin, alphabet)

Alphabetization of a qtwin.

sage: twin = [[(1,0),(1,1)],[(0,0),(0,1)]]
sage: alphabet = Alphabet("ab")
sage: 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: 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: alphabetized_qtwin(twin,alphabet)
[['a', 'b', 'a'], ['c', 'b', 'c']]

sage.dynamics.interval_exchanges.reduced.labelize_flip(couple)

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