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.dynamics.interval_exchanges.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.dynamics.interval_exchanges.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.dynamics.interval_exchanges.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.dynamics.interval_exchanges.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.dynamics.interval_exchanges.reduced import ReducedRauzyDiagram
sage: p = ReducedPermutationIET([[1,2,3],[3,2,1]])
sage: d = ReducedRauzyDiagram(p)
-
class
sage.dynamics.interval_exchanges.reduced.
FlippedReducedPermutation
(intervals=None, flips=None, alphabet=None)¶ Bases:
sage.dynamics.interval_exchanges.reduced.ReducedPermutation
Flipped Reduced Permutation.
Warning
Internal class! Do not use directly!
INPUT:
intervals
- a list of two listsflips
- the flipped lettersalphabet
- 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.dynamics.interval_exchanges.reduced.
FlippedReducedPermutationIET
(intervals=None, flips=None, alphabet=None)¶ Bases:
sage.dynamics.interval_exchanges.reduced.FlippedReducedPermutation
,sage.dynamics.interval_exchanges.template.FlippedPermutationIET
,sage.dynamics.interval_exchanges.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.dynamics.interval_exchanges.reduced.
FlippedReducedPermutationLI
(intervals=None, flips=None, alphabet=None)¶ Bases:
sage.dynamics.interval_exchanges.reduced.FlippedReducedPermutation
,sage.dynamics.interval_exchanges.template.FlippedPermutationLI
,sage.dynamics.interval_exchanges.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.dynamics.interval_exchanges.reduced.
FlippedReducedRauzyDiagram
(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)¶ Bases:
sage.dynamics.interval_exchanges.template.FlippedRauzyDiagram
,sage.dynamics.interval_exchanges.reduced.ReducedRauzyDiagram
Rauzy diagram of flipped reduced permutations.
-
class
sage.dynamics.interval_exchanges.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 labelsalphabet
- (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)¶ Bases:
sage.dynamics.interval_exchanges.reduced.ReducedPermutation
,sage.dynamics.interval_exchanges.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: 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
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: 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)¶ Bases:
sage.dynamics.interval_exchanges.reduced.ReducedPermutation
,sage.dynamics.interval_exchanges.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.dynamics.interval_exchanges.reduced.
ReducedPermutationsIET_iterator
(nintervals=None, irreducible=True, alphabet=None)¶ Returns an iterator over reduced permutations
INPUT:
nintervals
- integer or Noneirreducible
- booleanalphabet
- 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.dynamics.interval_exchanges.reduced.
ReducedRauzyDiagram
(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)¶ Bases:
sage.dynamics.interval_exchanges.template.RauzyDiagram
Rauzy diagram of reduced permutations
-
sage.dynamics.interval_exchanges.reduced.
alphabetized_atwin
(twin, alphabet)¶ Alphabetization of a twin of iet.
TESTS:
sage: from sage.dynamics.interval_exchanges.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.dynamics.interval_exchanges.reduced.
alphabetized_qtwin
(twin, alphabet)¶ Alphabetization of a qtwin.
TESTS:
sage: from sage.dynamics.interval_exchanges.reduced import alphabetized_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).
TESTS:
sage: from sage.dynamics.interval_exchanges.reduced import labelize_flip sage: labelize_flip((4,1)) ' 4' sage: labelize_flip(('a',-1)) '-a'