Permutations template¶
This file define high level operations on permutations (alphabet, the different rauzy induction, ...) shared by reduced and labeled permutations.
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
Todo
- construct as options different string representations for a permutation
- the two intervals: str
- the two intervals on one line: str_one_line
- the separatrix diagram: str_separatrix_diagram
- twin[0] and twin[1] for reduced permutation
- nothing (useful for Rauzy diagram)
-
class
sage.dynamics.interval_exchanges.template.
FlippedPermutation
¶ Bases:
sage.dynamics.interval_exchanges.template.Permutation
Template for flipped generalized permutations.
Warning
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
-
str
(sep='\n')¶ String representation.
TESTS:
sage: p = iet.GeneralizedPermutation('a a','b b',flips='a') sage: print(p.str()) -a -a b b sage: print(p.str('/')) -a -a/ b b
-
class
sage.dynamics.interval_exchanges.template.
FlippedPermutationIET
¶ Bases:
sage.dynamics.interval_exchanges.template.FlippedPermutation
,sage.dynamics.interval_exchanges.template.PermutationIET
Template for flipped Abelian permutations.
Warning
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
-
flips
()¶ Returns the list of flips.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a',flips='ac') sage: p.flips() ['a', 'c']
-
class
sage.dynamics.interval_exchanges.template.
FlippedPermutationLI
¶ Bases:
sage.dynamics.interval_exchanges.template.FlippedPermutation
,sage.dynamics.interval_exchanges.template.PermutationLI
Template for flipped quadratic permutations.
Warning
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
-
flips
()¶ Returns the list of flipped intervals.
EXAMPLES:
sage: p = iet.GeneralizedPermutation('a a','b b',flips='a') sage: p.flips() ['a'] sage: p = iet.GeneralizedPermutation('a a','b b',flips='b',reduced=True) sage: p.flips() ['b']
-
class
sage.dynamics.interval_exchanges.template.
FlippedRauzyDiagram
(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)¶ Bases:
sage.dynamics.interval_exchanges.template.RauzyDiagram
Template for flipped Rauzy diagrams.
Warning
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2009-09-29): initial version
-
complete
(p, reducible=False)¶ Completion of the Rauzy diagram
Add all successors of p for defined operations in edge_types. Could be used for generating non (strongly) connected Rauzy diagrams. Sometimes, for flipped permutations, the maximal connected graph in all permutations is not strongly connected. Finding such components needs to call most than once the .complete() method.
INPUT:
p
- a permutationreducible
- put or not reducible permutations
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a',flips='a') sage: d = p.rauzy_diagram() sage: d Rauzy diagram with 3 permutations sage: p = iet.Permutation('a b c','c b a',flips='b') sage: d.complete(p) sage: d Rauzy diagram with 8 permutations sage: p = iet.Permutation('a b c','c b a',flips='a') sage: d.complete(p) sage: d Rauzy diagram with 8 permutations
-
class
sage.dynamics.interval_exchanges.template.
Permutation
¶ Bases:
sage.structure.sage_object.SageObject
Template for all permutations.
Warning
Internal class! Do not use directly!
This class implement generic algorithm (stratum, connected component, ...) and unfies all its children.
-
alphabet
(data=None)¶ Manages the alphabet of self.
If there is no argument, the method returns the alphabet used. If the argument could be converted to an alphabet, this alphabet will be used.
INPUT:
data
- None or something that could be converted to an alphabet
OUTPUT:
– either None or the current alphabet
EXAMPLES:
sage: p = iet.Permutation('a b','a b') sage: p.alphabet([0,1]) sage: p.alphabet() == Alphabet([0,1]) True sage: p 0 1 0 1 sage: p.alphabet("cd") sage: p.alphabet() == Alphabet(['c','d']) True sage: p c d c d
-
has_rauzy_move
(winner='top', side=None)¶ Tests the legality of a Rauzy move.
INPUT:
winner
- ‘top’ or ‘bottom’ corresponding to the intervalside
- ‘left’ or ‘right’ (default)
OUTPUT:
– a boolean
EXAMPLES:
sage: p = iet.Permutation('a b','a b') sage: p.has_rauzy_move('top','right') False sage: p.has_rauzy_move('bottom','right') False sage: p.has_rauzy_move('top','left') False sage: p.has_rauzy_move('bottom','left') False
sage: p = iet.Permutation('a b c','b a c') sage: p.has_rauzy_move('top','right') False sage: p.has_rauzy_move('bottom', 'right') False sage: p.has_rauzy_move('top','left') True sage: p.has_rauzy_move('bottom','left') True
sage: p = iet.Permutation('a b','b a') sage: p.has_rauzy_move('top','right') True sage: p.has_rauzy_move('bottom','right') True sage: p.has_rauzy_move('top','left') True sage: p.has_rauzy_move('bottom','left') True
-
horizontal_inverse
()¶ Returns the top-bottom inverse.
You can use also use the shorter .tb_inverse().
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: p.top_bottom_inverse() b a a b sage: p = iet.Permutation('a b','b a',reduced=True) sage: p.top_bottom_inverse() == p True
sage: p = iet.Permutation('a b c d','c d a b') sage: p.top_bottom_inverse() c d a b a b c d
TESTS:
sage: p = iet.Permutation('a b','a b') sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False
-
left_right_inverse
()¶ Returns the left-right inverse.
You can also use the shorter .lr_inverse()
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b c','c a b') sage: p.left_right_inverse() c b a b a c sage: p = iet.Permutation('a b c d','c d a b') sage: p.left_right_inverse() d c b a b a d c
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: p.left_right_inverse() a a c c b b
sage: p = iet.Permutation('a b c','c b a',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.Permutation('a b c','c a b',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a b c b c a
sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.GeneralizedPermutation('a b b','c c a',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a a b b c c
TESTS:
sage: p = iet.GeneralizedPermutation('a a','b b') sage: p.left_right_inverse() a a b b sage: p is p.left_right_inverse() False sage: p == p.left_right_inverse() True
-
letters
()¶ Returns the list of letters of the alphabet used for representation.
The letters used are not necessarily the whole alphabet (for example if the alphabet is infinite).
OUTPUT:
– a list of labels
EXAMPLES:
sage: p = iet.Permutation([1,2],[2,1]) sage: p.alphabet(Alphabet(name="NN")) sage: p 0 1 1 0 sage: p.letters() [0, 1]
-
lr_inverse
()¶ Returns the left-right inverse.
You can also use the shorter .lr_inverse()
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b c','c a b') sage: p.left_right_inverse() c b a b a c sage: p = iet.Permutation('a b c d','c d a b') sage: p.left_right_inverse() d c b a b a d c
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: p.left_right_inverse() a a c c b b
sage: p = iet.Permutation('a b c','c b a',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.Permutation('a b c','c a b',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a b c b c a
sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.GeneralizedPermutation('a b b','c c a',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a a b b c c
TESTS:
sage: p = iet.GeneralizedPermutation('a a','b b') sage: p.left_right_inverse() a a b b sage: p is p.left_right_inverse() False sage: p == p.left_right_inverse() True
-
rauzy_move
(winner, side='right', iteration=1)¶ Returns the permutation after a Rauzy move.
INPUT:
winner
- ‘top’ or ‘bottom’ intervalside
- ‘right’ or ‘left’ (default: ‘right’) corresponding to the side on which the Rauzy move must be performed.iteration
- a non negative integer
OUTPUT:
- a permutation
TESTS:
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move(winner=0, side='right') == p True sage: p.rauzy_move(winner=1, side='right') == p True sage: p.rauzy_move(winner=0, side='left') == p True sage: p.rauzy_move(winner=1, side='left') == p True
sage: p = iet.Permutation('a b c','c b a') sage: p.rauzy_move(winner=0, side='right') a b c c a b sage: p.rauzy_move(winner=1, side='right') a c b c b a sage: p.rauzy_move(winner=0, side='left') a b c b c a sage: p.rauzy_move(winner=1, side='left') b a c c b a
-
str
(sep='\n')¶ A string representation of the generalized permutation.
INPUT:
sep
- (default: ‘n’) a separator for the two intervals
OUTPUT:
string – the string that represents the permutation
EXAMPLES:
For permutations of iet:
sage: p = iet.Permutation('a b c','c b a') sage: p.str() 'a b c\nc b a' sage: p.str(sep=' | ') 'a b c | c b a'
..the permutation can be rebuilt from the standard string:
sage: p == iet.Permutation(p.str()) True
For permutations of li:
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.str() 'a b b\nc c a' sage: p.str(sep=' | ') 'a b b | c c a'
..the generalized permutation can be rebuilt from the standard string:
sage: p == iet.GeneralizedPermutation(p.str()) True
-
symmetric
()¶ Returns the symmetric permutation.
The symmetric permutation is the composition of the top-bottom inversion and the left-right inversion (which are geometrically orientation reversing).
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation("a b c","c b a") sage: p.symmetric() a b c c b a sage: q = iet.Permutation("a b c d","b d a c") sage: q.symmetric() c a d b d c b a
sage: p = iet.Permutation('a b c d','c a d b') sage: q = p.symmetric() sage: q1 = p.tb_inverse().lr_inverse() sage: q2 = p.lr_inverse().tb_inverse() sage: q == q1 True sage: q == q2 True
TESTS:
sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True) sage: q = p.symmetric() sage: q1 = p.tb_inverse().lr_inverse() sage: q2 = p.lr_inverse().tb_inverse() sage: q == q1 True sage: q == q2 True
sage: p = iet.GeneralizedPermutation('a a b','b c c',reduced=True,flips='a') sage: q = p.symmetric() sage: q1 = p.tb_inverse().lr_inverse() sage: q2 = p.lr_inverse().tb_inverse() sage: q == q1 True sage: q == q2 True
-
tb_inverse
()¶ Returns the top-bottom inverse.
You can use also use the shorter .tb_inverse().
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: p.top_bottom_inverse() b a a b sage: p = iet.Permutation('a b','b a',reduced=True) sage: p.top_bottom_inverse() == p True
sage: p = iet.Permutation('a b c d','c d a b') sage: p.top_bottom_inverse() c d a b a b c d
TESTS:
sage: p = iet.Permutation('a b','a b') sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False
-
top_bottom_inverse
()¶ Returns the top-bottom inverse.
You can use also use the shorter .tb_inverse().
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: p.top_bottom_inverse() b a a b sage: p = iet.Permutation('a b','b a',reduced=True) sage: p.top_bottom_inverse() == p True
sage: p = iet.Permutation('a b c d','c d a b') sage: p.top_bottom_inverse() c d a b a b c d
TESTS:
sage: p = iet.Permutation('a b','a b') sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) sage: p == p.top_bottom_inverse() True sage: p is p.top_bottom_inverse() False
-
vertical_inverse
()¶ Returns the left-right inverse.
You can also use the shorter .lr_inverse()
OUTPUT:
– a permutation
EXAMPLES:
sage: p = iet.Permutation('a b c','c a b') sage: p.left_right_inverse() c b a b a c sage: p = iet.Permutation('a b c d','c d a b') sage: p.left_right_inverse() d c b a b a d c
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: p.left_right_inverse() a a c c b b
sage: p = iet.Permutation('a b c','c b a',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.Permutation('a b c','c a b',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a b c b c a
sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True) sage: p.left_right_inverse() == p True sage: p = iet.GeneralizedPermutation('a b b','c c a',reduced=True) sage: q = p.left_right_inverse() sage: q == p False sage: q a a b b c c
TESTS:
sage: p = iet.GeneralizedPermutation('a a','b b') sage: p.left_right_inverse() a a b b sage: p is p.left_right_inverse() False sage: p == p.left_right_inverse() True
-
-
class
sage.dynamics.interval_exchanges.template.
PermutationIET
¶ Bases:
sage.dynamics.interval_exchanges.template.Permutation
Template for permutation from Interval Exchange Transformation.
Warning
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version
-
arf_invariant
()¶ Returns the Arf invariant of the suspension of self.
OUTPUT:
integer – 0 or 1
EXAMPLES:
Permutations from the odd and even component of H(2,2,2):
sage: a = range(10) sage: b1 = [3,2,4,6,5,7,9,8,1,0] sage: b0 = [6,5,4,3,2,7,9,8,1,0] sage: p1 = iet.Permutation(a,b1) sage: p1.arf_invariant() 1 sage: p0 = iet.Permutation(a,b0) sage: p0.arf_invariant() 0
Permutations from the odd and even component of H(4,4):
sage: a = range(11) sage: b1 = [3,2,5,4,6,8,7,10,9,1,0] sage: b0 = [5,4,3,2,6,8,7,10,9,1,0] sage: p1 = iet.Permutation(a,b1) sage: p1.arf_invariant() 1 sage: p0 = iet.Permutation(a,b0) sage: p0.arf_invariant() 0
REFERENCES:
[Jo80] D. Johnson, “Spin structures and quadratic forms on surfaces”, J. London Math. Soc (2), 22, 1980, 365-373
[KoZo03] M. Kontsevich, A. Zorich “Connected components of the moduli spaces of Abelian differentials with prescribed singularities”, Inventiones Mathematicae, 153, 2003, 631-678
-
attached_in_degree
()¶ Returns the degree of the singularity at the right of the interval.
OUTPUT:
– a positive integer
EXAMPLES:
sage: p1 = iet.Permutation('a b c d e f g','d c g f e b a') sage: p2 = iet.Permutation('a b c d e f g','e d c g f b a') sage: p1.attached_in_degree() 1 sage: p2.attached_in_degree() 3
-
attached_out_degree
()¶ Returns the degree of the singularity at the left of the interval.
OUTPUT:
– a positive integer
EXAMPLES:
sage: p1 = iet.Permutation('a b c d e f g','d c g f e b a') sage: p2 = iet.Permutation('a b c d e f g','e d c g f b a') sage: p1.attached_out_degree() 3 sage: p2.attached_out_degree() 1
-
attached_type
()¶ Return the singularity degree attached on the left and the right.
OUTPUT:
([degre], angle_parity)
– if the same singularity is attached on the left and right([left_degree, right_degree], 0)
– the degrees at the left and the right which are different singularititesEXAMPLES:
With two intervals:
sage: p = iet.Permutation('a b','b a') sage: p.attached_type() ([0], 1)
With three intervals:
sage: p = iet.Permutation('a b c','b c a') sage: p.attached_type() ([0], 1) sage: p = iet.Permutation('a b c','c a b') sage: p.attached_type() ([0], 1) sage: p = iet.Permutation('a b c','c b a') sage: p.attached_type() ([0, 0], 0)
With four intervals:
sage: p = iet.Permutation('1 2 3 4','4 3 2 1') sage: p.attached_type() ([2], 0)
-
connected_component
(marked_separatrix='no')¶ Returns a connected components of a stratum.
EXAMPLES:
Permutations from the stratum H(6):
sage: a = range(8) sage: b_hyp = [7,6,5,4,3,2,1,0] sage: b_odd = [3,2,5,4,7,6,1,0] sage: b_even = [5,4,3,2,7,6,1,0] sage: p_hyp = iet.Permutation(a, b_hyp) sage: p_odd = iet.Permutation(a, b_odd) sage: p_even = iet.Permutation(a, b_even) sage: p_hyp.connected_component() H_hyp(6) sage: p_odd.connected_component() H_odd(6) sage: p_even.connected_component() H_even(6)
Permutations from the stratum H(4,4):
sage: a = range(11) sage: b_hyp = [10,9,8,7,6,5,4,3,2,1,0] sage: b_odd = [3,2,5,4,6,8,7,10,9,1,0] sage: b_even = [5,4,3,2,6,8,7,10,9,1,0] sage: p_hyp = iet.Permutation(a,b_hyp) sage: p_odd = iet.Permutation(a,b_odd) sage: p_even = iet.Permutation(a,b_even) sage: p_hyp.stratum() == AbelianStratum(4,4) True sage: p_hyp.connected_component() H_hyp(4, 4) sage: p_odd.stratum() == AbelianStratum(4,4) True sage: p_odd.connected_component() H_odd(4, 4) sage: p_even.stratum() == AbelianStratum(4,4) True sage: p_even.connected_component() H_even(4, 4)
As for stratum you can specify that you want to attach the singularity on the left of the interval using the option marked_separatrix:
sage: a = [1,2,3,4,5,6,7,8,9] sage: b4_odd = [4,3,6,5,7,9,8,2,1] sage: b4_even = [6,5,4,3,7,9,8,2,1] sage: b2_odd = [4,3,5,7,6,9,8,2,1] sage: b2_even = [7,6,5,4,3,9,8,2,1] sage: p4_odd = iet.Permutation(a,b4_odd) sage: p4_even = iet.Permutation(a,b4_even) sage: p2_odd = iet.Permutation(a,b2_odd) sage: p2_even = iet.Permutation(a,b2_even) sage: p4_odd.connected_component(marked_separatrix='out') H_odd^out(4, 2) sage: p4_even.connected_component(marked_separatrix='out') H_even^out(4, 2) sage: p2_odd.connected_component(marked_separatrix='out') H_odd^out(2, 4) sage: p2_even.connected_component(marked_separatrix='out') H_even^out(2, 4) sage: p2_odd.connected_component() == p4_odd.connected_component() True sage: p2_odd.connected_component('out') == p4_odd.connected_component('out') False
-
cylindric
()¶ Returns a permutation in the Rauzy class such that
twin[0][-1] == 0 twin[1][-1] == 0TESTS:
sage: p = iet.Permutation('a b c','c b a') sage: p.cylindric() == p True sage: p = iet.Permutation('a b c d','b d a c') sage: q = p.cylindric() sage: q[0][0] == q[1][-1] True sage: q[1][0] == q[1][0] True
-
decompose
()¶ Returns the decomposition of self.
OUTPUT:
– a list of permutations
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a').decompose()[0] sage: p a b c c b a
sage: p1,p2,p3 = iet.Permutation('a b c d e','b a c e d').decompose() sage: p1 a b b a sage: p2 c c sage: p3 d e e d
-
erase_marked_points
()¶ Returns a permutation equivalent to self but without marked points.
EXAMPLES:
sage: a = iet.Permutation('a b1 b2 c d', 'd c b1 b2 a') sage: a.erase_marked_points() a b1 c d d c b1 a
-
genus
()¶ Returns the genus corresponding to any suspension of the permutation.
OUTPUT:
– a positive integer
EXAMPLES:
sage: p = iet.Permutation('a b c', 'c b a') sage: p.genus() 1
sage: p = iet.Permutation('a b c d','d c b a') sage: p.genus() 2
- REFERENCES:
- Veech
-
intersection_matrix
()¶ Returns the intersection matrix.
This \(d*d\) antisymmetric matrix is given by the rule :
\[\begin{split}m_{ij} = \begin{cases} 1 & \text{$i < j$ and $\pi(i) > \pi(j)$} \\ -1 & \text{$i > j$ and $\pi(i) < \pi(j)$} \\ 0 & \text{else} \end{cases}\end{split}\]OUTPUT:
- a matrix
EXAMPLES:
sage: p = iet.Permutation('a b c d','d c b a') sage: p.intersection_matrix() [ 0 1 1 1] [-1 0 1 1] [-1 -1 0 1] [-1 -1 -1 0]
sage: p = iet.Permutation('1 2 3 4 5','5 3 2 4 1') sage: p.intersection_matrix() [ 0 1 1 1 1] [-1 0 1 0 1] [-1 -1 0 0 1] [-1 0 0 0 1] [-1 -1 -1 -1 0]
-
is_cylindric
()¶ Returns True if the permutation is Rauzy_1n.
A permutation is cylindric if 1 and n are exchanged.
EXAMPLES:
sage: iet.Permutation('1 2 3','3 2 1').is_cylindric() True sage: iet.Permutation('1 2 3','2 1 3').is_cylindric() False
-
is_hyperelliptic
()¶ Returns True if the permutation is in the class of the symmetric permutations (with eventual marked points).
This is equivalent to say that the suspension lives in an hyperelliptic stratum of Abelian differentials H_hyp(2g-2) or H_hyp(g-1, g-1) with some marked points.
EXAMPLES:
sage: iet.Permutation('a b c d','d c b a').is_hyperelliptic() True sage: iet.Permutation('0 1 2 3 4 5','5 2 1 4 3 0').is_hyperelliptic() False
REFERENCES:
Gerard Rauzy, “Echanges d’intervalles et transformations induites”, Acta Arith. 34, no. 3, 203-212, 1980
M. Kontsevich, A. Zorich “Connected components of the moduli space of Abelian differentials with prescribed singularities” Invent. math. 153, 631-678 (2003)
-
is_irreducible
(return_decomposition=False)¶ Tests the irreducibility.
An abelian permutation p = (p0,p1) is reducible if: set(p0[:i]) = set(p1[:i]) for an i < len(p0)
OUTPUT:
- a boolean
EXAMPLES:
sage: p = iet.Permutation('a b c', 'c b a') sage: p.is_irreducible() True sage: p = iet.Permutation('a b c', 'b a c') sage: p.is_irreducible() False
-
order_of_rauzy_action
(winner, side=None)¶ Returns the order of the action of a Rauzy move.
INPUT:
winner
- string'top'
or'bottom'
side
- string'left'
or'right'
OUTPUT:
An integer corresponding to the order of the Rauzy action.
EXAMPLES:
sage: p = iet.Permutation('a b c d','d a c b') sage: p.order_of_rauzy_action('top', 'right') 3 sage: p.order_of_rauzy_action('bottom', 'right') 2 sage: p.order_of_rauzy_action('top', 'left') 1 sage: p.order_of_rauzy_action('bottom', 'left') 3
-
separatrix_diagram
(side=False)¶ Returns the separatrix diagram of the permutation.
INPUT:
side
- boolean
OUTPUT:
– a list of lists
EXAMPLES:
sage: iet.Permutation([0, 1], [1, 0]).separatrix_diagram() [[(1, 0), (1, 0)]]
sage: iet.Permutation('a b c d','d c b a').separatrix_diagram() [[('d', 'a'), 'b', 'c', ('d', 'a'), 'b', 'c']]
-
stratum
(marked_separatrix='no')¶ Returns the strata in which any suspension of this permutation lives.
OUTPUT:
- a stratum of Abelian differentials
EXAMPLES:
sage: p = iet.Permutation('a b c', 'c b a') sage: p.stratum() H(0, 0) sage: p = iet.Permutation('a b c d', 'd a b c') sage: p.stratum() H(0, 0, 0) sage: p = iet.Permutation(range(9), [8,5,2,7,4,1,6,3,0]) sage: p.stratum() H(1, 1, 1, 1)
You can specify that you want to attach the singularity on the left (or on the right) with the option marked_separatrix:
sage: a = 'a b c d e f g h i j' sage: b3 = 'd c g f e j i h b a' sage: b2 = 'd c e g f j i h b a' sage: b1 = 'e d c g f h j i b a' sage: p3 = iet.Permutation(a, b3) sage: p3.stratum() H(3, 2, 1) sage: p3.stratum(marked_separatrix='out') H^out(3, 2, 1) sage: p2 = iet.Permutation(a, b2) sage: p2.stratum() H(3, 2, 1) sage: p2.stratum(marked_separatrix='out') H^out(2, 3, 1) sage: p1 = iet.Permutation(a, b1) sage: p1.stratum() H(3, 2, 1) sage: p1.stratum(marked_separatrix='out') H^out(1, 3, 2)
- AUTHORS:
- Vincent Delecroix (2008-12-20)
-
to_permutation
()¶ Returns the permutation as an element of the symmetric group.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: p.to_permutation() [3, 2, 1]
sage: p = Permutation([2,4,1,3]) sage: q = iet.Permutation(p) sage: q.to_permutation() == p True
-
class
sage.dynamics.interval_exchanges.template.
PermutationLI
¶ Bases:
sage.dynamics.interval_exchanges.template.Permutation
Template for quadratic permutation.
Warning
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version
-
has_right_rauzy_move
(winner)¶ Test of Rauzy movability (with an eventual specified choice of 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
- the integer ‘top’ or ‘bottom’
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
-
is_irreducible
(return_decomposition=False)¶ Test of reducibility
A quadratic (or generalized) permutation is reducible if there exists a decomposition
\[ \begin{align}\begin{aligned}A1 u B1 | ... | B1 u A2\\A1 u B2 | ... | B2 u A2\end{aligned}\end{align} \]where no corners is empty, or exactly one corner is empty and it is on the left, or two and they are both on the right or on the left. The definition is due to [BL08] where they prove that the property of being irreducible is stable under Rauzy induction.
INPUT:
return_decomposition
- boolean (default: False) - if True, and the permutation is reducible, returns also the blocs A1 u B1, B1 u A2, A1 u B2 and B2 u A2 of a decomposition as above.
OUTPUT:
If return_decomposition is True, returns a 2-uple (test,decomposition) where test is the preceding test and decomposition is a 4-uple (A11,A12,A21,A22) where:
A11 = A1 u B1 A12 = B1 u A2 A21 = A1 u B2 A22 = B2 u A2
EXAMPLES:
sage: GP = iet.GeneralizedPermutation sage: GP('a a','b b').is_irreducible() False sage: GP('a a b','b c c').is_irreducible() True sage: GP('1 2 3 4 5 1','5 6 6 4 3 2').is_irreducible() True
TESTS:
Test reducible permutations with no empty corner:
sage: GP('1 4 1 3','4 2 3 2').is_irreducible(True) (False, (['1', '4'], ['1', '3'], ['4', '2'], ['3', '2']))
Test reducible permutations with one left corner empty:
sage: GP('1 2 2 3 1','4 4 3').is_irreducible(True) (False, (['1'], ['3', '1'], [], ['3'])) sage: GP('4 4 3','1 2 2 3 1').is_irreducible(True) (False, ([], ['3'], ['1'], ['3', '1']))
Test reducible permutations with two left corners empty:
sage: GP('1 1 2 3','4 2 4 3').is_irreducible(True) (False, ([], ['3'], [], ['3']))
Test reducible permutations with two right corners empty:
sage: GP('1 2 2 3 3','1 4 4').is_irreducible(True) (False, (['1'], [], ['1'], [])) sage: GP('1 2 2','1 3 3').is_irreducible(True) (False, (['1'], [], ['1'], [])) sage: GP('1 2 3 3','2 1 4 4 5 5').is_irreducible(True) (False, (['1', '2'], [], ['2', '1'], []))
AUTHORS:
- Vincent Delecroix (2008-12-20)
-
class
sage.dynamics.interval_exchanges.template.
RauzyDiagram
(p, right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False)¶ Bases:
sage.structure.sage_object.SageObject
Template for Rauzy diagrams.
Warning
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
-
class
Path
(parent, *data)¶ Bases:
sage.structure.sage_object.SageObject
Path in Rauzy diagram.
A path in a Rauzy diagram corresponds to a subsimplex of the simplex of lengths. This correspondance is obtained via the Rauzy induction. To a idoc IET we can associate a unique path in a Rauzy diagram. This establishes a correspondance between infinite full path in Rauzy diagram and equivalence topologic class of IET.-
append
(edge_type)¶ Append an edge to the path.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p) sage: g.append('top') sage: g Path of length 1 in a Rauzy diagram sage: g.append('bottom') sage: g Path of length 2 in a Rauzy diagram
-
composition
(function, composition=None)¶ Compose an edges function on a path
INPUT:
path
- either a Path or a tuple describing a pathfunction
- function must be of the formcomposition
- the composition function
AUTHOR:
- Vincent Delecroix (2009-09-29)
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: def f(i,t): ....: if t is None: return [] ....: return [t] sage: g = r.path(p) sage: g.composition(f,list.__add__) [] sage: g = r.path(p,0,1) sage: g.composition(f, list.__add__) [0, 1]
-
edge_types
()¶ Returns the edge types of the path.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p, 0, 1) sage: g.edge_types() [0, 1]
-
end
()¶ Returns the last vertex of the path.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g1 = r.path(p, 't', 'b', 't') sage: g1.end() == p True sage: g2 = r.path(p, 'b', 't', 'b') sage: g2.end() == p True
-
extend
(path)¶ Extends self with another path.
EXAMPLES:
sage: p = iet.Permutation('a b c d','d c b a') sage: r = p.rauzy_diagram() sage: g1 = r.path(p,'t','t') sage: g2 = r.path(p.rauzy_move('t',iteration=2),'b','b') sage: g = r.path(p,'t','t','b','b') sage: g == g1 + g2 True sage: g = copy(g1) sage: g.extend(g2) sage: g == g1 + g2 True
-
is_loop
()¶ Tests whether the path is a loop (start point = end point).
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: r.path(p).is_loop() True sage: r.path(p,0,1,0,0).is_loop() True
-
losers
()¶ Returns a list of the loosers on the path.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g0 = r.path(p,'t','b','t') sage: g0.losers() ['a', 'c', 'b'] sage: g1 = r.path(p,'b','t','b') sage: g1.losers() ['c', 'a', 'b']
-
pop
()¶ Pops the queue of the path
OUTPUT:
a path corresponding to the last edge
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: g = r.path(p,0,1,0) sage: g0,g1,g2,g3 = g[0], g[1], g[2], g[3] sage: g.pop() == r.path(g2,0) True sage: g == r.path(g0,0,1) True sage: g.pop() == r.path(g1,1) True sage: g == r.path(g0,0) True sage: g.pop() == r.path(g0,0) True sage: g == r.path(g0) True sage: g.pop() == r.path(g0) True
-
right_composition
(function, composition=None)¶ Compose an edges function on a path
INPUT:
function
- function must be of the form (indice,type) -> element. Moreover function(None,None) must be an identity element for initialization.composition
- the composition function for the function. * if None (default None)
TEST:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: def f(i,t): ....: if t is None: return [] ....: return [t] sage: g = r.path(p) sage: g.right_composition(f,list.__add__) [] sage: g = r.path(p,0,1) sage: g.right_composition(f, list.__add__) [1, 0]
-
start
()¶ Returns the first vertex of the path.
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p, 't', 'b') sage: g.start() == p True
-
winners
()¶ Returns the winner list associated to the edge of the path.
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: r.path(p).winners() [] sage: r.path(p,0).winners() ['b'] sage: r.path(p,1).winners() ['a']
-
-
RauzyDiagram.
alphabet
(data=None)¶ TESTS:
sage: r = iet.RauzyDiagram('a b','b a') sage: r.alphabet() == Alphabet(['a','b']) True sage: r = iet.RauzyDiagram([0,1],[1,0]) sage: r.alphabet() == Alphabet([0,1]) True
-
RauzyDiagram.
cardinality
()¶ Returns the number of permutations in this Rauzy diagram.
OUTPUT:
- \(integer\) - the number of vertices in the diagram
EXAMPLES:
sage: r = iet.RauzyDiagram('a b','b a') sage: r.cardinality() 1 sage: r = iet.RauzyDiagram('a b c','c b a') sage: r.cardinality() 3 sage: r = iet.RauzyDiagram('a b c d','d c b a') sage: r.cardinality() 7
-
RauzyDiagram.
complete
(p)¶ Completion of the Rauzy diagram.
Add to the Rauzy diagram all permutations that are obtained by successive operations defined by edge_types(). The permutation must be of the same type and the same length as the one used for the creation.
INPUT:
p
- a permutation of Interval exchange transformation
Rauzy diagram is the reunion of all permutations that could be obtained with successive rauzy moves. This function just use the functions __getitem__ and has_rauzy_move and rauzy_move which must be defined for child and their corresponding permutation types.
TEST:
sage: r = iet.RauzyDiagram('a b c','c b a') #indirect doctest sage: r = iet.RauzyDiagram('a b c','c b a',left_induction=True) #indirect doctest sage: r = iet.RauzyDiagram('a b c','c b a',symmetric=True) #indirect doctest sage: r = iet.RauzyDiagram('a b c','c b a',lr_inversion=True) #indirect doctest sage: r = iet.RauzyDiagram('a b c','c b a',tb_inversion=True) #indirect doctest
-
RauzyDiagram.
edge_iterator
()¶ Returns an iterator over the edges of the graph.
EXAMPLES:
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: for e in r.edge_iterator(): ....: print(e[0].str(sep='/') + ' --> ' + e[1].str(sep='/')) a b/b a --> a b/b a a b/b a --> a b/b a
-
RauzyDiagram.
edge_to_loser
(p=None, edge_type=None)¶ Return the corresponding loser
TEST:
sage: r = iet.RauzyDiagram('a b','b a') sage: r.edge_to_loser(None,None) []
-
RauzyDiagram.
edge_to_matrix
(p=None, edge_type=None)¶ Return the corresponding matrix
INPUT:
p
- a permutationedge_type
- 0 or 1 corresponding to the type of the edge
OUTPUT:
A matrix
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: d = p.rauzy_diagram() sage: d.edge_to_matrix(p,1) [1 0 1] [0 1 0] [0 0 1]
-
RauzyDiagram.
edge_to_winner
(p=None, edge_type=None)¶ Return the corresponding winner
TEST:
sage: r = iet.RauzyDiagram('a b','b a') sage: r.edge_to_winner(None,None) []
-
RauzyDiagram.
edge_types
()¶ Print information about edges.
EXAMPLES:
sage: r = iet.RauzyDiagram('a b', 'b a') sage: r.edge_types() 0: rauzy_move(0, -1) 1: rauzy_move(1, -1)
sage: r = iet.RauzyDiagram('a b', 'b a', left_induction=True) sage: r.edge_types() 0: rauzy_move(0, -1) 1: rauzy_move(1, -1) 2: rauzy_move(0, 0) 3: rauzy_move(1, 0)
sage: r = iet.RauzyDiagram('a b',' b a',symmetric=True) sage: r.edge_types() 0: rauzy_move(0, -1) 1: rauzy_move(1, -1) 2: symmetric()
-
RauzyDiagram.
edge_types_index
(data)¶ Try to convert the data as an edge type.
INPUT:
data
- a string
OUTPUT:
integer
EXAMPLES:
For a standard Rauzy diagram (only right induction) the 0 index corresponds to the ‘top’ induction and the index 1 corresponds to the ‘bottom’ one:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: r.edge_types_index('top') 0 sage: r[p][0] == p.rauzy_move('top') True sage: r.edge_types_index('bottom') 1 sage: r[p][1] == p.rauzy_move('bottom') True
The special operations (inversion and symmetry) always appears after the different Rauzy inductions:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram(symmetric=True) sage: r.edge_types_index('symmetric') 2 sage: r[p][2] == p.symmetric() True
This function always try to resolve conflictuous name. If it’s impossible a ValueError is raised:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram(left_induction=True) sage: r.edge_types_index('top') Traceback (most recent call last): ... ValueError: left and right inductions must be differentiated sage: r.edge_types_index('top_right') 0 sage: r[p][0] == p.rauzy_move(0) True sage: r.edge_types_index('bottom_left') 3 sage: r[p][3] == p.rauzy_move('bottom', 'left') True
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram(left_right_inversion=True,top_bottom_inversion=True) sage: r.edge_types_index('inversion') Traceback (most recent call last): ... ValueError: left-right and top-bottom inversions must be differentiated sage: r.edge_types_index('lr_inverse') 2 sage: p.lr_inverse() == r[p][2] True sage: r.edge_types_index('tb_inverse') 3 sage: p.tb_inverse() == r[p][3] True
Short names are accepted:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram(right_induction='top',top_bottom_inversion=True) sage: r.edge_types_index('top_rauzy_move') 0 sage: r.edge_types_index('t') 0 sage: r.edge_types_index('tb') 1 sage: r.edge_types_index('inversion') 1 sage: r.edge_types_index('inverse') 1 sage: r.edge_types_index('i') 1
-
RauzyDiagram.
edges
(labels=True)¶ Returns a list of the edges.
EXAMPLES:
sage: r = iet.RauzyDiagram('a b','b a') sage: len(r.edges()) 2
-
RauzyDiagram.
graph
()¶ Returns the Rauzy diagram as a Graph object
The graph returned is more precisely a DiGraph (directed graph) with loops and multiedges allowed.
EXAMPLES:
sage: r = iet.RauzyDiagram('a b c','c b a') sage: r Rauzy diagram with 3 permutations sage: r.graph() Looped multi-digraph on 3 vertices
-
RauzyDiagram.
letters
()¶ Returns the letters used by the RauzyDiagram.
EXAMPLES:
sage: r = iet.RauzyDiagram('a b','b a') sage: r.alphabet() {'a', 'b'} sage: r.letters() ['a', 'b'] sage: r.alphabet('ABCDEF') sage: r.alphabet() {'A', 'B', 'C', 'D', 'E', 'F'} sage: r.letters() ['A', 'B']
-
RauzyDiagram.
path
(*data)¶ Returns a path over this Rauzy diagram.
INPUT:
initial_vertex
- the initial vertex (starting point of the path)data
- a sequence of edges
EXAMPLES:
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p, 'top', 'bottom')
-
RauzyDiagram.
vertex_iterator
()¶ Returns an iterator over the vertices
EXAMPLES:
sage: r = iet.RauzyDiagram('a b','b a') sage: for p in r.vertex_iterator(): print(p) a b b a
sage: r = iet.RauzyDiagram('a b c d','d c b a') sage: from six.moves import filter sage: r_1n = filter(lambda x: x.is_cylindric(), r) sage: for p in r_1n: print(p) a b c d d c b a
-
RauzyDiagram.
vertices
()¶ Returns a list of the vertices.
EXAMPLES:
sage: r = iet.RauzyDiagram('a b','b a') sage: for p in r.vertices(): print(p) a b b a
-
sage.dynamics.interval_exchanges.template.
interval_conversion
(interval=None)¶ Converts the argument in 0 or 1.
INPUT:
winner
- ‘top’ (or ‘t’ or 0) or bottom (or ‘b’ or 1)
OUTPUT:
integer – 0 or 1
TESTS:
sage: from sage.dynamics.interval_exchanges.template import interval_conversion sage: interval_conversion('top') 0 sage: interval_conversion('t') 0 sage: interval_conversion(0) 0 sage: interval_conversion('bottom') 1 sage: interval_conversion('b') 1 sage: interval_conversion(1) 1
-
sage.dynamics.interval_exchanges.template.
labelize_flip
(couple)¶ Returns a string from a 2-uple couple of the form (name, flip).
TESTS:
sage: from sage.dynamics.interval_exchanges.template import labelize_flip sage: labelize_flip((0,1)) ' 0' sage: labelize_flip((0,-1)) '-0'
-
sage.dynamics.interval_exchanges.template.
side_conversion
(side=None)¶ Converts the argument in 0 or -1.
INPUT:
side
- either ‘left’ (or ‘l’ or 0) or ‘right’ (or ‘r’ or -1)
OUTPUT:
integer – 0 or -1
TESTS:
sage: from sage.dynamics.interval_exchanges.template import side_conversion sage: side_conversion('left') 0 sage: side_conversion('l') 0 sage: side_conversion(0) 0 sage: side_conversion('right') -1 sage: side_conversion('r') -1 sage: side_conversion(1) -1 sage: side_conversion(-1) -1
-
sage.dynamics.interval_exchanges.template.
twin_list_iet
(a=None)¶ Returns the twin list of intervals.
The twin intervals is the correspondance between positions of labels in such way that a[interval][position] is a[1-interval][twin[interval][position]]
INPUT:
a
- two lists of labels
OUTPUT:
list – a list of two lists of integers
TESTS:
sage: from sage.dynamics.interval_exchanges.template import twin_list_iet sage: twin_list_iet([['a','b','c'],['a','b','c']]) [[0, 1, 2], [0, 1, 2]] sage: twin_list_iet([['a','b','c'],['a','c','b']]) [[0, 2, 1], [0, 2, 1]] sage: twin_list_iet([['a','b','c'],['b','a','c']]) [[1, 0, 2], [1, 0, 2]] sage: twin_list_iet([['a','b','c'],['b','c','a']]) [[2, 0, 1], [1, 2, 0]] sage: twin_list_iet([['a','b','c'],['c','a','b']]) [[1, 2, 0], [2, 0, 1]] sage: twin_list_iet([['a','b','c'],['c','b','a']]) [[2, 1, 0], [2, 1, 0]]
-
sage.dynamics.interval_exchanges.template.
twin_list_li
(a=None)¶ Returns the twin list of intervals
INPUT:
a
- two lists of labels
OUTPUT:
list – a list of two lists of couples of integers
TESTS:
sage: from sage.dynamics.interval_exchanges.template import twin_list_li sage: twin_list_li([['a','a','b','b'],[]]) [[(0, 1), (0, 0), (0, 3), (0, 2)], []] sage: twin_list_li([['a','a','b'],['b']]) [[(0, 1), (0, 0), (1, 0)], [(0, 2)]] sage: twin_list_li([['a','a'],['b','b']]) [[(0, 1), (0, 0)], [(1, 1), (1, 0)]] sage: twin_list_li([['a'], ['a','b','b']]) [[(1, 0)], [(0, 0), (1, 2), (1, 1)]] sage: twin_list_li([[], ['a','a','b','b']]) [[], [(1, 1), (1, 0), (1, 3), (1, 2)]]