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""" Labelled permutations
.. WARNING::
This module is deprecated. You are advised to install and use the surface_dynamics package instead available at https://pypi.python.org/pypi/surface_dynamics/
A labelled (generalized) permutation is better suited to study the dynamic of a translation surface than a reduced one (see the module :mod:`sage.dynamics.interval_exchanges.reduced`). The latter is more adapted to the study of strata. This kind of permutation was introduced by Yoccoz [Yoc2005]_ (see also [MMY2003]_).
In fact, there is a geometric counterpart of labelled permutations. They correspond to translation surfaces with marked outgoing separatrices (i.e. we fix a label for each of them).
Remarks that Rauzy diagram of reduced objects are significantly smaller than the one for labelled object (for the permutation a b d b e / e d c a c the labelled Rauzy diagram contains 8760 permutations, and the reduced only 73). But, as it is in geometrical way, the labelled Rauzy diagram is a covering of the reduced Rauzy diagram.
AUTHORS:
- Vincent Delecroix (2009-09-29) : initial version
TESTS::
sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationIET sage: LabelledPermutationIET([['a', 'b', 'c'], ['c', 'b', 'a']]) a b c c b a sage: LabelledPermutationIET([[1,2,3,4],[4,1,2,3]]) 1 2 3 4 4 1 2 3 sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationLI sage: LabelledPermutationLI([[1,1],[2,2,3,3,4,4]]) 1 1 2 2 3 3 4 4 sage: LabelledPermutationLI([['a','a','b','b','c','c'],['d','d']]) a a b b c c d d sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationIET sage: FlippedLabelledPermutationIET([[1,2,3],[3,2,1]],flips=[1,2]) -1 -2 3 3 -2 -1 sage: FlippedLabelledPermutationIET([['a','b','c'],['b','c','a']],flips='b') a -b c -b c a sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationLI sage: FlippedLabelledPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4]) -1 -1 2 2 3 3 -4 -4 sage: FlippedLabelledPermutationLI([['a','a','b','b'],['c','c']],flips='ac') -a -a b b -c -c sage: from sage.dynamics.interval_exchanges.labelled import LabelledRauzyDiagram sage: p = LabelledPermutationIET([[1,2,3],[3,2,1]]) sage: d1 = LabelledRauzyDiagram(p) sage: p = LabelledPermutationIET([['a','b'],['b','a']]) sage: d = p.rauzy_diagram() sage: g1 = d.path(p, 'top', 'bottom') sage: g1.matrix() [1 1] [1 2] sage: g2 = d.path(p, 'bottom', 'top') sage: g2.matrix() [2 1] [1 1] sage: p = LabelledPermutationIET([['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: s1 = g.orbit_substitution() sage: s1 WordMorphism: a->adbd, b->adbdbd, c->adccd, d->adcd sage: s2 = g.interval_substitution() sage: s2 WordMorphism: a->abcd, b->bab, c->cdc, d->dcbababcd sage: s1.incidence_matrix() == s2.incidence_matrix().transpose() True """ #***************************************************************************** # 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""" General template for labelled objects.
.. warning::
Internal class! Do not use directly! """ r""" TESTS::
sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationIET sage: p1 = LabelledPermutationIET([[1,2,3],[3,2,1]]) sage: p1 == loads(dumps(p1)) True sage: p2 = LabelledPermutationIET([['a', 'b', 'c'], ['c', 'b', 'a']]) sage: p2 == loads(dumps(p2)) True sage: p3 = LabelledPermutationIET([['1','2','3'],['3','2','1']]) sage: p3 == loads(dumps(p3)) True sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationLI sage: p1 = LabelledPermutationLI([[1,2,2],[3,3,1]]) sage: p1 == loads(dumps(p1)) True sage: p2 = LabelledPermutationLI([['a','b','b'],['c','c','a']]) sage: p2 == loads(dumps(p2)) True sage: p3 = LabelledPermutationLI([['1','2','2'],['3','3','1']]) sage: p3 == loads(dumps(p3)) True """
else: raise ValueError("the alphabet is too short")
else:
[self._alphabet.rank(_) for _ in intervals[0]], [self._alphabet.rank(_) for _ in intervals[1]]]
r""" Returns a copy of self.
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: q = copy(p) sage: p == q True sage: p is q False sage: p._inversed() sage: p == q False sage: p._inversed() sage: p == q True sage: p._reversed() sage: p == q False sage: q._reversed() sage: p == q True """
copy(self._intervals[0]), copy(self._intervals[1])]
r""" TESTS::
sage: len(iet.Permutation('','')) 0 sage: len(iet.Permutation('a','a')) 1 sage: len(iet.Permutation('1 2 3 4 5 6','1 2 3 4 5 6')) 6 """
r""" Returns the number of intervals in the top segment.
OUTPUT:
integer -- number of intervals
EXAMPLES::
sage: iet.Permutation('a b c','c b a').length_top() 3 sage: iet.GeneralizedPermutation('a a','b b c c').length_top() 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. 2 sage: iet.GeneralizedPermutation('a a b b','c c').length_top() 4 """
r""" Returns the number of intervals in the bottom segment.
OUTPUT:
integer -- number of intervals
EXAMPLES::
sage: iet.Permutation('a b','b a').length_bottom() 2 sage: iet.GeneralizedPermutation('a a','b b c c').length_bottom() 4 sage: iet.GeneralizedPermutation('a a b b','c c').length_bottom() 2 """
r""" Returns a 2-uple of lengths.
p.length() is identical to (p.length_top(), p.length_bottom()) If an interval is specified, it returns the length of the specified interval.
INPUT:
- ``interval`` - ``None``, 'top' or 'bottom'
OUTPUT:
tuple -- a 2-uple of integers
EXAMPLES::
sage: iet.Permutation('a b c','c b a').length() (3, 3) sage: iet.GeneralizedPermutation('a a','b b c c').length() (2, 4) sage: iet.GeneralizedPermutation('a a b b','c c').length() (4, 2) """ else:
r""" TESTS::
sage: p = iet.Permutation([0,1,2,3],[3,2,1,0]) sage: p[0][0] 0 sage: p[1][2] 1 sage: p = iet.Permutation('a b c','c b a') sage: p[0][1] 'b' sage: p[1][2] 'a' """
r""" ALGORITHM:
Uses the hash of string
TESTS::
sage: from sage.dynamics.interval_exchanges.labelled import * sage: p1 = LabelledPermutationIET([[1,2],[1,2]]) sage: p2 = LabelledPermutationIET([[1,2],[2,1]]) sage: p3 = LabelledPermutationLI([[1,1],[2,2]]) sage: hash(p1) == hash(p2) False sage: hash(p1) == hash(p3) False sage: hash(p2) == hash(p3) False sage: p1 = LabelledPermutationLI([[1,1], [2,2,3,3]]) sage: p2 = LabelledPermutationLI([[1,1,2], [2,3,3]]) sage: p3 = LabelledPermutationLI([[1,1,2,2], [3,3]]) sage: hash(p1) == hash(p2) False sage: hash(p1) == hash(p3) False sage: hash(p2) == hash(p3) False """
r""" .. TODO::
resolve properly the mutability problem with the :meth:`_twin` attribute.
TESTS::
sage: p = iet.Permutation([1,2,3],[3,1,2]) sage: p 1 2 3 3 1 2 sage: p._reversed() sage: p 3 2 1 2 1 3 """ del self.__dict__['_twin'] self._hash = None
r""" .. TODO::
properly resolve the mutability problem of the twin
TESTS::
sage: p = iet.Permutation([1,2,3],[3,1,2]) sage: p 1 2 3 3 1 2 sage: p._inversed() sage: p 3 1 2 1 2 3 """ del self.__dict__['_twin'] self._hash = None
r""" Returns a list of two lists corresponding to the intervals.
OUTPUT:
list -- two lists of labels
EXAMPLES:
The list of an permutation from iet::
sage: p1 = iet.Permutation('1 2 3', '3 1 2') sage: p1.list() [['1', '2', '3'], ['3', '1', '2']] sage: p1.alphabet("abc") sage: p1.list() [['a', 'b', 'c'], ['c', 'a', 'b']]
Recovering the permutation from this list (and the alphabet)::
sage: q1 = iet.Permutation(p1.list(),alphabet=p1.alphabet()) sage: p1 == q1 True
The list of a quadratic permutation::
sage: p2 = iet.GeneralizedPermutation('g o o', 'd d g') sage: p2.list() [['g', 'o', 'o'], ['d', 'd', 'g']]
Recovering the permutation::
sage: q2 = iet.GeneralizedPermutation(p2.list(),alphabet=p2.alphabet()) sage: p2 == q2 True """
r""" Return the permutation with the specified letter removed.
OUTPUT:
permutation -- the resulting permutation
EXAMPLES:
::
sage: p = iet.Permutation('a b c d','c d b a') sage: p.erase_letter('a') b c d c d b sage: p.erase_letter('b') a c d c d a sage: p.erase_letter('c') a b d d b a sage: p.erase_letter('d') a b c c b a
::
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.erase_letter('a') b b c c
Beware, there is no validity check for permutation from linear involutions::
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.erase_letter('b') a c c a """
r""" Returns the Rauzy move matrix.
This matrix corresponds to the action of a Rauzy move on the vector of lengths. By convention (to get a positive matrix), the matrix is defined as the inverse transformation on the length vector.
OUTPUT:
matrix -- a square matrix of positive integers
EXAMPLES:
::
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move_matrix('t') [1 0] [1 1] sage: p.rauzy_move_matrix('b') [1 1] [0 1]
::
sage: p = iet.Permutation('a b c d','b d a c') sage: q = p.left_right_inverse() sage: m0 = p.rauzy_move_matrix(winner='top',side='right') sage: n0 = q.rauzy_move_matrix(winner='top',side='left') sage: m0 == n0 True sage: m1 = p.rauzy_move_matrix(winner='bottom',side='right') sage: n1 = q.rauzy_move_matrix(winner='bottom',side='left') sage: m1 == n1 True """ return identity_matrix(len(self))
r""" Returns the winner of a Rauzy move.
INPUT:
- ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
- ``side`` - either 'left' or 'right' ('l' or 'r' for short)
OUTPUT:
-- a label
EXAMPLES:
::
sage: p = iet.Permutation('a b c d','b d a c') sage: p.rauzy_move_winner('top','right') 'd' sage: p.rauzy_move_winner('bottom','right') 'c' sage: p.rauzy_move_winner('top','left') 'a' sage: p.rauzy_move_winner('bottom','left') 'b'
::
sage: p = iet.GeneralizedPermutation('a b b c','d c a e d e') sage: p.rauzy_move_winner('top','right') 'c' sage: p.rauzy_move_winner('bottom','right') 'e' sage: p.rauzy_move_winner('top','left') 'a' sage: p.rauzy_move_winner('bottom','left') 'd' """ return None
r""" Returns the loser of a Rauzy move
INPUT:
- ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
- ``side`` - either 'left' or 'right' ('l' or 'r' for short)
OUTPUT:
-- a label
EXAMPLES::
sage: p = iet.Permutation('a b c d','b d a c') sage: p.rauzy_move_loser('top','right') 'c' sage: p.rauzy_move_loser('bottom','right') 'd' sage: p.rauzy_move_loser('top','left') 'b' sage: p.rauzy_move_loser('bottom','left') 'a' """ return None
irreducible=True, alphabet=None): r""" Returns an iterator over labelled permutations.
INPUT:
- ``nintervals`` - integer or ``None``
- ``irreducible`` - boolean (default: ``True``)
- ``alphabet`` - something that should be converted to an alphabet of at least nintervals letters
OUTPUT:
iterator -- an iterator over permutations
TESTS::
sage: for p in iet.Permutations_iterator(2, alphabet="ab"): ....: print(p) ....: print("****") #indirect doctest 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. a b b a **** b a a b **** sage: for p in iet.Permutations_iterator(3, alphabet="abc"): ....: print(p) ....: print("*****") #indirect doctest a b c b c a ***** a b c c a b ***** a b c c b a ***** a c b b a c ***** a c b b c a ***** a c b c b a ***** b a c a c b ***** b a c c a b ***** b a c c b a ***** b c a a b c ***** b c a a c b ***** b c a c a b ***** c a b a b c ***** c a b b a c ***** c a b b c a ***** c b a a b c ***** c b a a c b ***** c b a b a c ***** """
raise ValueError("choose a number of intervals")
raise ValueError("nintervals must be positive")
else: lambda x: x.is_irreducible(), LabelledPermutationsIET_iterator(nintervals,False,alphabet))
""" Labelled permutation for iet
EXAMPLES:
Reducibility testing::
sage: p = iet.Permutation('a b c', 'c b a') sage: p.is_irreducible() True
sage: q = iet.Permutation('a b c d', 'b a d c') sage: q.is_irreducible() False
Rauzy movability and Rauzy move::
sage: p = iet.Permutation('a b c', 'c b a') sage: p.has_rauzy_move('top') True sage: p.rauzy_move('bottom') a c b c b a sage: p.has_rauzy_move('top') True sage: p.rauzy_move('top') a b c c a b
Rauzy diagram::
sage: p = iet.Permutation('a b c', 'c b a') sage: d = p.rauzy_diagram() sage: p in d True """ r""" ALGORITHM:
The order is lexicographic on intervals[0] + intervals[1]
TESTS::
sage: list_of_p2 = [] sage: p0 = iet.Permutation('1 2', '1 2') sage: p1 = iet.Permutation('1 2', '2 1') sage: p0 != p0 False sage: (p0 == p0) and (p0 < p1) True sage: (p1 > p0) and (p1 == p1) True """ return -1
return n - len(other)
def _twin(self): r""" The twin relations of the permutation.
TESTS::
sage: p = iet.Permutation('a b','a b') sage: p._twin [[0, 1], [0, 1]] sage: p = iet.Permutation('a b','b a') sage: p._twin [[1, 0], [1, 0]] """
r""" Returns the associated reduced abelian permutation.
OUTPUT:
a reduced permutation -- the underlying reduced permutation
EXAMPLES::
sage: p = iet.Permutation("a b c d","d c a b") sage: q = iet.Permutation("a b c d","d c a b",reduced=True) sage: p.reduced() == q True """
r""" Returns True if self is the identity.
OUTPUT:
bool -- True if self corresponds to the identity
EXAMPLES::
sage: iet.Permutation("a b","a b").is_identity() True sage: iet.Permutation("a b","b a").is_identity() False """
r""" Returns ``True`` if you can perform a Rauzy move.
INPUT:
- ``winner`` - the winner interval ('top' or 'bottom')
- ``side`` - (default: 'right') the side ('left' or 'right')
OUTPUT:
bool -- ``True`` if self has a Rauzy move
EXAMPLES:
::
sage: p = iet.Permutation('a b','b a') sage: p.has_rauzy_move() True
::
sage: p = iet.Permutation('a b c','b a c') sage: p.has_rauzy_move() False """ else:
r""" Returns the Rauzy move.
INPUT:
- ``winner`` - the winner interval ('top' or 'bottom')
- ``side`` - (default: 'right') the side ('left' or 'right')
OUTPUT:
permutation -- the Rauzy move of the permutation
EXAMPLES:
::
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move('t','right') a b b a sage: p.rauzy_move('b','right') a b b a
::
sage: p = iet.Permutation('a b c','c b a') sage: p.rauzy_move('t','right') a b c c a b sage: p.rauzy_move('b','right') a c b c b a
::
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move('t','left') a b b a sage: p.rauzy_move('b','left') a b b a
::
sage: p = iet.Permutation('a b c','c b a') sage: p.rauzy_move('t','left') a b c b c a sage: p.rauzy_move('b','left') b a c c b a """
r""" Returns the interval substitution associated.
INPUT:
- ``winner`` - the winner interval ('top' or 'bottom')
- ``side`` - (default: 'right') the side ('left' or 'right')
OUTPUT:
WordMorphism -- a substitution on the alphabet of the permutation
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move_interval_substitution('top','right') WordMorphism: a->a, b->ba sage: p.rauzy_move_interval_substitution('bottom','right') WordMorphism: a->ab, b->b sage: p.rauzy_move_interval_substitution('top','left') WordMorphism: a->ba, b->b sage: p.rauzy_move_interval_substitution('bottom','left') WordMorphism: a->a, b->ab """
return WordMorphism(d)
else:
r""" Return the action of the rauzy_move on the orbit.
INPUT:
- ``i`` - integer
- ``winner`` - the winner interval ('top' or 'bottom')
- ``side`` - (default: 'right') the side ('right' or 'left')
OUTPUT:
WordMorphism -- a substitution on the alphabet of self
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: p.rauzy_move_orbit_substitution('top','right') WordMorphism: a->ab, b->b sage: p.rauzy_move_orbit_substitution('bottom','right') WordMorphism: a->a, b->ab sage: p.rauzy_move_orbit_substitution('top','left') WordMorphism: a->a, b->ba sage: p.rauzy_move_orbit_substitution('bottom','left') WordMorphism: a->ba, b->b """
return WordMorphism(d)
""" Returns the associated Rauzy diagram.
For more information try help(iet.RauzyDiagram).
OUTPUT:
Rauzy diagram -- the Rauzy diagram of the permutation
EXAMPLES::
sage: p = iet.Permutation('a b c', 'c b a') sage: d = p.rauzy_diagram() """
r""" Labelled quadratic (or generalized) permutation
EXAMPLES:
Reducibility testing::
sage: p = iet.GeneralizedPermutation('a b b', 'c c a') sage: p.is_irreducible() True
Reducibility testing with associated decomposition::
sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c') sage: p.is_irreducible() False sage: test, decomposition = p.is_irreducible(return_decomposition = True) sage: test False sage: decomposition (['a'], ['c', 'a'], [], ['c'])
Rauzy movability and Rauzy move::
sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d') sage: p.has_rauzy_move(0) False sage: p.has_rauzy_move(1) True sage: q = p.rauzy_move(1) sage: q a a b b c c d d sage: q.has_rauzy_move(0) True sage: q.has_rauzy_move(1) True
Rauzy diagrams::
sage: p = iet.GeneralizedPermutation('0 0 1 1','2 2') sage: r = p.rauzy_diagram() sage: p in r True """ r""" ALGORITHM:
Order is lexicographic on length of intervals and on intervals.
TESTS::
sage: p0 = iet.GeneralizedPermutation('0 0','1 1 2 2') sage: p1 = iet.GeneralizedPermutation('0 0','1 2 1 2') sage: p2 = iet.GeneralizedPermutation('0 0','1 2 2 1') sage: p3 = iet.GeneralizedPermutation('0 0 1','1 2 2') sage: p4 = iet.GeneralizedPermutation('0 0 1 1','2 2') sage: p5 = iet.GeneralizedPermutation('0 1 0 1','2 2') sage: p6 = iet.GeneralizedPermutation('0 1 1 0','2 2') sage: p0 == p0 and p0 < p1 and p0 < p2 and p0 < p3 and p0 < p4 True sage: p0 < p5 and p0 < p6 and p1 < p2 and p1 < p3 and p1 < p4 True sage: p1 < p5 and p1 < p6 and p2 < p3 and p2 < p4 and p2 < p5 True sage: p2 < p6 and p3 < p4 and p3 < p5 and p3 < p6 and p4 < p5 True sage: p4 < p6 and p5 < p6 and p0 == p0 and p1 == p1 and p2 == p2 True sage: p3 == p3 and p4 == p4 and p5 == p5 and p6 == p6 True """ return -1
r""" Test of Rauzy movability with a specified winner
A quadratic (or generalized) permutation is rauzy_movable type depending on the possible length of the last interval. It is dependent of the length equation.
INPUT:
- ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
OUTPUT:
bool -- ``True`` if self has a Rauzy move
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) return False
# 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""" Perform a Rauzy move on the right (the standard one).
INPUT:
- ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
OUTPUT:
boolean -- ``True`` if self has a Rauzy move
EXAMPLES:
::
sage: p = iet.GeneralizedPermutation('a a b','b c c') sage: p.right_rauzy_move(0) a a b b c c sage: p.right_rauzy_move(1) a a b b c c
::
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.right_rauzy_move(0) a a b b c c sage: p.right_rauzy_move(1) a b b c c a
TESTS::
sage: p = iet.GeneralizedPermutation('a a b','b c c') sage: q = p.top_bottom_inverse() sage: q = q.right_rauzy_move(0) sage: q = q.top_bottom_inverse() sage: q == p.right_rauzy_move(1) True sage: q = p.top_bottom_inverse() sage: q = q.right_rauzy_move(1) sage: q = q.top_bottom_inverse() sage: q == p.right_rauzy_move(0) True sage: p = p.left_right_inverse() sage: q = q.left_rauzy_move(0) sage: q = q.left_right_inverse() sage: q == p.right_rauzy_move(0) True sage: q = p.left_right_inverse() sage: q = q.left_rauzy_move(1) sage: q = q.left_right_inverse() sage: q == p.right_rauzy_move(1) True """
else:
r""" Perform a Rauzy move on the left.
INPUT:
- ``winner`` - 'top' or 'bottom'
OUTPUT:
permutation -- the Rauzy move of self
EXAMPLES:
::
sage: p = iet.GeneralizedPermutation('a a b','b c c') sage: p.left_rauzy_move(0) a a b b c c sage: p.left_rauzy_move(1) a a b b c c
::
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.left_rauzy_move(0) a b b c c a sage: p.left_rauzy_move(1) b b c c a a
TESTS::
sage: p = iet.GeneralizedPermutation('a a b','b c c') sage: q = p.top_bottom_inverse() sage: q = q.left_rauzy_move(0) sage: q = q.top_bottom_inverse() sage: q == p.left_rauzy_move(1) True sage: q = p.top_bottom_inverse() sage: q = q.left_rauzy_move(1) sage: q = q.top_bottom_inverse() sage: q == p.left_rauzy_move(0) True sage: q = p.left_right_inverse() sage: q = q.right_rauzy_move(0) sage: q = q.left_right_inverse() sage: q == p.left_rauzy_move(0) True sage: q = p.left_right_inverse() sage: q = q.right_rauzy_move(1) sage: q = q.left_right_inverse() sage: q == p.left_rauzy_move(1) True """
else:
r""" Returns the associated reduced quadratic permutations.
OUTPUT:
permutation -- the underlying reduced permutation
EXAMPLES::
sage: p = iet.GeneralizedPermutation('a a','b b c c') sage: q = p.reduced() sage: q a a b b c c sage: p.rauzy_move(0).reduced() == q.rauzy_move(0) True """
r""" Returns the associated RauzyDiagram.
OUTPUT:
Rauzy diagram -- the Rauzy diagram of the permutation
EXAMPLES::
sage: p = iet.GeneralizedPermutation('a b c b', 'c d d a') sage: d = p.rauzy_diagram() sage: p in d True
For more information, try help(iet.RauzyDiagram) """
def _twin(self): r""" The twin list of the permutation
TESTS::
sage: p = iet.GeneralizedPermutation('a a','b b') sage: p._twin [[(0, 1), (0, 0)], [(1, 1), (1, 0)]] """
r""" General template for labelled objects
.. warning::
Internal class! Do not use directly! """ r""" INPUT:
- `intervals` - the intervals as a list of two lists
- `alphabet` - something that should be converted to an alphabe
- `flips` - a list of letters of the alphabet
TESTS:
::
sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationIET sage: p = FlippedLabelledPermutationIET([['a','b'],['a','b']],flips='a') sage: p == loads(dumps(p)) True sage: p = FlippedLabelledPermutationIET([['a','b'],['b','a']],flips='ab') sage: p == loads(dumps(p)) True
::
sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationLI sage: p = FlippedLabelledPermutationLI([['a','a','b'],['b','c','c']],flips='a') sage: p == loads(dumps(p)) True sage: p = FlippedLabelledPermutationLI([['a','a'],['b','b','c','c']],flips='ac') sage: p == loads(dumps(p)) True """
r""" Returns a copy of ``self``
TESTS::
sage: p = iet.Permutation('a b c','c b a',flips='a') sage: h = hash(p) sage: t = p._twin sage: q = copy(p) sage: q == p True sage: q is p False sage: q._twin is p._twin False """
self._intervals[1][:]] self._flips[1][:]]
r""" Returns a list associated to the permutation.
INPUT:
- ``flips`` - boolean (default: ``False``)
OUTPUT:
list -- two lists of labels
EXAMPLES::
sage: p = iet.GeneralizedPermutation('0 0 1 2 2 1', '3 3', flips='1') sage: p.list(flips=True) [[('0', 1), ('0', 1), ('1', -1), ('2', 1), ('2', 1), ('1', -1)], [('3', 1), ('3', 1)]] sage: p.list(flips=False) [['0', '0', '1', '2', '2', '1'], ['3', '3']]
The list can be used to reconstruct the permutation
::
sage: p = iet.Permutation('a b c','c b a',flips='ab') sage: p == iet.Permutation(p.list(), flips=p.flips()) True
::
sage: p = iet.GeneralizedPermutation('a b b c','c d d a',flips='ad') sage: p == iet.GeneralizedPermutation(p.list(),flips=p.flips()) True """ for _ in self._intervals[0]], self._flips[0])) for _ in self._intervals[1]], self._flips[1])) else:
r""" Get labels and flips of specified interval.
The result is a 2-uple (letter, flip) where letter is the name of the sub-interval and flip is a number corresponding to the presence of flip as following: 1 (no flip) and -1 (a flip).
EXAMPLES::
sage: p = iet.Permutation('a b', 'b a', flips='a') sage: p[0] [('a', -1), ('b', 1)] sage: p = iet.GeneralizedPermutation('c p p', 't t c', flips='ct') sage: p[1] [('t', -1), ('t', -1), ('c', -1)] """ raise TypeError("Must be an integer") raise IndexError("The integer must be 0 or 1")
r""" Test of equality
ALGORITHM:
not considering the alphabet used for the representation but just the order
TESTS::
sage: p1 = iet.Permutation('a b c','c b a',flips='a') sage: p2 = iet.Permutation('a b c','c b a',flips='b') sage: p3 = iet.Permutation('d e f','f e d',flips='d') sage: p1 == p1 and p2 == p2 and p3 == p3 True sage: p1 == p2 False sage: p1 == p3 True """ type(self) is type(other) and self._intervals == other._intervals and self._flips == other._flips)
r""" Test of difference
ALGORITHM:
not considering the alphabet used for the representation
TESTS::
sage: p1 = iet.Permutation('a b c','c b a',flips='a') sage: p2 = iet.Permutation('a b c','c b a',flips='b') sage: p3 = iet.Permutation('d e f','f e d',flips='d') sage: p1 != p1 or p2 != p2 or p3 != p3 False sage: p1 != p2 True sage: p1 != p3 False """ type(self) is not type(other) or self._intervals != other._intervals or self._flips != other._flips)
r""" Inversion of the permutation (called by tb_inverse).
.. TODO::
Resolve properly the mutability problem associated to hash value and twin list.
TESTS::
sage: p = iet.Permutation('a','a',flips='a') sage: p.tb_inverse() #indirect doctest -a -a sage: p = iet.Permutation('a b','a b',flips='a') sage: p.tb_inverse() #indirect doctest -a b -a b sage: p = iet.Permutation('a b','a b',flips='b') sage: p.tb_inverse() #indirect doctest a -b a -b sage: p = iet.Permutation('a b','b a',flips='a') sage: p.tb_inverse() #indirect doctest b -a -a b sage: p = iet.Permutation('a b','b a',flips='b') sage: p.tb_inverse() #indirect doctest -b a a -b """
self._hash = None
r""" Reverses the permutation (called by lr_inverse)
.. TODO::
Resolve properly the mutability problem with _twin list and the hash value.
TESTS::
sage: p = iet.Permutation('a','a',flips='a') sage: p.lr_inverse() #indirect doctest -a -a sage: p = iet.Permutation('a b','a b',flips='a') sage: p.lr_inverse() #indirect doctest b -a b -a sage: p = iet.Permutation('a b','a b',flips='b') sage: p.lr_inverse() #indirect doctest -b a -b a sage: p = iet.Permutation('a b','b a',flips='a') sage: p.lr_inverse() #indirect doctest b -a -a b sage: p = iet.Permutation('a b','b a',flips='b') sage: p.lr_inverse() #indirect doctest -b a a -b """
self._hash is None
FlippedLabelledPermutation, FlippedPermutationIET, LabelledPermutationIET): r""" Flipped labelled permutation from iet.
EXAMPLES:
Reducibility testing (does not depends of flips)::
sage: p = iet.Permutation('a b c', 'c b a',flips='a') sage: p.is_irreducible() True sage: q = iet.Permutation('a b c d', 'b a d c', flips='bc') sage: q.is_irreducible() False
Rauzy movability and Rauzy move::
sage: p = iet.Permutation('a b c', 'c b a',flips='a') sage: p -a b c c b -a sage: p.rauzy_move(1) -c -a b -c b -a sage: p.rauzy_move(0) -a b c c -a b
Rauzy diagrams::
sage: d = iet.RauzyDiagram('a b c d','d a b c',flips='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.
AUTHORS:
- Vincent Delecroix (2009-09-29): initial version """ r""" The associated reduced permutation.
OUTPUT:
permutation -- the associated reduced permutation
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a',flips='a') sage: q = iet.Permutation('a b c','c b a',flips='a',reduced=True) sage: p.reduced() == q True """
intervals=self.list(flips=False), flips=self.flips(), alphabet=self.alphabet())
r""" ALGORITHM:
Uses hash of string
TESTS::
sage: p =[] sage: p.append(iet.Permutation('a b','a b',flips='a')) sage: p.append(iet.Permutation('a b','a b',flips='b')) sage: p.append(iet.Permutation('a b','a b',flips='ab')) sage: p.append(iet.Permutation('a b','b a',flips='a')) sage: p.append(iet.Permutation('a b','b a',flips='b')) sage: p.append(iet.Permutation('a b','b a',flips='ab')) sage: h = list(map(hash, p)) sage: for i in range(len(h)-1): ....: if h[i] == h[i+1]: ....: print("You choose a bad hash!") """
r""" Returns the Rauzy move.
INPUT:
- ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
- ``side`` - (default: 'right') 'right' (or 'r') or 'left' (or 'l')
OUTPUT:
permutation -- the Rauzy move of ``self``
EXAMPLES:
::
sage: p = iet.Permutation('a b','b a',flips='a') sage: p.rauzy_move('top') -a b b -a sage: p.rauzy_move('bottom') -b -a -b -a
::
sage: p = iet.Permutation('a b c','c b a',flips='b') sage: p.rauzy_move('top') a -b c c a -b sage: p.rauzy_move('bottom') a c -b c -b a """
r""" Returns the Rauzy diagram associated to this permutation.
For more information, try help(iet.RauzyDiagram)
OUTPUT:
RauzyDiagram -- the Rauzy diagram of ``self``
EXAMPLES::
sage: p = iet.Permutation('a b c', 'c b a',flips='a') sage: p.rauzy_diagram() Rauzy diagram with 3 permutations """
FlippedPermutationLI, LabelledPermutationLI): r""" Flipped labelled quadratic (or generalized) permutation.
EXAMPLES:
Reducibility testing::
sage: p = iet.GeneralizedPermutation('a b b', 'c c a', flips='a') sage: p.is_irreducible() True
Reducibility testing with associated decomposition::
sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c', flips='ab') sage: p.is_irreducible() False sage: test, decomp = p.is_irreducible(return_decomposition = True) sage: test False sage: decomp (['a'], ['c', 'a'], [], ['c'])
Rauzy movability and Rauzy move::
sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d', flips='d') sage: p.has_rauzy_move(0) False sage: p.has_rauzy_move(1) True sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c') sage: p.has_rauzy_move(0) True sage: p.has_rauzy_move(1) True """ r""" The associated reduced permutation.
OUTPUT:
permutation -- the associated reduced permutation
EXAMPLES::
sage: p = iet.GeneralizedPermutation('a a','b b c c',flips='a') sage: q = iet.GeneralizedPermutation('a a','b b c c',flips='a',reduced=True) sage: p.reduced() == q True """
intervals=self.list(flips=False), flips=self.flips(), alphabet=self.alphabet())
r""" Perform a Rauzy move on the right (the standard one).
INPUT:
- ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
OUTPUT:
permutation -- the Rauzy move of ``self``
EXAMPLES:
::
sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c') sage: p.right_rauzy_move(0) a a b -c b -c sage: p.right_rauzy_move(1) a a -b -c -b -c
::
sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='ab') sage: p.right_rauzy_move(0) a -b a -b c c sage: p.right_rauzy_move(1) b -a b c c -a """
else:
else:
r""" Perform a Rauzy move on the left.
INPUT:
- ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
OUTPUT:
-- a permutation
EXAMPLES:
::
sage: p = iet.GeneralizedPermutation('a a b','b c c') sage: p.left_rauzy_move(0) a a b b c c sage: p.left_rauzy_move(1) a a b b c c
::
sage: p = iet.GeneralizedPermutation('a b b','c c a') sage: p.left_rauzy_move(0) a b b c c a sage: p.left_rauzy_move(1) b b c c a a """ result = copy(self)
winner_letter = result._intervals[winner][0] loser_letter = result._intervals[1-winner].pop(0)
if winner_letter in result._intervals[winner][1:]: loser_to = result._intervals[winner][1:].index(winner_letter)+2 result._intervals[winner].insert(loser_to, loser_letter)
else: loser_to = result._intervals[1-winner].index(winner_letter) result._intervals[1-winner].insert(loser_to, loser_letter)
return result
r""" Returns the associated Rauzy diagram.
For more information, try help(RauzyDiagram)
OUTPUT :
-- a RauzyDiagram
EXAMPLES::
sage: p = iet.GeneralizedPermutation('a b b a', 'c d c d') sage: d = p.rauzy_diagram() """ return FlippedLabelledRauzyDiagram(self, **kargs)
r""" Template for Rauzy diagrams of labelled permutations.
.. WARNING::
DO NOT USE """ r""" Path in Labelled Rauzy diagram. """ r""" Returns the matrix associated to a path.
The matrix associated to a Rauzy induction, is the linear application that allows to recover the lengths of ``self`` from the lengths of the induced.
OUTPUT:
matrix -- a square matrix of integers
EXAMPLES:
::
sage: p = iet.Permutation('a1 a2','a2 a1') sage: d = p.rauzy_diagram() sage: g = d.path(p,'top') sage: g.matrix() [1 0] [1 1] sage: g = d.path(p,'bottom') sage: g.matrix() [1 1] [0 1]
::
sage: p = iet.Permutation('a b c','c b a') sage: d = p.rauzy_diagram() sage: g = d.path(p) sage: g.matrix() == identity_matrix(3) True sage: g = d.path(p,'top') sage: g.matrix() [1 0 0] [0 1 0] [1 0 1] sage: g = d.path(p,'bottom') sage: g.matrix() [1 0 1] [0 1 0] [0 0 1] """
r""" Returns the substitution of intervals obtained.
OUTPUT:
WordMorphism -- the word morphism corresponding to the interval
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: p0 = r.path(p,0) sage: s0 = p0.interval_substitution() sage: s0 WordMorphism: a->a, b->ba sage: p1 = r.path(p,1) sage: s1 = p1.interval_substitution() sage: s1 WordMorphism: a->ab, b->b sage: (p0 + p1).interval_substitution() == s1 * s0 True sage: (p1 + p0).interval_substitution() == s0 * s1 True """
r""" Return the substitution on the orbit of the left extremity.
OUTPUT:
WordMorphism -- the word morphism corresponding to the orbit
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: d = p.rauzy_diagram() sage: g0 = d.path(p,'top') sage: s0 = g0.orbit_substitution() sage: s0 WordMorphism: a->ab, b->b sage: g1 = d.path(p,'bottom') sage: s1 = g1.orbit_substitution() sage: s1 WordMorphism: a->a, b->ab sage: (g0 + g1).orbit_substitution() == s0 * s1 True sage: (g1 + g0).orbit_substitution() == s1 * s0 True """
r""" Tests the fullness.
A path is full if all intervals win at least one time.
OUTPUT:
boolean -- ``True`` if the path is full and ``False`` else
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: g1 = r.path(p,'b','t','b') sage: g0.is_full() False sage: g1.is_full() False sage: (g0 + g1).is_full() True sage: (g1 + g0).is_full() True """
r""" Returns the interval substitution associated to an edge
OUTPUT:
WordMorphism -- the WordMorphism corresponding to the edge
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: r.edge_to_interval_substitution(None,None) WordMorphism: a->a, b->b, c->c sage: r.edge_to_interval_substitution(p,0) WordMorphism: a->a, b->b, c->ca sage: r.edge_to_interval_substitution(p,1) WordMorphism: a->ac, b->b, c->c """
return WordMorphism(dict((a,a) for a in self.letters()))
r""" Returns the interval substitution associated to an edge
OUTPUT:
WordMorphism -- the word morphism corresponding to the edge
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: r.edge_to_orbit_substitution(None,None) WordMorphism: a->a, b->b, c->c sage: r.edge_to_orbit_substitution(p,0) WordMorphism: a->ac, b->b, c->c sage: r.edge_to_orbit_substitution(p,1) WordMorphism: a->a, b->b, c->ac """
return WordMorphism(dict((a,a) for a in self.letters()))
r""" Returns an iterator over all full path starting at start.
INPUT:
- ``start`` - the start point
- ``max_length`` - a limit on the length of the paths
OUTPUT:
iterator -- iterator over full loops
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: r = p.rauzy_diagram() sage: for g in r.full_loop_iterator(p,2): ....: print(g.matrix()) ....: print("*****") [1 1] [1 2] ***** [2 1] [1 1] ***** """
lambda x: x.is_loop() and x.is_full(), self._all_path_extension(g,max_length))
r""" Returns an iterator over all full loops of given length.
INPUT:
- ``start`` - the initial permutation
- ``length`` - the length to consider
OUTPUT:
iterator -- an iterator over the full loops of given length
EXAMPLES::
sage: p = iet.Permutation('a b','b a') sage: d = p.rauzy_diagram() sage: for g in d.full_nloop_iterator(p,2): ....: print(g.matrix()) ....: print("*****") [1 1] [1 2] ***** [2 1] [1 1] ***** """
lambda x: x.is_loop() and x.is_full(), self._all_npath_extension(g,length))
r""" Translation of a labelled permutation to a vertex
INPUT:
- ``p`` - a labelled Permutation
TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: p in r #indirect doctest True """
r""" Sets self._element with data
TESTS::
sage: p = iet.Permutation('a b c','c b a') sage: r = p.rauzy_diagram() sage: r[p][0] == p.rauzy_move(0) #indirect doctest True sage: r[p][1] == p.rauzy_move(1) #indirect doctest True """
r""" Rauzy diagram of flipped labelled permutations """ r""" Returns what must be stored from p.
INPUT:
- ``p`` - a Flipped labelled permutation
TESTS::
sage: p = iet.Permutation('a b c','c b a',flips='a') sage: r = p.rauzy_diagram() sage: p in r #indirect doctest True """ (tuple(p._flips[0]), tuple(p._flips[1])))
r""" Returns what the vertex i as a permutation.
TESTS::
sage: p = iet.Permutation('a b','b a',flips='a') sage: r = p.rauzy_diagram() sage: p in r #indirect doctest True """ |