r"""
Permutations template
This file define high level operations on permutations (alphabet,
the different rauzy induction, ...) shared by reduced and labeled
permutations.
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
TODO:
- construct as options different string representations for a permutation
- the two intervals: str
- the two intervals on one line: str_one_line
- the separatrix diagram: str_separatrix_diagram
- twin[0] and twin[1] for reduced permutation
- nothing (useful for Rauzy diagram)
"""
from sage.structure.sage_object import SageObject
from copy import copy
from sage.rings.integer import Integer
from sage.combinat.words.alphabet import Alphabet
from sage.graphs.graph import DiGraph
from sage.matrix.constructor import identity_matrix, matrix
def interval_conversion(interval=None):
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.combinat.iet.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
"""
if isinstance(interval, (int,Integer)):
if interval != 0 and interval != 1:
raise ValueError, "interval must be 0 or 1"
return interval
if isinstance(interval,str):
if interval == '':
raise ValueError, "the interval can not be the empty string"
if 'top'.startswith(interval): return 0
if 'bottom'.startswith(interval): return 1
raise ValueError, "'%s' can not be converted to interval" %(interval)
raise TypeError, "'%s' is not an admissible type" %(str(interval))
def side_conversion(side=None):
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.combinat.iet.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
"""
if side is None: return -1
if isinstance(side,str):
if side == '':
raise ValueError, "no empty string for side"
if 'left'.startswith(side): return 0
if 'right'.startswith(side): return -1
raise ValueError, "'%s' can not be converted to a side" %(side)
if isinstance(side, (int,Integer)):
if side != 0 and side != 1 and side != -1:
raise ValueError, "side must be 0 or 1"
if side == 0: return 0
return -1
raise TypeError, "'%s' is not an admissible type" %(str(side))
def twin_list_iet(a=None):
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.combinat.iet.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]]
"""
if a is None : return [[],[]]
twin = [[0]*len(a[0]), [0]*len(a[1])]
for i in range(len(twin[0])) :
c = a[0][i]
j = a[1].index(c)
twin[0][i] = j
twin[1][j] = i
return twin
def twin_list_li(a=None):
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.combinat.iet.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)]]
"""
if a is None: return [[],[]]
twin = [
[(0,j) for j in range(len(a[0]))],
[(1,j) for j in range(len(a[1]))]]
for i in (0,1):
for j in range(len(twin[i])) :
if twin[i][j] == (i,j) :
if a[i][j] in a[i][j+1:] :
j2 = (a[i][j+1:]).index(a[i][j]) + j + 1
twin[i][j] = (i,j2)
twin[i][j2] = (i,j)
else :
j2 = a[1].index(a[i][j])
twin[0][j] = (1,j2)
twin[1][j2] = (0,j)
return twin
class Permutation(SageObject):
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.
"""
def _repr_(self):
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')
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]]
"""
if self._repr_type is None:
return ''
elif self._repr_type == 'reduced':
return ''.join(map(str,self[1]))
else:
f = getattr(self, self._repr_type)
if callable(f):
return str(f(*self._repr_options))
else:
return str(f)
def str(self, sep= "\n"):
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')
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
"""
l = self.list()
s0 = ' '.join(map(str,l[0]))
s1 = ' '.join(map(str,l[1]))
return s0 + sep + s1
_repr_type = 'str'
_repr_options = ("\n",)
def _set_alphabet(self, alphabet):
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
"""
alphabet = Alphabet(alphabet)
if alphabet.cardinality() <len(self):
raise ValueError, "Your alphabet has not enough letters"
self._alphabet = alphabet
def alphabet(self, data=None):
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
"""
if data is None:
return self._alphabet
else:
self._set_alphabet(data)
def letters(self):
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]
"""
return map(self._alphabet.unrank, range(len(self)))
def left_right_inverse(self):
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
"""
result = copy(self)
result._reversed()
return result
lr_inverse = left_right_inverse
vertical_inverse = left_right_inverse
def top_bottom_inverse(self):
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
"""
result = copy(self)
result._inversed()
return result
tb_inverse = top_bottom_inverse
horizontal_inverse = top_bottom_inverse
def symmetric(self):
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
"""
res = copy(self)
res._inversed()
res._reversed()
return res
def has_rauzy_move(self, winner='top', side=None):
r"""
Tests the legality of a Rauzy move.
INPUT:
- ``winner`` - 'top' or 'bottom' corresponding to the interval
- ``side`` - 'left' or 'right' (defaut)
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
"""
winner = interval_conversion(winner)
side = side_conversion(side)
if side == -1:
return self.has_right_rauzy_move(winner)
elif side == 0:
return self.lr_inverse().has_right_rauzy_move(winner)
def rauzy_move(self, winner, side='right', iteration=1):
r"""
Returns the permutation after a Rauzy move.
INPUT:
- ``winner`` - 'top' or 'bottom' interval
- ``side`` - 'right' or 'left' (defaut: '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
"""
winner = interval_conversion(winner)
side = side_conversion(side)
if side == -1:
tmp = self
for k in range(iteration):
tmp = tmp.right_rauzy_move(winner)
return tmp
elif side == 0:
tmp = self
for k in range(iteration):
tmp = tmp.left_rauzy_move(winner)
return tmp
class PermutationIET(Permutation):
"""
Template for permutation from Interval Exchange Transformation.
.. warning::
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version
"""
def _init_alphabet(self,a) :
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
"""
self._alphabet = Alphabet(a[0])
def is_irreducible(self, return_decomposition=False) :
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
"""
s0, s1 = 0, 0
for i in range(len(self)-1) :
s0 += i
s1 += self._twin[0][i]
if s0 == s1 :
if return_decomposition :
return False, (self[0][:i+1], self[0][i+1:], self[1][:i+1], self[1][i+1:])
return False
if return_decomposition:
return True, (self[0],[],self[1],[])
return True
def decompose(self):
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
"""
l = []
test, t = self.is_irreducible(return_decomposition=True)
l.append(self.__class__((t[0],t[2])))
while not test:
q = self.__class__((t[1],t[3]))
test, t = q.is_irreducible(return_decomposition=True)
l.append(self.__class__((t[0],t[2])))
return l
def intersection_matrix(self):
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]
"""
n = self.length_top()
m = matrix(n)
for i in range(n):
for j in range(i,n):
if self._twin[0][i] > self._twin[0][j]:
m[i,j] = 1
m[j,i] = -1
return m
def attached_out_degree(self):
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
"""
left_corner = ((self[1][0], self[0][0]), 'L')
for s in self.separatrix_diagram(side=True):
if left_corner in s:
return len(s)/2 - 1
def attached_in_degree(self):
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
"""
right_corner = ((self[0][-1], self[1][-1]), 'R')
for s in self.separatrix_diagram(side=True):
if right_corner in s:
return len(s)/2 - 1
def attached_type(self):
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)
"""
left_corner = ((self[1][0], self[0][0]), 'L')
right_corner = ((self[0][-1], self[1][-1]), 'R')
l = self.separatrix_diagram(side=True)
for s in l:
if left_corner in s and right_corner in s:
i1 = s.index(left_corner)
i2 = s.index(right_corner)
return ([len(s)/2-1], ((i2-i1+1)/2) %2)
elif left_corner in s:
left_degree = len(s)/2-1
elif right_corner in s:
right_degree = len(s)/2-1
return ([left_degree,right_degree], 0)
def separatrix_diagram(self,side=False):
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']]
"""
separatrices = range(len(self))
labels = self[1]
singularities = []
twin = self._twin
n = len(self)-1
while separatrices != []:
start = separatrices.pop(0)
separatrix = start
if side:
singularity = [(labels[start],'L')]
else:
singularity = [labels[start]]
while True:
if separatrix == 0:
separatrix = twin[0][0]
if side:
a = singularity.pop()[0]
else:
a = singularity.pop()
if side:
singularity.append(((a,labels[separatrix]), 'L'))
else:
singularity.append((a,labels[separatrix]))
if separatrix == start:
singularities.append(singularity)
break
del separatrices[separatrices.index(separatrix)]
else:
separatrix -= 1
if side:
singularity.append((labels[separatrix],'R'))
else:
singularity.append(labels[separatrix])
if separatrix == twin[0][n] :
separatrix = n
if side:
a = singularity.pop()[0]
else:
a = singularity.pop()
if side:
singularity.append(((a,labels[separatrix]),'R'))
else:
singularity.append((a,labels[separatrix]))
separatrix = twin[0][twin[1][separatrix]+1]
if separatrix == start:
singularities.append(singularity)
break
elif separatrix != twin[0][0]:
del separatrices[separatrices.index(separatrix)]
if side:
singularity.append((labels[separatrix],'L'))
else:
singularity.append(labels[separatrix])
return singularities
def stratum(self, marked_separatrix='no'):
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: print p.stratum()
H(0, 0)
sage: p = iet.Permutation('a b c d', 'd a b c')
sage: print p.stratum()
H(0, 0, 0)
sage: p = iet.Permutation(range(9), [8,5,2,7,4,1,6,3,0])
sage: print 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)
"""
from sage.combinat.iet.strata import AbelianStratum
if not self.is_irreducible():
return map(lambda x: x.stratum(marked_separatrix), self.decompose())
if len(self) == 1:
return AbelianStratum([])
singularities = [len(x)/2 - 1 for x in self.separatrix_diagram()]
return AbelianStratum(singularities,marked_separatrix=marked_separatrix)
def genus(self) :
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
"""
return self.stratum().genus()
def arf_invariant(self):
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: print p1.arf_invariant()
1
sage: p0 = iet.Permutation(a,b0)
sage: print 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: print p1.arf_invariant()
1
sage: p0 = iet.Permutation(a,b0)
sage: print 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
"""
M = self.intersection_matrix()
F, C = M.symplectic_form()
g = F.rank()/2
n = F.ncols()
s = 0
for i in range(g):
a = C.row(i)
a_indices = []
for k in xrange(n):
if a[k] != 0: a_indices.append(k)
t_a = len(a_indices) % 2
for j1 in xrange(len(a_indices)):
for j2 in xrange(j1+1,len(a_indices)):
t_a = (t_a + M[a_indices[j1], a_indices[j2]]) % 2
b = C.row(g+i)
b_indices = []
for k in xrange(n):
if b[k] != 0: b_indices.append(k)
t_b = len(b_indices) % 2
for j1 in xrange(len(b_indices)):
for j2 in xrange(j1+1,len(b_indices)):
t_b = (t_b + M[b_indices[j1],b_indices[j2]]) % 2
s = (s + t_a * t_b) % 2
return s
def connected_component(self,marked_separatrix='no'):
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: print p_hyp.connected_component()
H_hyp(6)
sage: print p_odd.connected_component()
H_odd(6)
sage: print 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: print p_hyp.connected_component()
H_hyp(4, 4)
sage: p_odd.stratum() == AbelianStratum(4,4)
True
sage: print p_odd.connected_component()
H_odd(4, 4)
sage: p_even.stratum() == AbelianStratum(4,4)
True
sage: print 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
"""
from sage.combinat.iet.strata import (CCA, HypCCA,
NonHypCCA, OddCCA, EvenCCA)
if not self.is_irreducible():
return map(lambda x: x.connected_component(marked_separatrix),
self.decompose())
stratum = self.stratum(marked_separatrix=marked_separatrix)
cc = stratum._cc
if len(cc) == 1:
return stratum.connected_components()[0]
if HypCCA in cc:
if self.is_hyperelliptic():
return HypCCA(stratum)
else:
cc = cc[1:]
if len(cc) == 1:
return cc[0](stratum)
else:
spin = self.arf_invariant()
if spin == 0:
return EvenCCA(stratum)
else:
return OddCCA(stratum)
def order_of_rauzy_action(self, winner, side=None):
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
"""
winner = interval_conversion(winner)
side = side_conversion(side)
if side == -1:
return self.length(winner) - self._twin[winner][-1] - 1
elif side == 0:
return self._twin[winner][0]
def erase_marked_points(self):
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
"""
res = copy(self)
l = res.list()
left_corner = ((l[1][0], l[0][0]), 'L')
right_corner = ((l[0][-1], l[1][-1]), 'R')
s = res.separatrix_diagram(side=True)
lengths = map(len, s)
while 2 in lengths:
if lengths == [2]:
return res
i = lengths.index(2)
t = s[i]
if t[0] == left_corner or t[0] == right_corner:
letter = t[1][0]
else:
letter = t[0][0]
res = res.erase_letter(letter)
l = res.list()
s = res.separatrix_diagram(side=True)
lengths = map(len, s)
return res
def is_hyperelliptic(self):
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 prescripebd singularities" Invent. math.
153, 631-678 (2003)
"""
test = self.erase_marked_points()
n = test.length_top()
cylindric = test.cylindric()
return cylindric._twin[0] == range(n-1,-1,-1)
def cylindric(self):
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
"""
tmp = copy(self)
n = self.length(0)
a0 = tmp._twin[0][-1]
a1 = tmp._twin[1][-1]
p_min = min(a0,a1)
while p_min > 0:
if p_min == a0:
k_min = min(tmp._twin[1][a0+1:])
k = n - tmp._twin[1].index(k_min) - 1
tmp = tmp.rauzy_move(0, iteration=k)
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)
a0 = tmp._twin[0][-1]
a1 = tmp._twin[1][-1]
p_min = min(a0,a1)
if a0 == 0:
k = n - tmp._twin[1].index(0) - 1
tmp = tmp.rauzy_move(0, iteration = k)
else:
k = n - tmp._twin[0].index(0) - 1
tmp = tmp.rauzy_move(1, iteration=k)
return tmp
def is_cylindric(self):
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
"""
return self._twin[0][-1] == 0 and self._twin[1][-1] == 0
def to_permutation(self):
r"""
Returns the permutation as an element of the symetric 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
"""
from sage.combinat.permutation import Permutation
return Permutation(map(lambda x: x+1,self._twin[1]))
class PermutationLI(Permutation):
r"""
Template for quadratic permutation.
.. warning::
Internal class! Do not use directly!
AUTHOR:
- Vincent Delecroix (2008-12-20): initial version
"""
def _init_twin(self,a):
r"""
Initialization of the twin data.
TEST::
sage: p = iet.GeneralizedPermutation('a a','b b',reduced=True) #indirect doctest
sage: p._twin
[[(0, 1), (0, 0)], [(1, 1), (1, 0)]]
"""
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:] :
j2 = (a[i][j+1:]).index(a[i][j]) + j + 1
l[i][j] = (i,j2)
l[i][j2] = (i,j)
else :
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]
def _init_alphabet(self, intervals) :
r"""
Intialization procedure of the alphabet of self from intervals list
TEST::
sage: p = iet.GeneralizedPermutation('a a','b b') #indirect doctest
sage: p.alphabet()
Ordered Alphabet ['a', 'b']
"""
tmp_alphabet = []
for letter in intervals[0] + intervals[1] :
if letter not in tmp_alphabet :
tmp_alphabet.append(letter)
self._alphabet = Alphabet(tmp_alphabet)
def is_irreducible(self, return_decomposition=False) :
r"""
Test of reducibility
A quadratic (or generalized) permutation is reducible if there exist 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.
INPUT:
- you can eventually set return_decomposition to True
OUTPUT:
An integer, or an integer and a tuple.
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 BA
A12 = B1 u A2
A21 = A1 u B2
A22 = B2 u A2
REFERENCES:
Boissy-Lanneau
EXAMPLES::
sage: iet.GeneralizedPermutation('a a','b b').is_irreducible()
False
sage: iet.GeneralizedPermutation('a a b','b c c').is_irreducible()
True
AUTHORS:
- Vincent Delecroix (2008-12-20)
"""
l0 = self.length_top()
l1 = self.length_bottom()
s = self.list()
A11, A12, A21, A22 = [], [], [], []
for i1 in range(0, l0) :
if (i1 > 0) and (s[0][i1-1] in A11) :
A11 = []
break
A11 = s[0][:i1]
for i2 in range(l0 - 1, i1 - 1, -1) :
if s[0][i2] in A12 :
A12 = []
break
A12 = s[0][i2:]
for i3 in range(0, l1) :
if (i3 > 0) and (s[1][i3-1] in A21) :
A21 = []
break
A21 = s[1][:i3]
for i4 in range(l1 - 1, i3 - 1, -1) :
if s[1][i4] in A22 :
A22 = []
break
A22 = s[1][i4:]
if sorted(A11 + A22) == sorted(A12 + A21) :
if return_decomposition :
return False, (A11,A12,A21,A22)
return False
else : A22 = []
else : A21 = []
else : A12 = []
else : A11 = []
A11, A21 = s[0][:1], s[1][:1]
for i1 in range(1, l0) :
if s[0][i1-1] in A11 :
A11 = s[0][:1]
break
A11 = s[0][:i1]
for i3 in range(1, l1) :
if s[1][i3-1] in A21 :
A21 = s[1][:1]
break
A21 = s[1][:i3]
if sorted(A11) == sorted(A21) :
if return_decomposition :
return False,(A11,A12,A21,A22)
return False
else : A11 = s[0][:1]
else : A21 = s[1][:1]
if return_decomposition :
return True, ()
return True
def has_right_rauzy_move(self, winner):
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
"""
winner = interval_conversion(winner)
loser = 1 - winner
if (self._twin[0][-1][0] == 1 and
self._twin[0][-1][1] == self.length_bottom() - 1) :
return False
if self._twin[winner][-1][0] == loser: return True
if self._twin[loser][-1][0] == winner: return True
if [i for i,_ in self._twin[loser]].count(loser) == 2:
return False
return True
def labelize_flip(couple):
r"""
Returns a string from a 2-uple couple of the form (name, flip).
TESTS::
sage: from sage.combinat.iet.template import labelize_flip
sage: labelize_flip((0,1))
' 0'
sage: labelize_flip((0,-1))
'-0'
"""
if couple[1] == -1: return '-' + str(couple[0])
return ' ' + str(couple[0])
class FlippedPermutation(Permutation):
r"""
Template for flipped generalized permutations.
.. warning::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
"""
def _init_flips(self,intervals,flips):
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']
"""
self._flips = [[1]*self.length_top(), [1]*self.length_bottom()]
for interval in (0,1):
for i,letter in enumerate(intervals[interval]):
if letter in flips:
self._flips[interval][i] = -1
def str(self, sep="\n"):
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
"""
l = self.list(flips=True)
return (' '.join(map(labelize_flip, l[0]))
+ sep
+ ' '.join(map(labelize_flip, l[1])))
return s
class FlippedPermutationIET(FlippedPermutation, PermutationIET):
r"""
Template for flipped Abelian permutations.
.. warning::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
"""
def flips(self):
r"""
Returns the list of flips.
EXAMPLES::
sage: p = iet.Permutation('a b c','c b a',flips='ac')
sage: p.flips()
['a', 'c']
"""
result = []
l = self.list(flips=False)
for i,f in enumerate(self._flips[0]):
if f == -1:
result.append(l[0][i])
return result
class FlippedPermutationLI(FlippedPermutation, PermutationLI):
r"""
Template for flipped quadratic permutations.
.. warning::
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
"""
def flips(self):
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']
"""
res = []
l = self.list(flips=False)
for i,f in enumerate(self._flips[0]):
if f == -1:
res.append(l[0][i])
for i,f in enumerate(self._flips[1]):
if f == -1:
res.append(l[1][i])
return list(set(res))
class RauzyDiagram(SageObject):
r"""
Template for Rauzy diagrams.
.. warning:
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2008-12-20): initial version
"""
class Path(SageObject):
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.
"""
def __init__(self, parent, *data):
r"""
Constructor of the path.
TEST::
sage: p = iet.Permutation('a b c','c b a')
sage: r = p.rauzy_diagram()
sage: g = r.path(p,0,1,0)
"""
self._parent = parent
if len(data) == 0:
raise ValueError("No empty data")
start = data[0]
if start not in self._parent:
raise ValueError, "Starting point not in this Rauzy diagram"
self._start = self._parent._permutation_to_vertex(start)
cur_vertex = self._start
self._edge_types = []
n = len(self._parent._edge_types)
for i in data[1:]:
if not isinstance(i, (int,Integer)):
i = self._parent.edge_types_index(i)
if i < 0 or i > n:
raise ValueError, "indices must be integer between 0 and %d" %(n)
neighbours = self._parent._succ[cur_vertex]
if neighbours[i] is None:
raise ValueError, "Invalid path"
cur_vertex = neighbours[i]
self._edge_types.append(i)
self._end = cur_vertex
def _repr_(self):
r"""
Returns a representation of the path.
TEST::
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
"""
return "Path of length %d in a Rauzy diagram" %(len(self))
def start(self):
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
"""
return self._parent._vertex_to_permutation(self._start)
def end(self):
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
"""
return self._parent._vertex_to_permutation(self._end)
def edge_types(self):
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]
"""
return copy(self._edge_types)
def __eq__(self, other):
r"""
Tests equality
TEST::
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
"""
return (
type(self) == type(other) and
self._parent == other._parent and
self._start == other._start and
self._edge_types == other._edge_types)
def __ne__(self,other):
r"""
Tests inequality
TEST::
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
"""
return (
type(self) != type(other) or
self._parent != other._parent or
self._start != other._start or
self._edge_types != other._edge_types)
def __copy__(self):
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
"""
res = self.__class__(self._parent, self.start())
res._edge_types = copy(self._edge_types)
res._end = copy(self._end)
return res
def pop(self):
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
"""
if len(self) == 0:
return self._parent.path(self.start())
else:
e = self._edge_types.pop()
self._end = self._parent._pred[self._end][e]
return self._parent.path(self.end(),e)
def append(self, edge_type):
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
"""
if not isinstance(edge_type, (int,Integer)):
edge_type = self._parent.edge_types_index(edge_type)
elif edge_type < 0 or edge_type >= len(self._parent._edge_types):
raise ValueError, "Edge type not valid"
if self._parent._succ[self._end][edge_type] is None:
raise ValueError, "%d is not a valid edge" %(edge_type)
self._edge_types.append(edge_type)
self._end = self._parent._succ[self._end][edge_type]
def _fast_append(self, edge_type):
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)
"""
self._edge_types.append(edge_type)
self._end = self._parent._succ[self._end][edge_type]
def extend(self, path):
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
"""
if self._parent != path._parent:
raise ValueError, "Not on the same Rauzy diagram"
if self._end != path._start:
raise ValueError, "The end of the first path must the start of the second"
self._edge_types.extend(path._edge_types)
self._end = path._end
def _fast_extend(self, path):
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
"""
self._edge_types.extend(path._edge_types)
self._end = path._end
def __len__(self):
r"""
Returns the length of the path.
TEST::
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
"""
return len(self._edge_types)
def __getitem__(self, i):
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
"""
if i > len(self) or i < -len(self)-1:
raise IndexError, "path index out of range"
if i == 0: return self.start()
if i < 0: i = i + len(self) + 1
v = self._start
for k in range(i):
v = self._parent._succ[v][self._edge_types[k]]
return self._parent._vertex_to_permutation(v)
def __add__(self, other):
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
"""
if self._end != other._start:
raise ValueError, "The end of the first path is not the start of the second"
res = copy(self)
res._fast_extend(other)
return res
def __mul__(self, n):
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
"""
if not self.is_loop():
raise ValueError("Must be a loop to have multiple")
if not isinstance(n, (Integer,int)):
raise TypeError("The multiplier must be an integer")
if n < 0:
raise ValueError("The multiplier must be non negative")
res = copy(self)
for i in range(n-1):
res += self
return res
def is_loop(self):
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
"""
return self._start == self._end
def winners(self):
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']
"""
return self.composition(
self._parent.edge_to_winner,
list.__add__)
def losers(self):
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']
"""
return self.composition(
self._parent.edge_to_loser,
list.__add__)
def __iter__(self):
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, "\n*****"
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, "\n*****"
a b c
c b a
*****
a c b
c b a
*****
a c b
c b a
*****
"""
i = self._start
for edge_type in self._edge_types:
yield self._parent._vertex_to_permutation(i)
i = self._parent._succ[i][edge_type]
yield self.end()
def composition(self, function, composition = None):
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]
"""
result = function(None,None)
cur_vertex = self._start
p = self._parent._element
if composition is None: composition = result.__class__.__mul__
for i in self._edge_types:
self._parent._set_element(cur_vertex)
result = composition(result, function(p,i))
cur_vertex = self._parent._succ[cur_vertex][i]
return result
def right_composition(self, function, composition = None) :
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 (defaut None)
TEST::
sage: p = iet.Permutation('a b','b a')
sage: r = p.rauzy_diagram()
sage: def f(i,t):
... if t is None: return []
... return [t]
sage: g = r.path(p)
sage: g.right_composition(f,list.__add__)
[]
sage: g = r.path(p,0,1)
sage: g.right_composition(f, list.__add__)
[1, 0]
"""
result = function(None,None)
p = self._parent._element
cur_vertex = self._start
if composition is None: composition = result.__class__.__mul__
for i in self._edge_types:
self._parent._set_element(cur_vertex)
result = composition(function(p,i),result)
cur_vertex = self._parent._succ[cur_vertex][i]
return result
def __init__(self, p,
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')
sage: r2 = loads(dumps(r1))
"""
self._edge_types = []
self._index = {}
if right_induction is True:
self._index['rt_rauzy'] = len(self._edge_types)
self._edge_types.append(('rauzy_move',(0,-1)))
self._index['rb_rauzy'] = len(self._edge_types)
self._edge_types.append(('rauzy_move',(1,-1)))
elif isinstance(right_induction,str):
if right_induction == '':
raise ValueError, "right_induction can not be empty string"
elif 'top'.startswith(right_induction):
self._index['rt_rauzy'] = len(self._edge_types)
self._edge_types.append(('rauzy_move',(0,-1)))
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 is True:
self._index['lt_rauzy'] = len(self._edge_types)
self._edge_types.append(('rauzy_move',(0,0)))
self._index['lb_rauzy'] = len(self._edge_types)
self._edge_types.append(('rauzy_move',(1,0)))
elif isinstance(left_induction,str):
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)
if left_right_inversion is True:
self._index['lr_inverse'] = len(self._edge_types)
self._edge_types.append(('left_right_inverse',()))
if top_bottom_inversion is True:
self._index['tb_inverse'] = len(self._edge_types)
self._edge_types.append(('top_bottom_inverse',()))
if symmetric is True:
self._index['symmetric'] = len(self._edge_types)
self._edge_types.append(('symmetric',()))
self._n = len(p)
self._element_class = p.__class__
self._element = copy(p)
self._alphabet = self._element._alphabet
self._pred = {}
self._succ = {}
self.complete(p)
def __eq__(self, other):
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
"""
return (
type(self) == type(other) and
self._edge_types == other._edge_types and
self._succ.keys()[0] in other._succ)
def __ne__(self, other):
r"""
Tests difference.
TEST::
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
"""
return (
type(self) != type(other) or
self._edge_types != other._edge_types or
self._succ.keys()[0] not in other._succ)
def vertices(self):
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
"""
return map(
lambda x: self._vertex_to_permutation(x),
self._succ.keys())
def vertex_iterator(self):
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 itertools import ifilter
sage: r_1n = ifilter(lambda x: x.is_cylindric(), r)
sage: for p in r_1n: print p
a b c d
d c b a
"""
from itertools import imap
return imap(
lambda x: self._vertex_to_permutation(x),
self._succ.keys())
def edges(self,labels=True):
r"""
Returns a list of the edges.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a')
sage: len(r.edges())
2
"""
return list(self.edge_iterator())
def edge_iterator(self):
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
"""
for x in self._succ.keys():
for i,y in enumerate(self._succ[x]):
if y is not None:
yield(
(self._vertex_to_permutation(x),
self._vertex_to_permutation(y),
i))
def edge_types_index(self, data):
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
"""
if not isinstance(data,str):
raise ValueError, "the edge type must be a string"
if ('top_rauzy_move'.startswith(data) or
't_rauzy_move'.startswith(data)):
if self._index.has_key('lt_rauzy'):
if self._index.has_key('rt_rauzy'):
raise ValueError, "left and right inductions must be differentiated"
return self._index['lt_rauzy']
if self._index.has_key('rt_rauzy'):
return self._index['rt_rauzy']
raise ValueError, "no top induction in this Rauzy diagram"
if ('bottom_rauzy_move'.startswith(data) or
'b_rauzy_move'.startswith(data)):
if self._index.has_key('lb_rauzy'):
if self._index.has_key('rb_rauzy'):
raise ValueError, "left and right inductions must be differentiated"
return self._index['lb_rauzy']
if self._index.has_key('rb_rauzy'):
return self._index['rb_rauzy']
raise ValueError, "no bottom Rauzy induction in this diagram"
if ('left_rauzy_move'.startswith(data) or
'l_rauzy_move'.startswith(data)):
if self._index.has_key('lt_rauzy'):
if self._index.has_key('lb_rauzy'):
raise ValueError, "top and bottom inductions must be differentiated"
return self._index['lt_rauzy']
if self._index.has_key('lb_rauzy'):
return self._index('lb_rauzy')
raise ValueError, "no left Rauzy induction in this diagram"
if ('lt_rauzy_move'.startswith(data) or
'tl_rauzy_move'.startswith(data) or
'left_top_rauzy_move'.startswith(data) or
'top_left_rauzy_move'.startswith(data)):
if not self._index.has_key('lt_rauzy'):
raise ValueError, "no top-left Rauzy induction in this diagram"
else:
return self._index['lt_rauzy']
if ('lb_rauzy_move'.startswith(data) or
'bl_rauzy_move'.startswith(data) or
'left_bottom_rauzy_move'.startswith(data) or
'bottom_left_rauzy_move'.startswith(data)):
if not self._index.has_key('lb_rauzy'):
raise ValueError, "no bottom-left Rauzy induction in this diagram"
else:
return self._index['lb_rauzy']
if 'right'.startswith(data):
raise ValueError, "ambiguity with your edge name: %s" %(data)
if ('rt_rauzy_move'.startswith(data) or
'tr_rauzy_move'.startswith(data) or
'right_top_rauzy_move'.startswith(data) or
'top_right_rauzy_move'.startswith(data)):
if not self._index.has_key('rt_rauzy'):
raise ValueError, "no top-right Rauzy induction in this diagram"
else:
return self._index['rt_rauzy']
if ('rb_rauzy_move'.startswith(data) or
'br_rauzy_move'.startswith(data) or
'right_bottom_rauzy_move'.startswith(data) or
'bottom_right_rauzy_move'.startswith(data)):
if not self._index.has_key('rb_rauzy'):
raise ValueError, "no bottom-right Rauzy induction in this diagram"
else:
return self._index['rb_rauzy']
if 'symmetric'.startswith(data):
if not self._index.has_key('symmetric'):
raise ValueError, "no symmetric in this diagram"
else:
return self._index['symmetric']
if 'inversion'.startswith(data) or data == 'inverse':
if self._index.has_key('lr_inverse'):
if self._index.has_key('tb_inverse'):
raise ValueError, "left-right and top-bottom inversions must be differentiated"
return self._index['lr_inverse']
if self._index.has_key('tb_inverse'):
return self._index['tb_inverse']
raise ValueError, "no inversion in this diagram"
if ('lr_inversion'.startswith(data) or
data == 'lr_inverse' or
'left_right_inversion'.startswith(data) or
data == 'left_right_inverse'):
if not self._index.has_key('lr_inverse'):
raise ValueError, "no left-right inversion in this diagram"
else:
return self._index['lr_inverse']
if ('tb_inversion'.startswith(data) or
data == 'tb_inverse' or
'top_bottom_inversion'.startswith(data)
or data == 'top_bottom_inverse'):
if not self._index.has_key('tb_inverse'):
raise ValueError, "no top-bottom inversion in this diagram"
else:
return self._index['tb_inverse']
raise ValueError, "this edge type does not exist: %s" %(data)
def edge_types(self):
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()
"""
for i,(edge_type,t) in enumerate(self._edge_types):
print str(i) + ": " + edge_type + str(t)
def alphabet(self, data=None):
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
"""
if data is None:
return self._element._alphabet
else:
self._element._set_alphabet(data)
def letters(self):
r"""
Returns the letters used by the RauzyDiagram.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a')
sage: r.alphabet()
Ordered Alphabet ['a', 'b']
sage: r.letters()
['a', 'b']
sage: r.alphabet('ABCDEF')
sage: r.alphabet()
Ordered Alphabet ['A', 'B', 'C', 'D', 'E', 'F']
sage: r.letters()
['A', 'B']
"""
return self._element.letters()
def _vertex_to_permutation(self,data=None):
r"""
Converts the (vertex) data to a permutation.
TESTS:
sage: r = iet.RauzyDiagram('a b','b a') #indirect doctest
"""
if data is not None:
self._set_element(data)
return copy(self._element)
def edge_to_matrix(self, p=None, edge_type=None):
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: print d.edge_to_matrix(p,1)
[1 0 1]
[0 1 0]
[0 0 1]
"""
if p is None and edge_type is None:
return identity_matrix(self._n)
function_name = self._edge_types[edge_type][0] + '_matrix'
if not hasattr(self._element_class,function_name):
return identity_matrix(self._n)
arguments = self._edge_types[edge_type][1]
return getattr(p,function_name)(*arguments)
def edge_to_winner(self, p=None, edge_type=None):
r"""
Return the corresponding winner
TEST::
sage: r = iet.RauzyDiagram('a b','b a')
sage: r.edge_to_winner(None,None)
[]
"""
if p is None and edge_type is None:
return []
function_name = self._edge_types[edge_type][0] + '_winner'
if not hasattr(self._element_class, function_name):
return [None]
arguments = self._edge_types[edge_type][1]
return [getattr(p,function_name)(*arguments)]
def edge_to_loser(self, p=None, edge_type=None):
r"""
Return the corresponding loser
TEST::
sage: r = iet.RauzyDiagram('a b','b a')
sage: r.edge_to_loser(None,None)
[]
"""
if p is None and edge_type is None:
return []
function_name = self._edge_types[edge_type][0] + '_loser'
if not hasattr(self._element_class, function_name):
return [None]
arguments = self._edge_types[edge_type][1]
return [getattr(p,function_name)(*arguments)]
def _all_npath_extension(self, g, length=0):
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
"""
if length == 0:
yield g
else:
for i in range(len(self._edge_types)):
if self._succ[g._end][i] is not None:
g._fast_append(i)
for h in self._all_npath_extension(g,length-1): yield h
g.pop()
def _all_path_extension(self, g, length=0):
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
"""
yield g
if length > 0:
for i in range(len(self._edge_types)):
if self._succ[g._end][i] is not None:
g._fast_append(i)
for h in self._all_path_extension(g,length-1): yield h
g.pop()
def __iter__(self):
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)
"""
for data in self._succ.iterkeys():
yield self._vertex_to_permutation(data)
def __contains__(self, element):
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
"""
for p in self._succ.iterkeys():
if self._vertex_to_permutation(p) == element:
return True
return False
def _repr_(self):
r"""
Returns a representation of self
TEST::
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
"""
if len(self._succ) == 0:
return "Empty Rauzy diagram"
elif len(self._succ) == 1:
return "Rauzy diagram with 1 permutation"
else:
return "Rauzy diagram with %d permutations" %(len(self._succ))
def __getitem__(self,p):
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
"""
if not isinstance(p, self._element_class):
raise ValueError, "Your element does not have the good type"
perm = self._permutation_to_vertex(p)
return map(lambda x: self._vertex_to_permutation(x),
self._succ[perm])
def __len__(self):
r"""
Deprecated use cardinality.
EXAMPLES::
sage: r = iet.RauzyDiagram('a b','b a')
sage: r.cardinality()
1
"""
return self.cardinality()
def cardinality(self):
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
"""
return len(self._succ)
def complete(self, p):
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.
TEST::
sage: r = iet.RauzyDiagram('a b c','c b a') #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',left_induction=True) #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',symmetric=True) #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',lr_inversion=True) #indirect doctest
sage: r = iet.RauzyDiagram('a b c','c b a',tb_inversion=True) #indirect doctest
"""
if p.__class__ is not self._element_class:
raise ValueError, "your permutation is not of good type"
if len(p) != self._n:
raise ValueError, "your permutation has not the good length"
pred = self._pred
succ = self._succ
p = self._permutation_to_vertex(p)
perm = self._element
l = []
if not succ.has_key(p):
succ[p] = [None] * len(self._edge_types)
pred[p] = [None] * len(self._edge_types)
l.append(p)
while(l != []):
p = l.pop()
self._set_element(p)
for t,edge in enumerate(self._edge_types):
if (not hasattr(perm, 'has_'+edge[0]) or
getattr(perm, 'has_'+edge[0])(*(edge[1]))):
q = getattr(perm,edge[0])(*(edge[1]))
q = self._permutation_to_vertex(q)
if not succ.has_key(q):
succ[q] = [None] * len(self._edge_types)
pred[q] = [None] * len(self._edge_types)
l.append(q)
succ[p][t] = q
pred[q][t] = p
def path(self, *data):
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')
"""
if len(data) == 0:
raise TypeError("Must be non empty")
elif len(data) == 1 and isinstance(data[0], self.Path):
return copy(data[0])
return self.Path(self,*data)
def graph(self):
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
"""
G = DiGraph(loops=True,multiedges=True)
for p,neighbours in self._succ.iteritems():
p = self._vertex_to_permutation(p)
for i,n in enumerate(neighbours):
if n is not None:
q = self._vertex_to_permutation(n)
G.add_edge(p,q,i)
return G
class FlippedRauzyDiagram(RauzyDiagram):
r"""
Template for flipped Rauzy diagrams.
.. warning:
Internal class! Do not use directly!
AUTHORS:
- Vincent Delecroix (2009-09-29): initial version
"""
def complete(self, p, reducible=False):
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
"""
if p.__class__ is not self._element_class:
raise ValueError, "your permutation is not of good type"
if len(p) != self._n:
raise ValueError, "your permutation has not the good length"
pred = self._pred
succ = self._succ
p = self._permutation_to_vertex(p)
l = []
if not succ.has_key(p):
succ[p] = [None] * len(self._edge_types)
pred[p] = [None] * len(self._edge_types)
l.append(p)
while(l != []):
p = l.pop()
for t,edge_type in enumerate(self._edge_types):
perm = self._vertex_to_permutation(p)
if (not hasattr(perm,'has_' + edge_type[0]) or
getattr(perm, 'has_' + edge_type[0])(*(edge_type[1]))):
q = perm.rauzy_move(t)
q = self._permutation_to_vertex(q)
if reducible == True or perm.is_irreducible():
if not succ.has_key(q):
succ[q] = [None] * len(self._edge_types)
pred[q] = [None] * len(self._edge_types)
l.append(q)
succ[p][t] = q
pred[q][t] = p
