Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Permutations template
.. 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/
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) """ #***************************************************************************** # Copyright (C) 2008 Vincent Delecroix <20100.delecroix@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #*****************************************************************************
r""" 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
.. Non admissible strings raise a ValueError::
sage: interval_conversion('') Traceback (most recent call last): ... ValueError: the interval can not be the empty string sage: interval_conversion('right') Traceback (most recent call last): ... ValueError: 'right' can not be converted to interval sage: interval_conversion('top_right') Traceback (most recent call last): ... ValueError: 'top_right' can not be converted to interval """ raise ValueError("interval must be 0 or 1")
raise TypeError("'%s' is not an admissible type" % (str(interval)))
r""" 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
.. Non admissible strings raise a ValueError::
sage: side_conversion('') Traceback (most recent call last): ... ValueError: no empty string for side sage: side_conversion('top') Traceback (most recent call last): ... ValueError: 'top' can not be converted to a side """
raise ValueError("side must be 0 or 1")
raise TypeError("'%s' is not an admissible type" % (str(side)))
r""" 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]] """
r""" 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)]] """
[(0,j) for j in range(len(a[0]))], [(1,j) for j in range(len(a[1]))]]
# two up or two down else : # one up, one down (here i=0)
r""" Template for all permutations.
.. WARNING::
Internal class! Do not use directly!
This class implement generic algorithm (stratum, connected component, ...) and unfies all its children. """ r""" Representation method of self.
Apply the function str to _repr_type(_repr_options) if _repr_type is callable and _repr_type else.
TESTS:
::
sage: p = iet.Permutation('a b c','c b a') doctest:warning ... DeprecationWarning: Permutation is deprecated and will be removed from Sage. You are advised to install the surface_dynamics package via: sage -pip install surface_dynamics If you do not have write access to the Sage installation you can alternatively do sage -pip install surface_dynamics --user The package surface_dynamics subsumes all flat surface related computation that are currently available in Sage. See more information at http://www.labri.fr/perso/vdelecro/surface-dynamics/latest/ See http://trac.sagemath.org/20695 for details. sage: p._repr_type = 'str' sage: p._repr_options = ('\n',) sage: p #indirect doctest a b c c b a sage: p._repr_options = (' / ',) sage: p #indirect doctest a b c / c b a
::
sage: p._repr_type = 'separatrix_diagram' sage: p._repr_options = (False,) sage: p #indirect doctest [[('c', 'a'), 'b'], ['b', ('c', 'a')]] sage: p._repr_options = (True,) sage: p [[(('c', 'a'), 'L'), ('b', 'R')], [('b', 'L'), (('c', 'a'), 'R')]]
::
sage: p._repr_type = '_twin' sage: p #indirect doctest [[2, 1, 0], [2, 1, 0]] """ return ''
return ''.join(map(str, self[1]))
else: else:
r""" 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') doctest:warning ... DeprecationWarning: GeneralizedPermutation is deprecated and will be removed from Sage. You are advised to install the surface_dynamics package via: sage -pip install surface_dynamics If you do not have write access to the Sage installation you can alternatively do sage -pip install surface_dynamics --user The package surface_dynamics subsumes all flat surface related computation that are currently available in Sage. See more information at http://www.labri.fr/perso/vdelecro/surface-dynamics/latest/ See http://trac.sagemath.org/20695 for details. 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
"""
r""" Sets the alphabet of self.
TESTS:
sage: p = iet.GeneralizedPermutation('a a','b b') sage: p.alphabet([0,1]) #indirect doctest sage: p.alphabet() == Alphabet([0,1]) True sage: p 0 0 1 1 sage: p.alphabet("cd") #indirect doctest sage: p.alphabet() == Alphabet(['c','d']) True sage: p c c d d
Tests with reduced permutations::
sage: p = iet.Permutation('a b','b a',reduced=True) sage: p.alphabet([0,1]) #indirect doctest sage: p.alphabet() == Alphabet([0,1]) True sage: p 0 1 1 0 sage: p.alphabet("cd") #indirect doctest sage: p.alphabet() == Alphabet(['c','d']) True sage: p c d d c
::
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) sage: p.alphabet([0,1]) #indirect doctest sage: p.alphabet() == Alphabet([0,1]) True sage: p 0 0 1 1 sage: p.alphabet("cd") #indirect doctest sage: p.alphabet() == Alphabet(['c','d']) True sage: p c c d d """ raise ValueError("Your alphabet has not enough letters")
r""" 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 """ else:
r""" 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] """
r""" 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 """
r""" 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 """
r""" 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
"""
r""" Tests the legality of a Rauzy move.
INPUT:
- ``winner`` - 'top' or 'bottom' corresponding to the interval
- ``side`` - '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 """
elif side == 0: return self.lr_inverse().has_right_rauzy_move(winner)
r""" Returns the permutation after a Rauzy move.
INPUT:
- ``winner`` - 'top' or 'bottom' interval
- ``side`` - '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 """
elif side == 0: tmp = self for k in range(iteration): tmp = tmp.left_rauzy_move(winner) return tmp
""" Template for permutation from Interval Exchange Transformation.
.. WARNING::
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version """ r""" Initializes the alphabet from intervals.
TESTS::
sage: p = iet.Permutation('a b c d','d c a b') #indirect doctest sage: p.alphabet() == Alphabet(['a', 'b', 'c', 'd']) True sage: p = iet.Permutation([0,1,2],[1,0,2],reduced=True) #indirect doctest sage: p.alphabet() == Alphabet([0,1,2]) True """
r""" 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 """
r""" 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 """
r""" Returns the intersection matrix.
This `d*d` antisymmetric matrix is given by the rule :
.. MATH::
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}
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] """
r""" 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 """
r""" 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 """
r""" 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 singularitites
EXAMPLES:
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) """
r""" 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']] """
else:
else: else:
singularities.append(singularity) break
else: else:
else: else:
else:
r""" 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() doctest:warning ... DeprecationWarning: AbelianStratum is deprecated and will be removed from Sage. You are advised to install the surface_dynamics package via: sage -pip install surface_dynamics If you do not have write access to the Sage installation you can alternatively do sage -pip install surface_dynamics --user The package surface_dynamics subsumes all flat surface related computation that are currently available in Sage. See more information at http://www.labri.fr/perso/vdelecro/surface-dynamics/latest/ See http://trac.sagemath.org/20695 for details. 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) """
return [x.stratum(marked_separatrix) for x in self.decompose()]
return AbelianStratum([])
r""" 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 """
r""" 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 """
r""" 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 """ OddCCA, EvenCCA)
return [x.connected_component(marked_separatrix) for x in self.decompose()]
else:
return cc[0](stratum)
else: else:
r""" 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 """
r""" 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 """
return res
letter = t[1][0] else:
r""" 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) """
r""" Returns a permutation in the Rauzy class such that
twin[0][-1] == 0 twin[1][-1] == 0
TESTS::
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 """
else: k_min = min(tmp._twin[0][a1+1:]) k = n - tmp._twin[0].index(k_min) - 1
tmp = tmp.rauzy_move(1, iteration=k)
else:
r""" 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 """
r""" 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 """
r""" Template for quadratic permutation.
.. WARNING::
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version """ r""" Initialization of the twin data.
TESTS::
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) #indirect doctest sage: p._twin [[(0, 1), (0, 0)], [(1, 1), (1, 0)]] """ # creation of the twin self._twin = [[],[]] l = [[(0,j) for j in range(len(a[0]))],[(1,j) for j in range(len(a[1]))]] for i in range(2) : for j in range(len(l[i])) : if l[i][j] == (i,j) : if a[i][j] in a[i][j+1:] : # two up or two down j2 = (a[i][j+1:]).index(a[i][j]) + j + 1 l[i][j] = (i,j2) l[i][j2] = (i,j) else : # one up, one down (here i=0) j2 = a[1].index(a[i][j]) l[0][j] = (1,j2) l[1][j2] = (0,j)
self._twin[0] = l[0] self._twin[1] = l[1]
r""" Intialization procedure of the alphabet of self from intervals list
TESTS::
sage: p = iet.GeneralizedPermutation('a a','b b') #indirect doctest sage: p.alphabet() {'a', 'b'} """
r""" Test of reducibility
A quadratic (or generalized) permutation is *reducible* if there exists a decomposition
.. MATH::
A1 u B1 | ... | B1 u A2
A1 u B2 | ... | B2 u A2
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 [BL2008]_ 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) """
# testing two corners empty on the right (i12 = i22 = 0)
return False
# testing no corner empty but one or two on the left
return True, ()
r""" 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 """
# the same letter at the right-end (False) self._twin[0][-1][1] == self.length_bottom() - 1):
# the winner (or loser) letter is repeated on the other interval (True)
# the loser letters is the only letter repeated in # the loser interval (False)
r""" 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' """
r""" Template for flipped generalized permutations.
.. WARNING::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version """ r""" Initialize the flip list
TESTS:
sage: iet.Permutation('a b','b a',flips='a').flips() #indirect doctest ['a'] sage: iet.Permutation('a b','b a',flips='b').flips() #indirect doctest ['b'] sage: iet.Permutation('a b','b a',flips='ab').flips() #indirect doctest ['a', 'b']
::
sage: iet.GeneralizedPermutation('a a','b b',flips='a').flips() ['a'] sage: iet.GeneralizedPermutation('a a','b b',flips='b').flips() ['b'] sage: iet.GeneralizedPermutation('a a','b b',flips='ab').flips() ['a', 'b'] """
r""" 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 """ + sep + ' '.join(map(labelize_flip, l[1])))
r""" Template for flipped Abelian permutations.
.. WARNING::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version """ r""" Returns the list of flips.
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a',flips='ac') sage: p.flips() ['a', 'c'] """
r""" Template for flipped quadratic permutations.
.. WARNING::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version """ r""" 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'] """
r""" Template for Rauzy diagrams.
.. WARNING::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version """ # TODO: pickle problem of Path (it does not understand what is its parent)
r""" 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. """ r""" Constructor of the path.
TESTS::
sage: p = iet.Permutation('a b c', 'c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p, 0, 1, 0); g Path of length 3 in a Rauzy diagram
Check for :trac:`8388`::
sage: loads(dumps(g)) == g True """
raise ValueError("No empty data")
raise ValueError("Starting point not in this Rauzy diagram")
raise ValueError("indices must be integer between 0 and %d" % (n)) raise ValueError("Invalid path")
r""" Returns a representation of the path.
TESTS::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: r.path(p) #indirect doctest Path of length 0 in a Rauzy diagram sage: r.path(p,'top') #indirect doctest Path of length 1 in a Rauzy diagram sage: r.path(p,'bottom') #indirect doctest Path of length 1 in a Rauzy diagram """
r""" 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 """
r""" 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 """
r""" 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] """
r""" Tests equality
TESTS::
sage: p1 = iet.Permutation('a b','b a') sage: r1 = p1.rauzy_diagram() sage: p2 = p1.reduced() sage: r2 = p2.rauzy_diagram() sage: r1.path(p1,0,1) == r2.path(p2,0,1) False sage: r1.path(p1,0) == r1.path(p1,0) True sage: r1.path(p1,1) == r1.path(p1,0) False """ type(self) is type(other) and self._parent == other._parent and self._start == other._start and self._edge_types == other._edge_types)
r""" Tests inequality
TESTS::
sage: p1 = iet.Permutation('a b','b a') sage: r1 = p1.rauzy_diagram() sage: p2 = p1.reduced() sage: r2 = p2.rauzy_diagram() sage: r1.path(p1,0,1) != r2.path(p2,0,1) True sage: r1.path(p1,0) != r1.path(p1,0) False sage: r1.path(p1,1) != r1.path(p1,0) True """ type(self) is not type(other) or self._parent != other._parent or self._start != other._start or self._edge_types != other._edge_types)
r""" Returns a copy of the path.
TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g1 = r.path(p,0,1,0,0) sage: g2 = copy(g1) sage: g1 is g2 False """
r""" 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 """
else:
r""" 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 """
raise ValueError("Edge type not valid")
r""" Append an edge to the path without verification.
EXAMPLES::
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: r = p.rauzy_diagram()
.. try to add 1 with append::
sage: g = r.path(p) sage: r[p][1] is None True sage: g.append(1) Traceback (most recent call last): ... ValueError: 1 is not a valid edge
.. the same with fast append::
sage: g = r.path(p) sage: r[p][1] is None True sage: g._fast_append(1) """
r""" 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 """ raise ValueError("Not on the same Rauzy diagram")
raise ValueError("The end of the first path must the start of the second")
r""" Extension with no verification.
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: p0, p1 = r[p] sage: g = r.path(p) sage: g._fast_extend(r.path(p0)) sage: g Path of length 0 in a Rauzy diagram sage: g._fast_extend(r.path(p1)) sage: g Path of length 0 in a Rauzy diagram """
r""" Returns the length of the path.
TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: len(r.path(p)) 0 sage: len(r.path(p,0)) 1 sage: len(r.path(p,1)) 1 """
r""" TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p,'t','b') sage: g[0] == p True sage: g[1] == p.rauzy_move('t') True sage: g[2] == p.rauzy_move('t').rauzy_move('b') True sage: g[-1] == g[2] True sage: g[-2] == g[1] True sage: g[-3] == g[0] True """ raise IndexError("path index out of range")
r""" Concatenation of paths.
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: r.path(p) + r.path(p,'b') == r.path(p,'b') True sage: r.path(p,'b') + r.path(p) == r.path(p,'b') True sage: r.path(p,'t') + r.path(p,'b') == r.path(p,'t','b') True """ raise ValueError("The end of the first path is not the start of the second")
r""" Multiple of a loop.
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: l = r.path(p,'b') sage: l * 2 == r.path(p,'b','b') True sage: l * 3 == r.path(p,'b','b','b') True """ raise ValueError("Must be a loop to have multiple")
raise TypeError("The multiplier must be an integer")
raise ValueError("The multiplier must be non negative")
r""" 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 """
r""" 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'] """ self._parent.edge_to_winner, list.__add__)
r""" 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'] """ self._parent.edge_to_loser, list.__add__)
r""" Iterator over the permutations of the path.
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: g = r.path(p) sage: for q in g: ....: print(p) a b c c b a sage: g = r.path(p, 't', 't') sage: for q in g: ....: print(q) ....: print("*****") a b c c b a ***** a b c c a b ***** a b c c b a ***** sage: g = r.path(p,'b','t') sage: for q in g: ....: print(q) ....: print("*****") a b c c b a ***** a c b c b a ***** a c b c b a ***** """
r""" Compose an edges function on a path
INPUT:
- ``path`` - either a Path or a tuple describing a path
- ``function`` - function must be of the form
- ``composition`` - 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] """
r""" 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)
TESTS::
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] """
right_induction=True, left_induction=False, left_right_inversion=False, top_bottom_inversion=False, symmetric=False): r""" - ``self._succ`` contains successors
- ``self._pred`` contains predecessors
- ``self._element_class`` is the class of elements of ``self``
- ``self._element`` is an instance of this class (hence contains the alphabet, the representation mode, ...). It is used to store data about property of permutations and also as a fast iterator.
INPUT:
- ``right_induction`` - boolean or 'top' or 'bottom': consider the right induction
- ``left_induction`` - boolean or 'top' or 'bottom': consider the left induction
- ``left_right_inversion`` - consider the left right inversion
- ``top_bottom_inversion`` - consider the top bottom inversion
- ``symmetric`` - consider the symmetric
TESTS::
sage: r1 = iet.RauzyDiagram('a b','b a') doctest:warning ... DeprecationWarning: RauzyDiagram is deprecated and will be removed from Sage. You are advised to install the surface_dynamics package via: sage -pip install surface_dynamics If you do not have write access to the Sage installation you can alternatively do sage -pip install surface_dynamics --user The package surface_dynamics subsumes all flat surface related computation that are currently available in Sage. See more information at http://www.labri.fr/perso/vdelecro/surface-dynamics/latest/ See http://trac.sagemath.org/20695 for details. sage: r2 = loads(dumps(r1)) """
raise ValueError("right_induction can not be empty string")
elif 'bottom'.startswith(right_induction): self._index['rb_rauzy'] = len(self._edge_types) self._edge_types.append(('rauzy_move',(1,-1)))
else: raise ValueError("%s is not valid for right_induction" % (right_induction))
if left_induction == '': raise ValueError("left_induction can not be empty string")
elif 'top'.startswith(left_induction): self._index['lt_rauzy'] = len(self._edge_types) self._edge_types.append(('rauzy_move', (0,0)))
elif 'bottom'.startswith(left_induction): self._index['lb_rauzy'] = len(self._edge_types) self._edge_types.append(('rauzy_move', (1,0)))
else: raise ValueError("%s is not valid for left_induction" % (right_induction))
r""" Tests equality.
TESTS:
::
sage: iet.RauzyDiagram('a b','b a') == iet.RauzyDiagram('a b c','c b a') False sage: r = iet.RauzyDiagram('a b c','c b a') sage: r1 = iet.RauzyDiagram('a c b','c b a', alphabet='abc') sage: r2 = iet.RauzyDiagram('a b c','c a b', alphabet='abc') sage: r == r1 True sage: r == r2 True sage: r1 == r2 True
::
sage: r = iet.RauzyDiagram('a b c d','d c b a') sage: for p in r: ....: p.rauzy_diagram() == r True True True True True True True """ type(self) is type(other) and self._edge_types == other._edge_types and next(iter(self._succ.keys())) in other._succ)
r""" Tests difference.
TESTS::
sage: iet.RauzyDiagram('a b','b a') != iet.RauzyDiagram('a b c','c b a') True sage: r = iet.RauzyDiagram('a b c','c b a') sage: r1 = iet.RauzyDiagram('a c b','c b a', alphabet='abc') sage: r2 = iet.RauzyDiagram('a b c','c a b', alphabet='abc') sage: r != r1 False sage: r != r2 False sage: r1 != r2 False """ type(self) is not type(other) or self._edge_types != other._edge_types or next(iter(self._succ.keys())) not in other._succ)
r""" 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 """
r""" 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 """
r""" Returns a list of the edges.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a') sage: len(r.edges()) 2 """
r""" 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 """ (self._vertex_to_permutation(x), self._vertex_to_permutation(y), i))
r""" 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 """ raise ValueError("the edge type must be a string")
"be differentiated") return self._index['lt_rauzy']
raise ValueError("no top induction in this Rauzy diagram")
'b_rauzy_move'.startswith(data)): if 'rb_rauzy' in self._index: raise ValueError("left and right inductions must " "be differentiated") return self._index['lb_rauzy']
raise ValueError("no bottom Rauzy induction in this diagram")
'l_rauzy_move'.startswith(data)): if 'lt_rauzy' in self._index: if 'lb_rauzy' in self._index: raise ValueError("top and bottom inductions must be differentiated") return self._index['lt_rauzy']
if 'lb_rauzy' in self._index: return self._index('lb_rauzy')
raise ValueError("no left Rauzy induction in this diagram")
'tl_rauzy_move'.startswith(data) or 'left_top_rauzy_move'.startswith(data) or 'top_left_rauzy_move'.startswith(data)): if not 'lt_rauzy' in self._index: raise ValueError("no top-left Rauzy induction in this diagram") else: return self._index['lt_rauzy']
'bl_rauzy_move'.startswith(data) or 'left_bottom_rauzy_move'.startswith(data) or 'bottom_left_rauzy_move'.startswith(data)): raise ValueError("no bottom-left Rauzy induction in this diagram") else:
raise ValueError("ambiguity with your edge name: %s" % (data))
'tr_rauzy_move'.startswith(data) or 'right_top_rauzy_move'.startswith(data) or 'top_right_rauzy_move'.startswith(data)): raise ValueError("no top-right Rauzy induction in this diagram") else:
'br_rauzy_move'.startswith(data) or 'right_bottom_rauzy_move'.startswith(data) or 'bottom_right_rauzy_move'.startswith(data)): if not 'rb_rauzy' in self._index: raise ValueError("no bottom-right Rauzy induction in this diagram") else: return self._index['rb_rauzy']
raise ValueError("no symmetric in this diagram") else:
return self._index['lr_inverse']
raise ValueError("no inversion in this diagram")
data == 'lr_inverse' or 'left_right_inversion'.startswith(data) or data == 'left_right_inverse'): raise ValueError("no left-right inversion in this diagram") else:
data == 'tb_inverse' or 'top_bottom_inversion'.startswith(data) or data == 'top_bottom_inverse'): raise ValueError("no top-bottom inversion in this diagram") else:
raise ValueError("this edge type does not exist: %s" % (data))
r""" 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() """
r""" 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 """ else:
r""" 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'] """
r""" Converts the (vertex) data to a permutation.
TESTS:
sage: r = iet.RauzyDiagram('a b','b a') #indirect doctest """
r""" Return the corresponding matrix
INPUT:
- ``p`` - a permutation
- ``edge_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] """
return identity_matrix(self._n)
r""" Return the corresponding winner
TESTS::
sage: r = iet.RauzyDiagram('a b','b a') sage: r.edge_to_winner(None,None) [] """
return [None]
r""" Return the corresponding loser
TESTS::
sage: r = iet.RauzyDiagram('a b','b a') sage: r.edge_to_loser(None,None) [] """
return [None]
r""" Returns an iterator over all extension of fixed length of p.
INPUT:
- ``p`` - a path
- ``length`` - a non-negative integer
TESTS:
::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: g0 = r.path(p) sage: for g in r._all_npath_extension(g0,0): ....: print(g) Path of length 0 in a Rauzy diagram sage: for g in r._all_npath_extension(g0,1): ....: print(g) Path of length 1 in a Rauzy diagram Path of length 1 in a Rauzy diagram sage: for g in r._all_npath_extension(g0,2): ....: print(g) Path of length 2 in a Rauzy diagram Path of length 2 in a Rauzy diagram Path of length 2 in a Rauzy diagram Path of length 2 in a Rauzy diagram
::
sage: p = iet.GeneralizedPermutation('a a','b b c c',reduced=True) sage: r = p.rauzy_diagram() sage: g0 = r.path(p) sage: len(list(r._all_npath_extension(g0,0))) 1 sage: len(list(r._all_npath_extension(g0,1))) 1 sage: len(list(r._all_npath_extension(g0,2))) 2 sage: len(list(r._all_npath_extension(g0,3))) 3 sage: len(list(r._all_npath_extension(g0,4))) 5 """
else:
r""" Returns an iterator over all path extension of p.
TESTS:
::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: g0 = r.path(p) sage: for g in r._all_path_extension(g0,0): ....: print(g) Path of length 0 in a Rauzy diagram sage: for g in r._all_path_extension(g0, 1): ....: print(g) Path of length 0 in a Rauzy diagram Path of length 1 in a Rauzy diagram Path of length 1 in a Rauzy diagram
::
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: r = p.rauzy_diagram() sage: g0 = r.path(p) sage: len(list(r._all_path_extension(g0,0))) 1 sage: len(list(r._all_path_extension(g0,1))) 2 sage: len(list(r._all_path_extension(g0,2))) 4 sage: len(list(r._all_path_extension(g0,3))) 7 """
r""" Iterator over the permutations of the Rauzy diagram.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a') sage: for p in r: print(p) a b b a sage: r = iet.RauzyDiagram('a b c','c b a') sage: for p in r: print(p.stratum()) H(0, 0) H(0, 0) H(0, 0) """
r""" Containance test.
TESTS::
sage: p = iet.Permutation('a b c d','d c b a',reduced=True) sage: q = iet.Permutation('a b c d','d b c a',reduced=True) sage: r = p.rauzy_diagram() sage: s = q.rauzy_diagram() sage: p in r True sage: p in s False sage: q in r False sage: q in s True """
r""" Returns a representation of self
TESTS::
sage: iet.RauzyDiagram('a b','b a') #indirect doctest Rauzy diagram with 1 permutation sage: iet.RauzyDiagram('a b c','c b a') #indirect doctest Rauzy diagram with 3 permutations """ return "Empty Rauzy diagram" else:
r""" Returns the neighbors of p.
Just use the function vertex_to_permutation that must be defined in each child.
INPUT:
- ``p`` - a permutation in the Rauzy diagram
TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: p0 = iet.Permutation('a b c','c a b',alphabet="abc") sage: p1 = iet.Permutation('a c b','c b a',alphabet="abc") sage: r = p.rauzy_diagram() sage: r[p] == [p0, p1] True sage: r[p1] == [p1, p] True sage: r[p0] == [p, p0] True """ raise ValueError("Your element does not have the good type")
r""" Deprecated use cardinality.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a') sage: r.cardinality() 1 """ return self.cardinality()
r""" 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 """
r""" 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.
TESTS::
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 """ raise ValueError("your permutation is not of good type")
raise ValueError("your permutation has not the good length")
getattr(perm, 'has_'+edge[0])(*(edge[1]))):
r""" 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') """ raise TypeError("Must be non empty") return copy(data[0])
r""" 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
"""
r""" Template for flipped Rauzy diagrams.
.. WARNING::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2009-09-29): initial version """ r""" 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 permutation
- ``reducible`` - 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 """ raise ValueError("your permutation is not of good type")
raise ValueError("your permutation has not the good length")
getattr(perm, 'has_' + edge_type[0])(*(edge_type[1]))):
|