Coverage for local/lib/python2.7/site-packages/sage/dynamics/interval_exchanges/constructors.py : 85%
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""" Class factories for Interval exchange transformations.
.. 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 library is designed for the usage and manipulation of interval exchange transformations and linear involutions. It defines specialized types of permutation (constructed using :meth:`iet.Permutation`) some associated graph (constructed using :meth:`iet.RauzyGraph`) and some maps of intervals (constructed using :meth:`iet.IntervalExchangeTransformation`).
EXAMPLES:
Creation of an interval exchange transformation::
sage: T = iet.IntervalExchangeTransformation(('a b','b a'),(sqrt(2),1)) doctest:warning ... DeprecationWarning: IntervalExchangeTransformation 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. 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: T Interval exchange transformation of [0, sqrt(2) + 1[ with permutation a b b a
It can also be initialized using permutation (group theoretic ones)::
sage: p = Permutation([3,2,1]) sage: T = iet.IntervalExchangeTransformation(p, [1/3,2/3,1]) sage: T Interval exchange transformation of [0, 2[ with permutation 1 2 3 3 2 1
For the manipulation of permutations of iet, there are special types provided by this module. All of them can be constructed using the constructor iet.Permutation. For the creation of labelled permutations of interval exchange transformation::
sage: p1 = iet.Permutation('a b c', 'c b a') sage: p1 a b c c b a
They can be used for initialization of an iet::
sage: p = iet.Permutation('a b','b a') sage: T = iet.IntervalExchangeTransformation(p, [1,sqrt(2)]) sage: T Interval exchange transformation of [0, sqrt(2) + 1[ with permutation a b b a
You can also, create labelled permutations of linear involutions::
sage: p = iet.GeneralizedPermutation('a a b', 'b c c') 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 a a b b c c
Sometimes it's more easy to deal with reduced permutations::
sage: p = iet.Permutation('a b c', 'c b a', reduced = True) sage: p a b c c b a
Permutations with flips::
sage: p1 = iet.Permutation('a b c', 'c b a', flips = ['a','c']) sage: p1 -a b -c -c b -a
Creation of Rauzy diagrams::
sage: r = iet.RauzyDiagram('a b c', 'c 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.
Reduced Rauzy diagrams are constructed using the same arguments than for permutations::
sage: r = iet.RauzyDiagram('a b b','c c a') sage: r_red = iet.RauzyDiagram('a b b','c c a',reduced=True) sage: r.cardinality() 12 sage: r_red.cardinality() 4
By default, Rauzy diagrams are generated by induction on the right. You can use several options to enlarge (or restrict) the diagram (try help(iet.RauzyDiagram) for more precisions)::
sage: r1 = iet.RauzyDiagram('a b c','c b a',right_induction=True) sage: r2 = iet.RauzyDiagram('a b c','c b a',left_right_inversion=True)
You can consider self similar iet using path in Rauzy diagrams and eigenvectors of the corresponding matrix::
sage: p = iet.Permutation("a b c d", "d c b a") sage: d = p.rauzy_diagram() sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b') sage: g Path of length 8 in a Rauzy diagram sage: g.is_loop() True sage: g.is_full() True sage: m = g.matrix() sage: v = m.eigenvectors_right()[-1][1][0] sage: T1 = iet.IntervalExchangeTransformation(p, v) sage: T2 = T1.rauzy_move(iterations=8) sage: T1.normalize(1) == T2.normalize(1) True
REFERENCES:
- [BL2008]_
- [DN1990]_
- [Nog1985]_
- [Rau1979]_
- [Vee1978]_
- [Zor]_
AUTHORS:
- Vincent Delecroix (2009-09-29): initial version
""" #***************************************************************************** # 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""" Try to return the input as a list of two lists
INPUT:
- ``a`` - either a string, one or two lists, one or two tuples
OUTPUT:
-- two lists
TESTS::
sage: from sage.dynamics.interval_exchanges.constructors import _two_lists sage: _two_lists(('a1 a2','b1 b2')) [['a1', 'a2'], ['b1', 'b2']] sage: _two_lists('a1 a2\nb1 b2') [['a1', 'a2'], ['b1', 'b2']] sage: _two_lists(['a b','c']) [['a', 'b'], ['c']]
..The ValueError and TypeError can be raised if it fails::
sage: _two_lists('a b') Traceback (most recent call last): ... ValueError: your chain must contain two lines sage: _two_lists('a b\nc d\ne f') Traceback (most recent call last): ... ValueError: your chain must contain two lines sage: _two_lists(1) Traceback (most recent call last): ... TypeError: argument not accepted sage: _two_lists([1,2,3]) Traceback (most recent call last): ... ValueError: your argument can not be split in two parts """
else :
a = a[0] if isinstance(a, Permutation): res[0] = list(range(1,len(a)+1)) res[1] = [a[i] for i in range(len(a))]
elif isinstance(a, (list,tuple)): if (len(a) != 2): raise ValueError("your list must contain two objects") for i in range(2): if isinstance(a[i], str): res[i] = a[i].split() else: res[i] = list(a[i])
else : raise TypeError("argument not accepted")
else : else:
r""" Returns a permutation of an interval exchange transformation.
Those permutations are the combinatoric part of an interval exchange transformation (IET). The combinatorial study of those objects starts with Gerard Rauzy [Rau1979]_ and William Veech [Vee1978]_.
The combinatoric part of interval exchange transformation can be taken independently from its dynamical origin. It has an important link with strata of Abelian differential (see :mod:`~sage.dynamics.interval_exchanges.strata`)
INPUT:
- ``intervals`` - string, two strings, list, tuples that can be converted to two lists
- ``reduced`` - boolean (default: False) specifies reduction. False means labelled permutation and True means reduced permutation.
- ``flips`` - iterable (default: None) the letters which correspond to flipped intervals.
OUTPUT:
permutation -- the output type depends of the data.
EXAMPLES:
Creation of labelled permutations ::
sage: iet.Permutation('a b c d','d c b a') a b c d d c b a sage: iet.Permutation([[0,1,2,3],[2,1,3,0]]) 0 1 2 3 2 1 3 0 sage: iet.Permutation([0, 'A', 'B', 1], ['B', 0, 1, 'A']) 0 A B 1 B 0 1 A
Creation of reduced permutations::
sage: iet.Permutation('a b c', 'c b a', reduced = True) a b c c b a sage: iet.Permutation([0, 1, 2, 3], [1, 3, 0, 2]) 0 1 2 3 1 3 0 2
Creation of flipped permutations::
sage: iet.Permutation('a b c', 'c b a', flips=['a','b']) -a -b c c -b -a sage: iet.Permutation('a b c', 'c b a', flips=['a'], reduced=True) -a b c c b -a
TESTS:
::
sage: p = iet.Permutation('a b c','c b a') sage: iet.Permutation(p) == p True sage: iet.Permutation(p, reduced=True) == p.reduced() True
::
sage: p = iet.Permutation('a','a',flips='a',reduced=True) sage: iet.Permutation(p) == p True
::
sage: p = iet.Permutation('a b c','c b a',flips='a') sage: iet.Permutation(p) == p True sage: iet.Permutation(p, reduced=True) == p.reduced() True
::
sage: p = iet.Permutation('a b c','c b a',reduced=True) sage: iet.Permutation(p) == p True
sage: iet.Permutation('a b c','c b a',reduced='badly') Traceback (most recent call last): ... TypeError: reduced must be of type boolean sage: iet.Permutation('a','a',flips='b',reduced=True) Traceback (most recent call last): ... ValueError: flips contains not valid letters sage: iet.Permutation('a b c','c a a',reduced=True) Traceback (most recent call last): ... ValueError: letters must appear once in each interval """
else :
else :
else :
else: else: # conversion not yet implemented reduced = reduction in (None, False) return PermutationIET( args.list(), reduced=reduced, flips=flips, alphabet=alphabet)
else: # conversion not yet implemented return PermutationIET( args.list(), reduced=True) else: # conversion not yet implemented reduced = reduction in (None, True) return PermutationIET( args.list(), reduced=reduced, flips=flips, alphabet=alphabet)
else : else : else :
r""" Returns a permutation of an interval exchange transformation.
Those permutations are the combinatoric part of linear involutions and were introduced by Danthony-Nogueira [DN1990]_. The full combinatoric study and precise links with strata of quadratic differentials was achieved few years later by Boissy-Lanneau [BL2008]_.
INPUT:
- ``intervals`` - strings, list, tuples
- ``reduced`` - boolean (default: False) specifies reduction. False means labelled permutation and True means reduced permutation.
- ``flips`` - iterable (default: None) the letters which correspond to flipped intervals.
OUTPUT:
generalized permutation -- the output type depends on the data.
EXAMPLES:
Creation of labelled generalized permutations::
sage: iet.GeneralizedPermutation('a b b','c c a') a b b c c a sage: iet.GeneralizedPermutation('a a','b b c c') a a b b c c sage: iet.GeneralizedPermutation([[0,1,2,3,1],[4,2,5,3,5,4,0]]) 0 1 2 3 1 4 2 5 3 5 4 0
Creation of reduced generalized permutations::
sage: iet.GeneralizedPermutation('a b b', 'c c a', reduced = True) a b b c c a sage: iet.GeneralizedPermutation('a a b b', 'c c d d', reduced = True) a a b b c c d d
Creation of flipped generalized permutations::
sage: iet.GeneralizedPermutation('a b c a', 'd c d b', flips = ['a','b']) -a -b c -a d c d -b
TESTS::
sage: iet.GeneralizedPermutation('a a b b', 'c c d d', reduced = 'may') Traceback (most recent call last): ... TypeError: reduced must be of type boolean sage: iet.GeneralizedPermutation('a b c a', 'd c d b', flips = ['e','b']) Traceback (most recent call last): ... TypeError: The flip list is not valid sage: iet.GeneralizedPermutation('a b c a', 'd c c b', flips = ['a','b']) Traceback (most recent call last): ... ValueError: Letters must reappear twice """
else :
else :
else :
if flips == []: if reduction is None or not reduction: from copy import copy return copy(args) else: return args.reduced() else: # conversion not yet implemented reduced = reduction in (None, False) return PermutationLI( args.list(), reduced=reduced, flips=flips, alphabet=alphabet)
if flips == []: if reduction is None or reduction: from copy import copy return copy(args) else: # conversion not yet implemented return PermutationLI( args.list(), reduced=True) else: # conversion not yet implemented reduced = reduction in (None, True) return PermutationLI( args.list(), reduced=reduced, flips=flips, alphabet=alphabet)
raise TypeError("reduced must be of type boolean") else :
else :
else :
# check existence of admissible length
raise ValueError("There is no admissible length")
else : else : else :
reduced=False, alphabet=None): r""" Returns an iterator over permutations.
This iterator allows you to iterate over permutations with given constraints. If you want to iterate over permutations coming from a given stratum you have to use the module :mod:`~sage.dynamics.flat_surfaces.strata` and generate Rauzy diagrams from connected components.
INPUT:
- ``nintervals`` - non negative integer
- ``irreducible`` - boolean (default: True)
- ``reduced`` - boolean (default: False)
- ``alphabet`` - alphabet (default: None)
OUTPUT:
iterator -- an iterator over permutations
EXAMPLES:
Generates all reduced permutations with given number of intervals::
sage: P = iet.Permutations_iterator(nintervals=2,alphabet="ab",reduced=True) doctest:warning ... DeprecationWarning: iet_Permutations_iterator 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: for p in P: ....: print(p) ....: print("* *") a b b a * * sage: P = iet.Permutations_iterator(nintervals=3,alphabet="abc",reduced=True) sage: for p in P: ....: print(p) ....: print("* * *") a b c b c a * * * a b c c a b * * * a b c c b a * * *
TESTS::
sage: P = iet.Permutations_iterator(nintervals=None, alphabet=None) Traceback (most recent call last): ... ValueError: You must specify an alphabet or a length sage: P = iet.Permutations_iterator(nintervals=None, alphabet=ZZ) Traceback (most recent call last): ... ValueError: You must specify a length with infinite alphabet """
else: nintervals = alphabet.cardinality()
alphabet = list(range(1, nintervals + 1))
irreducible=irreducible, alphabet=alphabet) else: irreducible=irreducible, alphabet=alphabet)
r""" Return an object coding a Rauzy diagram.
The Rauzy diagram is an oriented graph with labelled edges. The set of vertices corresponds to the permutations obtained by different operations (mainly the .rauzy_move() operations that corresponds to an induction of interval exchange transformation). The edges correspond to the action of the different operations considered.
It first appeared in the original article of Rauzy [Rau1979]_.
INPUT:
- ``intervals`` - lists, or strings, or tuples
- ``reduced`` - boolean (default: False) to precise reduction
- ``flips`` - list (default: []) for flipped permutations
- ``right_induction`` - boolean (default: True) consideration of left induction in the diagram
- ``left_induction`` - boolean (default: False) consideration of right induction in the diagram
- ``left_right_inversion`` - boolean (default: False) consideration of inversion
- ``top_bottom_inversion`` - boolean (default: False) consideration of reversion
- ``symmetric`` - boolean (default: False) consideration of the symmetric operation
OUTPUT:
Rauzy diagram -- the Rauzy diagram that corresponds to your request
EXAMPLES:
Standard Rauzy diagrams::
sage: iet.RauzyDiagram('a b c d', 'd b c a') Rauzy diagram with 12 permutations sage: iet.RauzyDiagram('a b c d', 'd b c a', reduced = True) Rauzy diagram with 6 permutations
Extended Rauzy diagrams::
sage: iet.RauzyDiagram('a b c d', 'd b c a', symmetric=True) Rauzy diagram with 144 permutations
Using Rauzy diagrams and path in Rauzy diagrams::
sage: r = iet.RauzyDiagram('a b c', 'c b a') sage: r Rauzy diagram with 3 permutations sage: p = iet.Permutation('a b c','c b a') sage: p in r True sage: g0 = r.path(p, 'top', 'bottom','top') sage: g1 = r.path(p, 'bottom', 'top', 'bottom') sage: g0.is_loop(), g1.is_loop() (True, True) sage: g0.is_full(), g1.is_full() (False, False) sage: g = g0 + g1 sage: g Path of length 6 in a Rauzy diagram sage: g.is_loop(), g.is_full() (True, True) sage: m = g.matrix() sage: m [1 1 1] [2 4 1] [2 3 2] sage: s = g.orbit_substitution() sage: s WordMorphism: a->acbbc, b->acbbcbbc, c->acbc sage: s.incidence_matrix() == m True
We can then create the corresponding interval exchange transformation and comparing the orbit of `0` to the fixed point of the orbit substitution::
sage: v = m.eigenvectors_right()[-1][1][0] sage: T = iet.IntervalExchangeTransformation(p, v).normalize() sage: T Interval exchange transformation of [0, 1[ with permutation a b c c b a sage: w1 = [] sage: x = 0 sage: for i in range(20): ....: w1.append(T.in_which_interval(x)) ....: x = T(x) sage: w1 = Word(w1) sage: w1 word: acbbcacbcacbbcbbcacb sage: w2 = s.fixed_point('a') sage: w2[:20] word: acbbcacbcacbbcbbcacb sage: w2[:20] == w1 True """
args, reduced= kargs['reduced'], flips = kargs['flips'], alphabet = kargs['alphabet'])
right_induction = kargs['right_induction'], left_induction = kargs['left_induction'], left_right_inversion = kargs['left_right_inversion'], top_bottom_inversion = kargs['top_bottom_inversion'], symmetric = kargs['symmetric'])
#TODO # def GeneralizedPermutation_iterator():
""" Constructs an Interval exchange transformation.
An interval exchange transformation (or iet) is a map from an interval to itself. It is defined on the interval except at a finite number of points (the singularities) and is a translation on each connected component of the complement of the singularities. Moreover it is a bijection on its image (or it is injective).
An interval exchange transformation is encoded by two datas. A permutation (that corresponds to the way we echange the intervals) and a vector of positive reals (that corresponds to the lengths of the complement of the singularities).
INPUT:
- ``permutation`` - a permutation
- ``lengths`` - a list or a dictionary of lengths
OUTPUT:
interval exchange transformation -- an map of an interval
EXAMPLES:
Two initialization methods, the first using a iet.Permutation::
sage: p = iet.Permutation('a b c','c b a') sage: t = iet.IntervalExchangeTransformation(p, {'a':1,'b':0.4523,'c':2.8})
The second is more direct::
sage: t = iet.IntervalExchangeTransformation(('a b','b a'),{'a':1,'b':4})
It's also possible to initialize the lengths only with a list::
sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2])
The two fundamental operations are Rauzy move and normalization::
sage: t = iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,0.4,2]) sage: s = t.rauzy_move() sage: s_n = s.normalize(t.length()) sage: s_n.length() == t.length() True
A not too simple example of a self similar interval exchange transformation::
sage: p = iet.Permutation('a b c d','d c b a') sage: d = p.rauzy_diagram() sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b') sage: m = g.matrix() sage: v = m.eigenvectors_right()[-1][1][0] sage: t = iet.IntervalExchangeTransformation(p,v) sage: s = t.rauzy_move(iterations=8) sage: s.normalize() == t.normalize() True
TESTS::
sage: iet.IntervalExchangeTransformation(('a b c','c b a'),[0.123,2]) Traceback (most recent call last): ... ValueError: bad number of lengths sage: iet.IntervalExchangeTransformation(('a b c','c b a'),[0.1,'rho',2]) Traceback (most recent call last): ... TypeError: unable to convert 'rho' to a float sage: iet.IntervalExchangeTransformation(('a b c','c b a'),[0.1,-2,2]) Traceback (most recent call last): ... ValueError: lengths must be positive """
raise TypeError("flips are not yet implemented") else:
else:
#TODO # def LinearInvolution(*args,**kargs): # r""" # Constructs a Linear Involution from the given data # """ # from iet import LinearInvolution as _LI # pass
# LI = LinearInvolution |