CoCalc -- labelled.py

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/dynamics/interval_exchanges/labelled.py
⁸⁸¹⁵ views
1
r"""
2
Labelled permutations
3

4
A labelled (generalized) permutation is better suited to study the
5
dynamic of a translation surface than a reduced one (see the module
6
:mod:`sage.dynamics.interval_exchanges.reduced`). The latter is more
7
adapted to the study of strata. This kind of permutation was
8
introduced by Yoccoz [Yoc05]_ (see also [MMY03]_).
9

10
In fact, there is a geometric counterpart of labelled
11
permutations. They correspond to translation surfaces with marked
12
outgoing separatrices (i.e. we fix a label for each of them).
13

14
Remarks that Rauzy diagram of reduced objects are significantly
15
smaller than the one for labelled object (for the permutation a b d b
16
e / e d c a c the labelled Rauzy diagram contains 8760 permutations,
17
and the reduced only 73).  But, as it is in geometrical way, the
18
labelled Rauzy diagram is a covering of the reduced Rauzy diagram.
19

20
AUTHORS:
21

22
- Vincent Delecroix (2009-09-29) : initial version
23

24
TESTS::
25

26
    sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationIET
27
    sage: LabelledPermutationIET([['a', 'b', 'c'], ['c', 'b', 'a']])
28
    a b c
29
    c b a
30
    sage: LabelledPermutationIET([[1,2,3,4],[4,1,2,3]])
31
    1 2 3 4
32
    4 1 2 3
33
    sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationLI
34
    sage: LabelledPermutationLI([[1,1],[2,2,3,3,4,4]])
35
    1 1
36
    2 2 3 3 4 4
37
    sage: LabelledPermutationLI([['a','a','b','b','c','c'],['d','d']])
38
    a a b b c c
39
    d d
40
    sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationIET
41
    sage: FlippedLabelledPermutationIET([[1,2,3],[3,2,1]],flips=[1,2])
42
    -1 -2  3
43
     3 -2 -1
44
    sage: FlippedLabelledPermutationIET([['a','b','c'],['b','c','a']],flips='b')
45
     a -b  c
46
    -b  c  a
47
    sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationLI
48
    sage: FlippedLabelledPermutationLI([[1,1],[2,2,3,3,4,4]], flips=[1,4])
49
    -1 -1
50
     2  2  3  3 -4 -4
51
    sage: FlippedLabelledPermutationLI([['a','a','b','b'],['c','c']],flips='ac')
52
    -a -a  b  b
53
    -c -c
54
    sage: from sage.dynamics.interval_exchanges.labelled import LabelledRauzyDiagram
55
    sage: p = LabelledPermutationIET([[1,2,3],[3,2,1]])
56
    sage: d1 = LabelledRauzyDiagram(p)
57
    sage: p = LabelledPermutationIET([['a','b'],['b','a']])
58
    sage: d = p.rauzy_diagram()
59
    sage: g1 = d.path(p, 'top', 'bottom')
60
    sage: g1.matrix()
61
    [1 1]
62
    [1 2]
63
    sage: g2 = d.path(p, 'bottom', 'top')
64
    sage: g2.matrix()
65
    [2 1]
66
    [1 1]
67
    sage: p = LabelledPermutationIET([['a','b','c','d'],['d','c','b','a']])
68
    sage: d = p.rauzy_diagram()
69
    sage: g = d.path(p, 't', 't', 'b', 't', 'b', 'b', 't', 'b')
70
    sage: g
71
    Path of length 8 in a Rauzy diagram
72
    sage: g.is_loop()
73
    True
74
    sage: g.is_full()
75
    True
76
    sage: s1 = g.orbit_substitution()
77
    sage: s1
78
    WordMorphism: a->adbd, b->adbdbd, c->adccd, d->adcd
79
    sage: s2 = g.interval_substitution()
80
    sage: s2
81
    WordMorphism: a->abcd, b->bab, c->cdc, d->dcbababcd
82
    sage: s1.incidence_matrix() == s2.incidence_matrix().transpose()
83
    True
84

85
REFERENCES:
86

87
.. [Yoc05] Jean-Christophe Yoccoz "Echange d'Intervalles", Cours au college de
88
   France
89

90
.. [MMY03] Jean-Christophe Yoccoz, Stefano Marmi and Pierre Moussa "On the
91
   cohomological equation for interval exchange maps", :arxiv:`math/0304469v1`
92
"""
93
#*****************************************************************************
94
#       Copyright (C) 2008 Vincent Delecroix <[email protected]>
95
#
96
#  Distributed under the terms of the GNU General Public License (GPL)
97
#                  http://www.gnu.org/licenses/
98
#*****************************************************************************
99

100
from sage.structure.sage_object import SageObject
101
from sage.misc.lazy_attribute import lazy_attribute
102

103
from copy import copy
104

105
from sage.combinat.words.alphabet import Alphabet
106
from sage.combinat.words.morphism import WordMorphism
107

108
from sage.matrix.constructor import identity_matrix
109
from sage.rings.integer import Integer
110

111
from template import PermutationIET, PermutationLI
112
from template import FlippedPermutationIET, FlippedPermutationLI
113
from template import twin_list_iet, twin_list_li
114
from template import RauzyDiagram, FlippedRauzyDiagram
115
from template import interval_conversion, side_conversion
116

117
class LabelledPermutation(SageObject):
118
    r"""
119
    General template for labelled objects.
120

121
    .. warning::
122

123
       Internal class! Do not use directly!
124
    """
125
    def __init__(self, intervals=None, alphabet=None):
126
        r"""
127
        TESTS::
128

129
            sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationIET
130
            sage: p1 = LabelledPermutationIET([[1,2,3],[3,2,1]])
131
            sage: p1 == loads(dumps(p1))
132
            True
133
            sage: p2 = LabelledPermutationIET([['a', 'b', 'c'], ['c', 'b', 'a']])
134
            sage: p2 == loads(dumps(p2))
135
            True
136
            sage: p3 = LabelledPermutationIET([['1','2','3'],['3','2','1']])
137
            sage: p3 == loads(dumps(p3))
138
            True
139
            sage: from sage.dynamics.interval_exchanges.labelled import LabelledPermutationLI
140
            sage: p1 = LabelledPermutationLI([[1,2,2],[3,3,1]])
141
            sage: p1 == loads(dumps(p1))
142
            True
143
            sage: p2 = LabelledPermutationLI([['a','b','b'],['c','c','a']])
144
            sage: p2 == loads(dumps(p2))
145
            True
146
            sage: p3 = LabelledPermutationLI([['1','2','2'],['3','3','1']])
147
            sage: p3 == loads(dumps(p3))
148
            True
149
        """
150
        self._hash = None
151

152
        if intervals is None:
153
            self._intervals = [[],[]]
154
            self._alphabet = None
155

156
        else:
157
            if alphabet is not None:
158
                alphabet = Alphabet(alphabet)
159
                if alphabet.cardinality() < len(intervals[0]) :
160
                    raise ValueError("the alphabet is too short")
161
                self._alphabet = alphabet
162

163
            else:
164
                self._init_alphabet(intervals)
165

166
            self._intervals = [
167
                map(self._alphabet.rank, intervals[0]),
168
                map(self._alphabet.rank, intervals[1])]
169

170
    def __copy__(self):
171
        r"""
172
        Returns a copy of self.
173

174
        TESTS::
175

176
            sage: p = iet.Permutation('a b c','c b a')
177
            sage: q = copy(p)
178
            sage: p == q
179
            True
180
            sage: p is q
181
            False
182
            sage: p._inversed()
183
            sage: p == q
184
            False
185
            sage: p._inversed()
186
            sage: p == q
187
            True
188
            sage: p._reversed()
189
            sage: p == q
190
            False
191
            sage: q._reversed()
192
            sage: p == q
193
            True
194
        """
195
        result = self.__class__()
196

197
        result._intervals = [
198
            copy(self._intervals[0]),
199
            copy(self._intervals[1])]
200

201
        result._alphabet = self._alphabet
202
        result._repr_type = self._repr_type
203
        result._repr_options = self._repr_options
204

205
        return result
206

207
    def __len__(self):
208
        r"""
209
        TESTS::
210

211
            sage: len(iet.Permutation('',''))
212
            0
213
            sage: len(iet.Permutation('a','a'))
214
            1
215
            sage: len(iet.Permutation('1 2 3 4 5 6','1 2 3 4 5 6'))
216
            6
217
        """
218
        return (len(self._intervals[0]) + len(self._intervals[1])) / 2
219

220
    def length_top(self):
221
        r"""
222
        Returns the number of intervals in the top segment.
223

224
        OUTPUT:
225

226
        integer -- number of intervals
227

228
        EXAMPLES::
229

230
            sage: iet.Permutation('a b c','c b a').length_top()
231
            3
232
            sage: iet.GeneralizedPermutation('a a','b b c c').length_top()
233
            2
234
            sage: iet.GeneralizedPermutation('a a b b','c c').length_top()
235
            4
236
        """
237
        return len(self._intervals[0])
238

239
    def length_bottom(self):
240
        r"""
241
        Returns the number of intervals in the bottom segment.
242

243
        OUTPUT:
244

245
        integer -- number of intervals
246

247
        EXAMPLES::
248

249
            sage: iet.Permutation('a b','b a').length_bottom()
250
            2
251
            sage: iet.GeneralizedPermutation('a a','b b c c').length_bottom()
252
            4
253
            sage: iet.GeneralizedPermutation('a a b b','c c').length_bottom()
254
            2
255
        """
256
        return len(self._intervals[1])
257

258
    def length(self, interval=None):
259
        r"""
260
        Returns a 2-uple of lengths.
261

262
        p.length() is identical to (p.length_top(), p.length_bottom())
263
        If an interval is specified, it returns the length of the specified
264
        interval.
265

266
        INPUT:
267

268
        - ``interval`` - ``None``, 'top' or 'bottom'
269

270
        OUTPUT:
271

272
        tuple -- a 2-uple of integers
273

274
        EXAMPLES::
275

276
            sage: iet.Permutation('a b c','c b a').length()
277
            (3, 3)
278
            sage: iet.GeneralizedPermutation('a a','b b c c').length()
279
            (2, 4)
280
            sage: iet.GeneralizedPermutation('a a b b','c c').length()
281
            (4, 2)
282
        """
283
        if interval is None:
284
            return len(self._intervals[0]),len(self._intervals[1])
285
        else:
286
            interval = interval_conversion(interval)
287
            return len(self._intervals[interval])
288

289
    def __getitem__(self,i):
290
        r"""
291
        TESTS::
292

293
            sage: p = iet.Permutation([0,1,2,3],[3,2,1,0])
294
            sage: p[0][0]
295
            0
296
            sage: p[1][2]
297
            1
298
            sage: p = iet.Permutation('a b c','c b a')
299
            sage: p[0][1]
300
            'b'
301
            sage: p[1][2]
302
            'a'
303
        """
304
        return map(self._alphabet.unrank, self._intervals[i])
305

306
    def __hash__(self):
307
        r"""
308
        ALGORITHM:
309

310
        Uses the hash of string
311

312
        TESTS::
313

314
            sage: from sage.dynamics.interval_exchanges.labelled import *
315
            sage: p1 = LabelledPermutationIET([[1,2],[1,2]])
316
            sage: p2 = LabelledPermutationIET([[1,2],[2,1]])
317
            sage: p3 = LabelledPermutationLI([[1,1],[2,2]])
318
            sage: hash(p1) == hash(p2)
319
            False
320
            sage: hash(p1) == hash(p3)
321
            False
322
            sage: hash(p2) == hash(p3)
323
            False
324
            sage: p1 = LabelledPermutationLI([[1,1], [2,2,3,3]])
325
            sage: p2 = LabelledPermutationLI([[1,1,2], [2,3,3]])
326
            sage: p3 = LabelledPermutationLI([[1,1,2,2], [3,3]])
327
            sage: hash(p1) == hash(p2)
328
            False
329
            sage: hash(p1) == hash(p3)
330
            False
331
            sage: hash(p2) == hash(p3)
332
            False
333
        """
334
        if self._hash is None:
335
            t = []
336
            t.extend([str(i) for i in self._intervals[0]])
337
            t.extend([str(-(i+1)) for i in self._intervals[1]])
338
            self._hash = hash(''.join(t))
339
        return self._hash
340

341
    def _reversed(self):
342
        r"""
343
        .. TODO::
344

345
            resolve properly the mutablility problem with the
346
            :meth:`_twin` attribute.
347

348
        TESTS::
349

350
            sage: p = iet.Permutation([1,2,3],[3,1,2])
351
            sage: p
352
            1 2 3
353
            3 1 2
354
            sage: p._reversed()
355
            sage: p
356
            3 2 1
357
            2 1 3
358
        """
359
        if self.__dict__.has_key('_twin'):
360
            del self.__dict__['_twin']
361
        if self._hash is not None:
362
            self._hash = None
363

364
        self._intervals[0].reverse()
365
        self._intervals[1].reverse()
366

367
    def _inversed(self):
368
        r"""
369
        .. TODO::
370

371
            properly resolve the mutability problem of the twin
372

373
        TESTS::
374

375
            sage: p = iet.Permutation([1,2,3],[3,1,2])
376
            sage: p
377
            1 2 3
378
            3 1 2
379
            sage: p._inversed()
380
            sage: p
381
            3 1 2
382
            1 2 3
383
        """
384
        if self.__dict__.has_key('_twin'):
385
            del self.__dict__['_twin']
386
        if self._hash is not None:
387
            self._hash = None
388

389
        self._intervals = (self._intervals[1],self._intervals[0])
390

391
    def list(self):
392
        r"""
393
        Returns a list of two lists corresponding to the intervals.
394

395
        OUTPUT:
396

397
        list -- two lists of labels
398

399
        EXAMPLES:
400

401
        The list of an permutation from iet::
402

403
            sage: p1 = iet.Permutation('1 2 3', '3 1 2')
404
            sage: p1.list()
405
            [['1', '2', '3'], ['3', '1', '2']]
406
            sage: p1.alphabet("abc")
407
            sage: p1.list()
408
            [['a', 'b', 'c'], ['c', 'a', 'b']]
409

410
        Recovering the permutation from this list (and the alphabet)::
411

412
            sage: q1 = iet.Permutation(p1.list(),alphabet=p1.alphabet())
413
            sage: p1 == q1
414
            True
415

416
        The list of a quadratic permutation::
417

418
            sage: p2 = iet.GeneralizedPermutation('g o o', 'd d g')
419
            sage: p2.list()
420
            [['g', 'o', 'o'], ['d', 'd', 'g']]
421

422
        Recovering the permutation::
423

424
            sage: q2 = iet.GeneralizedPermutation(p2.list(),alphabet=p2.alphabet())
425
            sage: p2 == q2
426
            True
427
        """
428
        a0 = map(self._alphabet.unrank, self._intervals[0])
429
        a1 = map(self._alphabet.unrank, self._intervals[1])
430
        return [a0, a1]
431

432
    def erase_letter(self, letter):
433
        r"""
434
        Return the permutation with the specified letter removed.
435

436
        OUTPUT:
437

438
        permutation -- the resulting permutation
439

440
        EXAMPLES:
441

442
        ::
443

444
            sage: p = iet.Permutation('a b c d','c d b a')
445
            sage: p.erase_letter('a')
446
            b c d
447
            c d b
448
            sage: p.erase_letter('b')
449
            a c d
450
            c d a
451
            sage: p.erase_letter('c')
452
            a b d
453
            d b a
454
            sage: p.erase_letter('d')
455
            a b c
456
            c b a
457

458
        ::
459

460
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
461
            sage: p.erase_letter('a')
462
            b b
463
            c c
464

465
        Beware, there is no validity check for permutation from linear
466
        involutions::
467

468
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
469
            sage: p.erase_letter('b')
470
            a
471
            c c a
472
        """
473
        l = [[], []]
474
        letters = self.letters()
475
        a = letters.index(letter)
476

477
        for i in (0, 1):
478
            for b in self._intervals[i]:
479
                if b < a:
480
                    l[i].append(b)
481
                elif b > a:
482
                    l[i].append(b-1)
483

484
        res = copy(self)
485
        res._intervals = l
486
        res.alphabet(letters[0:a] + letters[a+1:])
487

488
        return res
489

490
    def rauzy_move_matrix(self, winner=None, side='right'):
491
        r"""
492
        Returns the Rauzy move matrix.
493

494
        This matrix corresponds to the action of a Rauzy move on the
495
        vector of lengths. By convention (to get a positive matrix),
496
        the matrix is defined as the inverse transformation on the
497
        length vector.
498

499
        OUTPUT:
500

501
        matrix -- a square matrix of positive integers
502

503
        EXAMPLES:
504

505
        ::
506

507
            sage: p = iet.Permutation('a b','b a')
508
            sage: p.rauzy_move_matrix('t')
509
            [1 0]
510
            [1 1]
511
            sage: p.rauzy_move_matrix('b')
512
            [1 1]
513
            [0 1]
514

515
        ::
516

517
            sage: p = iet.Permutation('a b c d','b d a c')
518
            sage: q = p.left_right_inverse()
519
            sage: m0 = p.rauzy_move_matrix(winner='top',side='right')
520
            sage: n0 = q.rauzy_move_matrix(winner='top',side='left')
521
            sage: m0 == n0
522
            True
523
            sage: m1 = p.rauzy_move_matrix(winner='bottom',side='right')
524
            sage: n1 = q.rauzy_move_matrix(winner='bottom',side='left')
525
            sage: m1 == n1
526
            True
527
        """
528
        if winner is None and side is None:
529
            return identity_matrix(len(self))
530

531
        winner = interval_conversion(winner)
532
        side = side_conversion(side)
533

534
        winner_letter = self._intervals[winner][side]
535
        loser_letter = self._intervals[1-winner][side]
536

537
        m = copy(identity_matrix(len(self)))
538
        m[winner_letter, loser_letter] = 1
539

540
        return m
541

542
    def rauzy_move_winner(self, winner=None, side=None):
543
        r"""
544
        Returns the winner of a Rauzy move.
545

546
        INPUT:
547

548
        - ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
549

550
        - ``side`` - either 'left' or 'right' ('l' or 'r' for short)
551

552
        OUTPUT:
553

554
        -- a label
555

556
        EXAMPLES:
557

558
        ::
559

560
            sage: p = iet.Permutation('a b c d','b d a c')
561
            sage: p.rauzy_move_winner('top','right')
562
            'd'
563
            sage: p.rauzy_move_winner('bottom','right')
564
            'c'
565
            sage: p.rauzy_move_winner('top','left')
566
            'a'
567
            sage: p.rauzy_move_winner('bottom','left')
568
            'b'
569

570
        ::
571

572
            sage: p = iet.GeneralizedPermutation('a b b c','d c a e d e')
573
            sage: p.rauzy_move_winner('top','right')
574
            'c'
575
            sage: p.rauzy_move_winner('bottom','right')
576
            'e'
577
            sage: p.rauzy_move_winner('top','left')
578
            'a'
579
            sage: p.rauzy_move_winner('bottom','left')
580
            'd'
581
        """
582
        if winner is None and side is None:
583
            return None
584

585
        winner = interval_conversion(winner)
586
        side = side_conversion(side)
587

588
        return self[winner][side]
589

590
    def rauzy_move_loser(self,winner=None,side=None):
591
        r"""
592
        Returns the loser of a Rauzy move
593

594
        INPUT:
595

596
        - ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
597

598
        - ``side`` - either 'left' or 'right' ('l' or 'r' for short)
599

600
        OUTPUT:
601

602
        -- a label
603

604
        EXAMPLES::
605

606
            sage: p = iet.Permutation('a b c d','b d a c')
607
            sage: p.rauzy_move_loser('top','right')
608
            'c'
609
            sage: p.rauzy_move_loser('bottom','right')
610
            'd'
611
            sage: p.rauzy_move_loser('top','left')
612
            'b'
613
            sage: p.rauzy_move_loser('bottom','left')
614
            'a'
615
        """
616
        if winner is None and side is None:
617
            return None
618

619
        winner = interval_conversion(winner)
620
        side = side_conversion(side)
621

622
        return self[1-winner][side]
623

624
def LabelledPermutationsIET_iterator(nintervals=None,
625
                                     irreducible=True,
626
                                     alphabet=None):
627
    r"""
628
    Returns an iterator over labelled permutations.
629

630
    INPUT:
631

632
    - ``nintervals`` - integer or ``None``
633

634
    - ``irreducible`` - boolean (default: ``True``)
635

636
    - ``alphabet`` - something that should be converted to an alphabet
637
      of at least nintervals letters
638

639
    OUTPUT:
640

641
    iterator -- an iterator over permutations
642

643
    TESTS::
644

645
        sage: for p in iet.Permutations_iterator(2, alphabet="ab"):
646
        ....:     print p, "\n****"   #indirect doctest
647
        a b
648
        b a
649
        ****
650
        b a
651
        a b
652
        ****
653
        sage: for p in iet.Permutations_iterator(3, alphabet="abc"):
654
        ....:     print p, "\n*****"   #indirect doctest
655
        a b c
656
        b c a
657
        *****
658
        a b c
659
        c a b
660
        *****
661
        a b c
662
        c b a
663
        *****
664
        a c b
665
        b a c
666
        *****
667
        a c b
668
        b c a
669
        *****
670
        a c b
671
        c b a
672
        *****
673
        b a c
674
        a c b
675
        *****
676
        b a c
677
        c a b
678
        *****
679
        b a c
680
        c b a
681
        *****
682
        b c a
683
        a b c
684
        *****
685
        b c a
686
        a c b
687
        *****
688
        b c a
689
        c a b
690
        *****
691
        c a b
692
        a b c
693
        *****
694
        c a b
695
        b a c
696
        *****
697
        c a b
698
        b c a
699
        *****
700
        c b a
701
        a b c
702
        *****
703
        c b a
704
        a c b
705
        *****
706
        c b a
707
        b a c
708
        *****
709
    """
710
    from itertools import imap, ifilter, product
711
    from sage.combinat.permutation import Permutations
712

713
    if not irreducible:
714
        if nintervals is None:
715
            raise ValueError("choose a number of intervals")
716

717
        nintervals = Integer(nintervals)
718

719
        if not(nintervals > 0):
720
            raise ValueError("nintervals must be positive")
721

722
        f = lambda x: LabelledPermutationIET([list(x[0]),list(x[1])],alphabet=alphabet)
723

724
        alphabet = Alphabet(alphabet)
725
        g = lambda x: [alphabet.unrank(k-1) for k in x]
726
        P = map(g, Permutations(nintervals))
727
        return imap(f,product(P,P))
728
    else:
729
        return ifilter(
730
            lambda x: x.is_irreducible(),
731
            LabelledPermutationsIET_iterator(nintervals,False,alphabet))
732

733
class LabelledPermutationIET(LabelledPermutation, PermutationIET):
734
    """
735
    Labelled permutation for iet
736

737
    EXAMPLES:
738

739
    Reducibility testing::
740

741
        sage: p = iet.Permutation('a b c', 'c b a')
742
        sage: p.is_irreducible()
743
        True
744

745
        sage: q = iet.Permutation('a b c d', 'b a d c')
746
        sage: q.is_irreducible()
747
        False
748

749
    Rauzy movability and Rauzy move::
750

751
        sage: p = iet.Permutation('a b c', 'c b a')
752
        sage: p.has_rauzy_move('top')
753
        True
754
        sage: print p.rauzy_move('bottom')
755
        a c b
756
        c b a
757
        sage: p.has_rauzy_move('top')
758
        True
759
        sage: print p.rauzy_move('top')
760
        a b c
761
        c a b
762

763
    Rauzy diagram::
764

765
        sage: p = iet.Permutation('a b c', 'c b a')
766
        sage: d = p.rauzy_diagram()
767
        sage: p in d
768
        True
769
    """
770
    def __cmp__(self, other):
771
        r"""
772
        ALGORITHM:
773

774
        The order is lexicographic on intervals[0] + intervals[1]
775

776
        TESTS::
777
            sage: list_of_p2 = []
778
            sage: p0 = iet.Permutation('1 2', '1 2')
779
            sage: p1 = iet.Permutation('1 2', '2 1')
780
            sage: p0 != p0
781
            False
782
            sage: (p0 == p0) and (p0 < p1)
783
            True
784
            sage: (p1 > p0) and (p1 == p1)
785
            True
786
        """
787
        if type(self) != type(other):
788
            return -1
789

790
        n = len(self)
791
        if n != len(other):
792
            return n - len(other)
793

794
        i, j = 0, 0
795
        while (self._intervals[i][j] == other._intervals[i][j]):
796
            j += 1
797
            if j == n:
798
                if i == 1: return 0
799
                i = 1
800
                j = 0
801
        return self._intervals[i][j] - other._intervals[i][j]
802

803
    @lazy_attribute
804
    def _twin(self):
805
        r"""
806
        The twin relations of the permutation.
807

808
        TESTS::
809
            sage: p = iet.Permutation('a b','a b')
810
            sage: p._twin
811
            [[0, 1], [0, 1]]
812
            sage: p = iet.Permutation('a b','b a')
813
            sage: p._twin
814
            [[1, 0], [1, 0]]
815
        """
816
        return twin_list_iet(self._intervals)
817

818
    def reduced(self):
819
        r"""
820
        Returns the associated reduced abelian permutation.
821

822
        OUTPUT:
823

824
        a reduced permutation -- the underlying reduced permutation
825

826

827
        EXAMPLES::
828

829
            sage: p = iet.Permutation("a b c d","d c a b")
830
            sage: q = iet.Permutation("a b c d","d c a b",reduced=True)
831
            sage: p.reduced() == q
832
            True
833
        """
834
        from reduced import ReducedPermutationIET
835

836
        return ReducedPermutationIET(self.list(), alphabet=self._alphabet)
837

838
    def is_identity(self):
839
        r"""
840
        Returns True if self is the identity.
841

842
        OUTPUT:
843

844
        bool -- True if self corresponds to the identity
845

846
        EXAMPLES::
847

848
            sage: iet.Permutation("a b","a b").is_identity()
849
            True
850
            sage: iet.Permutation("a b","b a").is_identity()
851
            False
852
        """
853
        for i in range(len(self)):
854
            if self._intervals[0][i] != self._intervals[1][i]:
855
                return False
856
        return True
857

858
    def has_rauzy_move(self, winner=None, side=None):
859
        r"""
860
        Returns ``True`` if you can perform a Rauzy move.
861

862
        INPUT:
863

864
        - ``winner`` - the winner interval ('top' or 'bottom')
865

866
        - ``side`` - (default: 'right') the side ('left' or 'right')
867

868
        OUTPUT:
869

870
        bool -- ``True`` if self has a Rauzy move
871

872
        EXAMPLES:
873

874
        ::
875

876
            sage: p = iet.Permutation('a b','b a')
877
            sage: p.has_rauzy_move()
878
            True
879

880
        ::
881

882
            sage: p = iet.Permutation('a b c','b a c')
883
            sage: p.has_rauzy_move()
884
            False
885
        """
886
        if side is None:
887
            side = -1
888
        else:
889
            side = side_conversion(side)
890

891
        if not winner is None:
892
            winner = interval_conversion(winner)
893

894
        return self._intervals[0][side] != self._intervals[1][side]
895

896
    def rauzy_move(self, winner=None, side=None, iteration=1):
897
        r"""
898
        Returns the Rauzy move.
899

900
        INPUT:
901

902
        - ``winner`` - the winner interval ('top' or 'bottom')
903

904
        - ``side`` - (default: 'right') the side ('left' or 'right')
905

906
        OUTPUT:
907

908
        permutation -- the Rauzy move of the permutation
909

910
        EXAMPLES:
911

912
        ::
913

914
            sage: p = iet.Permutation('a b','b a')
915
            sage: p.rauzy_move('t','right')
916
            a b
917
            b a
918
            sage: p.rauzy_move('b','right')
919
            a b
920
            b a
921

922
        ::
923

924
            sage: p = iet.Permutation('a b c','c b a')
925
            sage: p.rauzy_move('t','right')
926
            a b c
927
            c a b
928
            sage: p.rauzy_move('b','right')
929
            a c b
930
            c b a
931

932
        ::
933

934
            sage: p = iet.Permutation('a b','b a')
935
            sage: p.rauzy_move('t','left')
936
            a b
937
            b a
938
            sage: p.rauzy_move('b','left')
939
            a b
940
            b a
941

942
        ::
943

944
            sage: p = iet.Permutation('a b c','c b a')
945
            sage: p.rauzy_move('t','left')
946
            a b c
947
            b c a
948
            sage: p.rauzy_move('b','left')
949
            b a c
950
            c b a
951
        """
952
        side = side_conversion(side)
953
        winner = interval_conversion(winner)
954

955
        result = copy(self)
956

957
        for i in range(iteration):
958
            winner_letter = result._intervals[winner][side]
959
            loser_letter = result._intervals[1-winner].pop(side)
960

961
            loser_to = result._intervals[1-winner].index(winner_letter) - side
962
            result._intervals[1-winner].insert(loser_to, loser_letter)
963

964
        return result
965

966
    def rauzy_move_interval_substitution(self,winner=None,side=None):
967
        r"""
968
        Returns the interval substitution associated.
969

970
        INPUT:
971

972
        - ``winner`` - the winner interval ('top' or 'bottom')
973

974
        - ``side`` - (default: 'right') the side ('left' or 'right')
975

976
        OUTPUT:
977

978
        WordMorphism -- a substitution on the alphabet of the permutation
979

980
        EXAMPLES::
981

982
            sage: p = iet.Permutation('a b','b a')
983
            sage: p.rauzy_move_interval_substitution('top','right')
984
            WordMorphism: a->a, b->ba
985
            sage: p.rauzy_move_interval_substitution('bottom','right')
986
            WordMorphism: a->ab, b->b
987
            sage: p.rauzy_move_interval_substitution('top','left')
988
            WordMorphism: a->ba, b->b
989
            sage: p.rauzy_move_interval_substitution('bottom','left')
990
            WordMorphism: a->a, b->ab
991
        """
992
        d = dict([(letter,letter) for letter in self.letters()])
993

994
        if winner is None and side is None:
995
            return WordMorphism(d)
996

997
        winner = interval_conversion(winner)
998
        side = side_conversion(side)
999

1000
        winner_letter = self.rauzy_move_winner(winner,side)
1001
        loser_letter = self.rauzy_move_loser(winner,side)
1002

1003
        if side == 0:
1004
            d[winner_letter] = [loser_letter,winner_letter]
1005
        else:
1006
            d[winner_letter] = [winner_letter,loser_letter]
1007

1008
        return WordMorphism(d)
1009

1010
    def rauzy_move_orbit_substitution(self,winner=None,side=None):
1011
        r"""
1012
        Return the action of the rauzy_move on the orbit.
1013

1014
        INPUT:
1015

1016
        - ``i`` - integer
1017

1018
        - ``winner`` - the winner interval ('top' or 'bottom')
1019

1020
        - ``side`` - (default: 'right') the side ('right' or 'left')
1021

1022
        OUTPUT:
1023

1024
        WordMorphism -- a substitution on the alphabet of self
1025

1026
        EXAMPLES::
1027

1028
            sage: p = iet.Permutation('a b','b a')
1029
            sage: p.rauzy_move_orbit_substitution('top','right')
1030
            WordMorphism: a->ab, b->b
1031
            sage: p.rauzy_move_orbit_substitution('bottom','right')
1032
            WordMorphism: a->a, b->ab
1033
            sage: p.rauzy_move_orbit_substitution('top','left')
1034
            WordMorphism: a->a, b->ba
1035
            sage: p.rauzy_move_orbit_substitution('bottom','left')
1036
            WordMorphism: a->ba, b->b
1037
        """
1038
        d = dict([(letter,letter) for letter in self.letters()])
1039

1040
        if winner is None and side is None:
1041
            return WordMorphism(d)
1042

1043
        winner = interval_conversion(winner)
1044
        side = side_conversion(side)
1045

1046

1047
        loser_letter = self.rauzy_move_loser(winner,side)
1048

1049
        top_letter = self.alphabet().unrank(self._intervals[0][side])
1050
        bottom_letter = self.alphabet().unrank(self._intervals[1][side])
1051

1052
        d[loser_letter] = [bottom_letter,top_letter]
1053

1054
        return WordMorphism(d)
1055

1056
    def rauzy_diagram(self, **args):
1057
        """
1058
        Returns the associated Rauzy diagram.
1059

1060
        For more information try help(iet.RauzyDiagram).
1061

1062
        OUTPUT:
1063

1064
        Rauzy diagram -- the Rauzy diagram of the permutation
1065

1066
        EXAMPLES::
1067

1068
            sage: p = iet.Permutation('a b c', 'c b a')
1069
            sage: d = p.rauzy_diagram()
1070
        """
1071
        return LabelledRauzyDiagram(self, **args)
1072

1073
class LabelledPermutationLI(LabelledPermutation, PermutationLI):
1074
    r"""
1075
    Labelled quadratic (or generalized) permutation
1076

1077
    EXAMPLES:
1078

1079
    Reducibility testing::
1080

1081
        sage: p = iet.GeneralizedPermutation('a b b', 'c c a')
1082
        sage: p.is_irreducible()
1083
        True
1084

1085
    Reducibility testing with associated decomposition::
1086

1087
        sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c')
1088
        sage: p.is_irreducible()
1089
        False
1090
        sage: test, decomposition = p.is_irreducible(return_decomposition = True)
1091
        sage: print test
1092
        False
1093
        sage: print decomposition
1094
        (['a'], ['c', 'a'], [], ['c'])
1095

1096
    Rauzy movability and Rauzy move::
1097

1098
        sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d')
1099
        sage: p.has_rauzy_move(0)
1100
        False
1101
        sage: p.has_rauzy_move(1)
1102
        True
1103
        sage: q = p.rauzy_move(1)
1104
        sage: print q
1105
        a a b b c
1106
        c d d
1107
        sage: q.has_rauzy_move(0)
1108
        True
1109
        sage: q.has_rauzy_move(1)
1110
        True
1111

1112
    Rauzy diagrams::
1113

1114
        sage: p = iet.GeneralizedPermutation('0 0 1 1','2 2')
1115
        sage: r = p.rauzy_diagram()
1116
        sage: p in r
1117
        True
1118
    """
1119
    def __cmp__(self, other):
1120
        r"""
1121
        ALGORITHM:
1122

1123
        Order is lexicographic on length of intervals and on intervals.
1124

1125
        TESTS::
1126
            sage: p0 = iet.GeneralizedPermutation('0 0','1 1 2 2')
1127
            sage: p1 = iet.GeneralizedPermutation('0 0','1 2 1 2')
1128
            sage: p2 = iet.GeneralizedPermutation('0 0','1 2 2 1')
1129
            sage: p3 = iet.GeneralizedPermutation('0 0 1','1 2 2')
1130
            sage: p4 = iet.GeneralizedPermutation('0 0 1 1','2 2')
1131
            sage: p5 = iet.GeneralizedPermutation('0 1 0 1','2 2')
1132
            sage: p6 = iet.GeneralizedPermutation('0 1 1 0','2 2')
1133
            sage: p0 == p0 and p0 < p1 and p0 < p2 and p0 < p3 and p0 < p4
1134
            True
1135
            sage: p0 < p5 and p0 < p6 and p1 < p2 and p1 < p3 and p1 < p4
1136
            True
1137
            sage: p1 < p5 and p1 < p6 and p2 < p3 and p2 < p4 and p2 < p5
1138
            True
1139
            sage: p2 < p6 and p3 < p4 and p3 < p5 and p3 < p6 and p4 < p5
1140
            True
1141
            sage: p4 < p6 and p5 < p6 and p0 == p0 and p1 == p1 and p2 == p2
1142
            True
1143
            sage: p3 == p3 and p4 == p4 and p5 == p5 and p6 == p6
1144
            True
1145
        """
1146
        if type(self) != type(other):
1147
            return -1
1148

1149
        n = len(self)
1150

1151
        if n != len(other): return n - len(other)
1152

1153
        l0 = self._intervals[0]
1154
        l1 = other._intervals[0]
1155

1156
        n = len(self._intervals[0])
1157

1158
        if n != len(other._intervals[0]): return n - len(other._intervals[0])
1159

1160
        i = 0
1161
        while (i < n) and (l0[i] == l1[i]):
1162
            i += 1
1163

1164
        if i != n:
1165
            return l0[i] - l1[i]
1166

1167
        l0 = self._intervals[1]
1168
        l1 = other._intervals[1]
1169
        n = len(self._intervals[1])
1170

1171
        i = 0
1172
        while (i < n) and (l0[i] == l1[i]):
1173
            i += 1
1174

1175
        if i != n:
1176
            return l0[i] - l1[i]
1177

1178
        return 0
1179

1180
    def has_right_rauzy_move(self, winner):
1181
        r"""
1182
        Test of Rauzy movability with a specified winner
1183

1184
        A quadratic (or generalized) permutation is rauzy_movable type
1185
        depending on the possible length of the last interval. It is
1186
        dependent of the length equation.
1187

1188
        INPUT:
1189

1190
        - ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
1191

1192
        OUTPUT:
1193

1194
        bool -- ``True`` if self has a Rauzy move
1195

1196
        EXAMPLES:
1197

1198
        ::
1199

1200
            sage: p = iet.GeneralizedPermutation('a a','b b')
1201
            sage: p.has_right_rauzy_move('top')
1202
            False
1203
            sage: p.has_right_rauzy_move('bottom')
1204
            False
1205

1206
        ::
1207

1208
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
1209
            sage: p.has_right_rauzy_move('top')
1210
            True
1211
            sage: p.has_right_rauzy_move('bottom')
1212
            True
1213

1214
        ::
1215

1216
            sage: p = iet.GeneralizedPermutation('a a','b b c c')
1217
            sage: p.has_right_rauzy_move('top')
1218
            True
1219
            sage: p.has_right_rauzy_move('bottom')
1220
            False
1221

1222
        ::
1223

1224
            sage: p = iet.GeneralizedPermutation('a a b b','c c')
1225
            sage: p.has_right_rauzy_move('top')
1226
            False
1227
            sage: p.has_right_rauzy_move('bottom')
1228
            True
1229
        """
1230
        winner = interval_conversion(winner)
1231
        loser = self._intervals[1-winner][-1]
1232

1233
        # the same letter at the right-end (False)
1234
        if self._intervals[0][-1] == self._intervals[1][-1] :
1235
            return False
1236

1237
        # the winner (or loser) letter is repeated on the other interval (True)
1238
        if self._intervals[0][-1] in self._intervals[1]: return True
1239
        if self._intervals[1][-1] in self._intervals[0]: return True
1240

1241
        # the loser letters is the only letter repeated in the loser
1242
        # interval (False)
1243
        for i,c in enumerate((self._intervals[1-winner])):
1244
            if c != loser and c in self._intervals[1-winner][i+1:]:
1245
                return True
1246

1247
        return False
1248

1249
    def right_rauzy_move(self, winner):
1250
        r"""
1251
        Perform a Rauzy move on the right (the standard one).
1252

1253
        INPUT:
1254

1255
        - ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
1256

1257
        OUTPUT:
1258

1259
        boolean -- ``True`` if self has a Rauzy move
1260

1261
        EXAMPLES:
1262

1263
        ::
1264

1265
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
1266
            sage: p.right_rauzy_move(0)
1267
            a a b
1268
            b c c
1269
            sage: p.right_rauzy_move(1)
1270
            a a
1271
            b b c c
1272

1273
        ::
1274

1275
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
1276
            sage: p.right_rauzy_move(0)
1277
            a a b b
1278
            c c
1279
            sage: p.right_rauzy_move(1)
1280
            a b b
1281
            c c a
1282

1283
        TESTS::
1284

1285
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
1286
            sage: q = p.top_bottom_inverse()
1287
            sage: q = q.right_rauzy_move(0)
1288
            sage: q = q.top_bottom_inverse()
1289
            sage: q == p.right_rauzy_move(1)
1290
            True
1291
            sage: q = p.top_bottom_inverse()
1292
            sage: q = q.right_rauzy_move(1)
1293
            sage: q = q.top_bottom_inverse()
1294
            sage: q == p.right_rauzy_move(0)
1295
            True
1296
            sage: p = p.left_right_inverse()
1297
            sage: q = q.left_rauzy_move(0)
1298
            sage: q = q.left_right_inverse()
1299
            sage: q == p.right_rauzy_move(0)
1300
            True
1301
            sage: q = p.left_right_inverse()
1302
            sage: q = q.left_rauzy_move(1)
1303
            sage: q = q.left_right_inverse()
1304
            sage: q == p.right_rauzy_move(1)
1305
            True
1306
        """
1307
        result = copy(self)
1308

1309
        winner_letter = result._intervals[winner][-1]
1310
        loser_letter = result._intervals[1-winner].pop(-1)
1311

1312
        if winner_letter in result._intervals[winner][:-1]:
1313
            loser_to = result._intervals[winner].index(winner_letter)
1314
            result._intervals[winner].insert(loser_to, loser_letter)
1315
        else:
1316
            loser_to = result._intervals[1-winner].index(winner_letter) + 1
1317
            result._intervals[1-winner].insert(loser_to, loser_letter)
1318

1319
        return result
1320

1321
    def left_rauzy_move(self, winner):
1322
        r"""
1323
        Perform a Rauzy move on the left.
1324

1325
        INPUT:
1326

1327
        - ``winner`` - 'top' or 'bottom'
1328

1329
        OUTPUT:
1330

1331
        permutation -- the Rauzy move of self
1332

1333
        EXAMPLES:
1334

1335
        ::
1336

1337
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
1338
            sage: p.left_rauzy_move(0)
1339
            a a b b
1340
            c c
1341
            sage: p.left_rauzy_move(1)
1342
            a a b
1343
            b c c
1344

1345
        ::
1346

1347
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
1348
            sage: p.left_rauzy_move(0)
1349
            a b b
1350
            c c a
1351
            sage: p.left_rauzy_move(1)
1352
            b b
1353
            c c a a
1354

1355

1356
        TESTS::
1357

1358
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
1359
            sage: q = p.top_bottom_inverse()
1360
            sage: q = q.left_rauzy_move(0)
1361
            sage: q = q.top_bottom_inverse()
1362
            sage: q == p.left_rauzy_move(1)
1363
            True
1364
            sage: q = p.top_bottom_inverse()
1365
            sage: q = q.left_rauzy_move(1)
1366
            sage: q = q.top_bottom_inverse()
1367
            sage: q == p.left_rauzy_move(0)
1368
            True
1369
            sage: q = p.left_right_inverse()
1370
            sage: q = q.right_rauzy_move(0)
1371
            sage: q = q.left_right_inverse()
1372
            sage: q == p.left_rauzy_move(0)
1373
            True
1374
            sage: q = p.left_right_inverse()
1375
            sage: q = q.right_rauzy_move(1)
1376
            sage: q = q.left_right_inverse()
1377
            sage: q == p.left_rauzy_move(1)
1378
            True
1379
        """
1380
        result = copy(self)
1381

1382
        winner_letter = result._intervals[winner][0]
1383
        loser_letter = result._intervals[1-winner].pop(0)
1384

1385
        if winner_letter in result._intervals[winner][1:]:
1386
            loser_to = result._intervals[winner][1:].index(winner_letter)+2
1387
            result._intervals[winner].insert(loser_to, loser_letter)
1388

1389
        else:
1390
            loser_to = result._intervals[1-winner].index(winner_letter)
1391
            result._intervals[1-winner].insert(loser_to, loser_letter)
1392

1393
        return result
1394

1395
    def reduced(self):
1396
        r"""
1397
        Returns the associated reduced quadratic permutations.
1398

1399
        OUTPUT:
1400

1401
        permutation -- the underlying reduced permutation
1402

1403
        EXAMPLES::
1404

1405
            sage: p = iet.GeneralizedPermutation('a a','b b c c')
1406
            sage: q = p.reduced()
1407
            sage: q
1408
            a a
1409
            b b c c
1410
            sage: p.rauzy_move(0).reduced() == q.rauzy_move(0)
1411
            True
1412
        """
1413
        from reduced import ReducedPermutationLI
1414

1415
        return ReducedPermutationLI(self.list(),alphabet=self._alphabet)
1416

1417
    def rauzy_diagram(self, **kargs):
1418
        r"""
1419
        Returns the associated RauzyDiagram.
1420

1421
        OUTPUT:
1422

1423
        Rauzy diagram -- the Rauzy diagram of the permutation
1424

1425
        EXAMPLES::
1426

1427
            sage: p = iet.GeneralizedPermutation('a b c b', 'c d d a')
1428
            sage: d = p.rauzy_diagram()
1429
            sage: p in d
1430
            True
1431

1432
        For more information, try help(iet.RauzyDiagram)
1433
        """
1434
        return LabelledRauzyDiagram(self, **kargs)
1435

1436
    @lazy_attribute
1437
    def _twin(self):
1438
        r"""
1439
        The twin list of the permutation
1440

1441
        TEST::
1442

1443
            sage: p = iet.GeneralizedPermutation('a a','b b')
1444
            sage: p._twin
1445
            [[(0, 1), (0, 0)], [(1, 1), (1, 0)]]
1446
        """
1447
        return twin_list_li(self._intervals)
1448

1449
class FlippedLabelledPermutation(LabelledPermutation):
1450
    r"""
1451
    General template for labelled objects
1452

1453
    .. warning::
1454

1455
       Internal class! Do not use directly!
1456
    """
1457
    def __init__(self, intervals=None, alphabet=None, flips=None):
1458
        r"""
1459
        INPUT:
1460

1461
        - `intervals` - the intervals as a list of two lists
1462

1463
        - `alphabet` - something that should be converted to an alphabe
1464

1465
        - `flips` - a list of letters of the alphabet
1466

1467
        TESTS:
1468

1469
        ::
1470

1471
            sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationIET
1472
            sage: p = FlippedLabelledPermutationIET([['a','b'],['a','b']],flips='a')
1473
            sage: p == loads(dumps(p))
1474
            True
1475
            sage: p = FlippedLabelledPermutationIET([['a','b'],['b','a']],flips='ab')
1476
            sage: p == loads(dumps(p))
1477
            True
1478

1479
        ::
1480

1481
            sage: from sage.dynamics.interval_exchanges.labelled import FlippedLabelledPermutationLI
1482
            sage: p = FlippedLabelledPermutationLI([['a','a','b'],['b','c','c']],flips='a')
1483
            sage: p == loads(dumps(p))
1484
            True
1485
            sage: p = FlippedLabelledPermutationLI([['a','a'],['b','b','c','c']],flips='ac')
1486
            sage: p == loads(dumps(p))
1487
            True
1488
        """
1489
        if intervals is None:
1490
            intervals = [[], []]
1491
        if flips is None: flips = []
1492

1493
        super(FlippedLabelledPermutation, self).__init__(intervals, alphabet)
1494
        self._init_flips(intervals, flips)
1495

1496
    def __copy__(self):
1497
        r"""
1498
        Returns a copy of ``self``
1499

1500
        TESTS::
1501

1502
            sage: p = iet.Permutation('a b c','c b a',flips='a')
1503
            sage: h = hash(p)
1504
            sage: t = p._twin
1505
            sage: q = copy(p)
1506
            sage: q == p
1507
            True
1508
            sage: q is p
1509
            False
1510
            sage: q._twin is p._twin
1511
            False
1512
        """
1513
        result = self.__class__()
1514

1515
        result._intervals = [self._intervals[0][:],
1516
                             self._intervals[1][:]]
1517
        result._flips = [self._flips[0][:],
1518
                         self._flips[1][:]]
1519

1520
        result._alphabet = self._alphabet
1521
        result._repr_type = self._repr_type
1522
        result._repr_options = self._repr_options
1523

1524
        return result
1525

1526
    def list(self, flips=False):
1527
        r"""
1528
        Returns a list associated to the permutation.
1529

1530
        INPUT:
1531

1532
        - ``flips`` - boolean (default: ``False``)
1533

1534
        OUTPUT:
1535

1536
        list -- two lists of labels
1537

1538
        EXAMPLES::
1539

1540
            sage: p = iet.GeneralizedPermutation('0 0 1 2 2 1', '3 3', flips='1')
1541
            sage: p.list(flips=True)
1542
            [[('0', 1), ('0', 1), ('1', -1), ('2', 1), ('2', 1), ('1', -1)], [('3', 1), ('3', 1)]]
1543
            sage: p.list(flips=False)
1544
            [['0', '0', '1', '2', '2', '1'], ['3', '3']]
1545

1546
        The list can be used to reconstruct the permutation
1547

1548
        ::
1549

1550
            sage: p = iet.Permutation('a b c','c b a',flips='ab')
1551
            sage: p == iet.Permutation(p.list(), flips=p.flips())
1552
            True
1553

1554
        ::
1555

1556
            sage: p = iet.GeneralizedPermutation('a b b c','c d d a',flips='ad')
1557
            sage: p == iet.GeneralizedPermutation(p.list(),flips=p.flips())
1558
            True
1559
        """
1560
        if flips:
1561
            a0 = zip(map(self._alphabet.unrank, self._intervals[0]), self._flips[0])
1562
            a1 = zip(map(self._alphabet.unrank, self._intervals[1]), self._flips[1])
1563
        else:
1564
            a0 = map(self._alphabet.unrank, self._intervals[0])
1565
            a1 = map(self._alphabet.unrank, self._intervals[1])
1566

1567
        return [a0,a1]
1568

1569
    def __getitem__(self,i):
1570
        r"""
1571
        Get labels and flips of specified interval.
1572

1573
        The result is a 2-uple (letter, flip) where letter is the name of the
1574
        sub-interval and flip is a number corresponding to the presence of flip
1575
        as following: 1 (no flip) and -1 (a flip).
1576

1577
        EXAMPLES::
1578

1579
            sage: p = iet.Permutation('a b', 'b a', flips='a')
1580
            sage: print p[0]
1581
            [('a', -1), ('b', 1)]
1582
            sage: p = iet.GeneralizedPermutation('c p p', 't t c', flips='ct')
1583
            sage: print p[1]
1584
            [('t', -1), ('t', -1), ('c', -1)]
1585
        """
1586
        if not isinstance(i, (Integer, int)):
1587
            raise TypeError("Must be an integer")
1588
        if i != 0 and i != 1:
1589
            raise IndexError("The integer must be 0 or 1")
1590

1591
        letters = map(self._alphabet.unrank, self._intervals[i])
1592
        flips = self._flips[i]
1593

1594
        return zip(letters,flips)
1595

1596
    def __eq__(self,other):
1597
        r"""
1598
        Test of equality
1599

1600
        ALGORITHM:
1601

1602
        not considering the alphabet used for the representation but just the
1603
        order
1604

1605
        TESTS::
1606

1607
            sage: p1 = iet.Permutation('a b c','c b a',flips='a')
1608
            sage: p2 = iet.Permutation('a b c','c b a',flips='b')
1609
            sage: p3 = iet.Permutation('d e f','f e d',flips='d')
1610
            sage: p1 == p1 and p2 == p2 and p3 == p3
1611
            True
1612
            sage: p1 == p2
1613
            False
1614
            sage: p1 == p3
1615
            True
1616
        """
1617
        return (
1618
            type(self) == type(other) and
1619
            self._intervals == other._intervals and
1620
            self._flips == other._flips)
1621

1622
    def __ne__(self,other):
1623
        r"""
1624
        Test of difference
1625

1626
        ALGORITHM:
1627

1628
        not considering the alphabet used for the representation
1629

1630
        TESTS::
1631

1632
            sage: p1 = iet.Permutation('a b c','c b a',flips='a')
1633
            sage: p2 = iet.Permutation('a b c','c b a',flips='b')
1634
            sage: p3 = iet.Permutation('d e f','f e d',flips='d')
1635
            sage: p1 != p1 or p2 != p2 or p3 != p3
1636
            False
1637
            sage: p1 != p2
1638
            True
1639
            sage: p1 != p3
1640
            False
1641
        """
1642
        return (
1643
            type(self) != type(other) or
1644
            self._intervals != other._intervals or
1645
            self._flips != other._flips)
1646

1647
    def _inversed(self):
1648
        r"""
1649
        Inversion of the permutation (called by tb_inverse).
1650

1651
        .. TODO::
1652

1653
            Resolve properly the mutability problem associated to hash
1654
            value and twin list.
1655

1656
        TESTS::
1657

1658
            sage: p = iet.Permutation('a','a',flips='a')
1659
            sage: p.tb_inverse()   #indirect doctest
1660
            -a
1661
            -a
1662
            sage: p = iet.Permutation('a b','a b',flips='a')
1663
            sage: p.tb_inverse()   #indirect doctest
1664
            -a b
1665
            -a b
1666
            sage: p = iet.Permutation('a b','a b',flips='b')
1667
            sage: p.tb_inverse()   #indirect doctest
1668
             a -b
1669
             a -b
1670
            sage: p = iet.Permutation('a b','b a',flips='a')
1671
            sage: p.tb_inverse()   #indirect doctest
1672
             b -a
1673
            -a  b
1674
            sage: p = iet.Permutation('a b','b a',flips='b')
1675
            sage: p.tb_inverse()   #indirect doctest
1676
            -b  a
1677
             a -b
1678
        """
1679
        if hasattr(self, '_twin'):
1680
            delattr(self, '_twin')
1681

1682
        if self._hash is not None:
1683
            self._hash = None
1684

1685
        self._intervals.reverse()
1686
        self._flips.reverse()
1687

1688
    def _reversed(self):
1689
        r"""
1690
        Reverses the permutation (called by lr_inverse)
1691

1692
        .. TODO::
1693

1694
            Resolve properly the mutability problem with _twin list
1695
            and the hash value.
1696

1697
        TESTS::
1698

1699
            sage: p = iet.Permutation('a','a',flips='a')
1700
            sage: p.lr_inverse()   #indirect doctest
1701
            -a
1702
            -a
1703
            sage: p = iet.Permutation('a b','a b',flips='a')
1704
            sage: p.lr_inverse()   #indirect doctest
1705
             b -a
1706
             b -a
1707
            sage: p = iet.Permutation('a b','a b',flips='b')
1708
            sage: p.lr_inverse()   #indirect doctest
1709
            -b a
1710
            -b a
1711
            sage: p = iet.Permutation('a b','b a',flips='a')
1712
            sage: p.lr_inverse()   #indirect doctest
1713
             b -a
1714
            -a  b
1715
            sage: p = iet.Permutation('a b','b a',flips='b')
1716
            sage: p.lr_inverse()   #indirect doctest
1717
            -b  a
1718
             a -b
1719
        """
1720
        if hasattr(self, '_twin'):
1721
            delattr(self, '_twin')
1722

1723
        if self._hash is not None:
1724
            self._hash is None
1725

1726
        self._intervals[0].reverse()
1727
        self._intervals[1].reverse()
1728
        self._flips[0].reverse()
1729
        self._flips[1].reverse()
1730

1731
class FlippedLabelledPermutationIET(
1732
    FlippedLabelledPermutation,
1733
    FlippedPermutationIET,
1734
    LabelledPermutationIET):
1735
    r"""
1736
    Flipped labelled permutation from iet.
1737

1738
    EXAMPLES:
1739

1740
    Reducibility testing (does not depends of flips)::
1741

1742
        sage: p = iet.Permutation('a b c', 'c b a',flips='a')
1743
        sage: p.is_irreducible()
1744
        True
1745
        sage: q = iet.Permutation('a b c d', 'b a d c', flips='bc')
1746
        sage: q.is_irreducible()
1747
        False
1748

1749
    Rauzy movability and Rauzy move::
1750

1751
        sage: p = iet.Permutation('a b c', 'c b a',flips='a')
1752
        sage: print p
1753
        -a  b  c
1754
         c  b -a
1755
        sage: print p.rauzy_move(1)
1756
        -c -a  b
1757
        -c  b -a
1758
        sage: print p.rauzy_move(0)
1759
        -a  b  c
1760
         c -a  b
1761

1762
    Rauzy diagrams::
1763

1764
        sage: d = iet.RauzyDiagram('a b c d','d a b c',flips='a')
1765

1766
    AUTHORS:
1767

1768
    - Vincent Delecroix (2009-09-29): initial version
1769
    """
1770
    def reduced(self):
1771
        r"""
1772
        The associated reduced permutation.
1773

1774
        OUTPUT:
1775

1776
        permutation -- the associated reduced permutation
1777

1778
        EXAMPLES::
1779

1780
            sage: p = iet.Permutation('a b c','c b a',flips='a')
1781
            sage: q = iet.Permutation('a b c','c b a',flips='a',reduced=True)
1782
            sage: p.reduced() == q
1783
            True
1784
        """
1785
        from sage.dynamics.interval_exchanges.reduced import FlippedReducedPermutationIET
1786

1787
        return FlippedReducedPermutationIET(
1788
            intervals=self.list(flips=False),
1789
            flips=self.flips(),
1790
            alphabet=self.alphabet())
1791

1792
    def __hash__(self):
1793
        r"""
1794
        ALGORITHM:
1795

1796
        Uses hash of string
1797

1798
        TESTS::
1799

1800
            sage: p =[]
1801
            sage: p.append(iet.Permutation('a b','a b',flips='a'))
1802
            sage: p.append(iet.Permutation('a b','a b',flips='b'))
1803
            sage: p.append(iet.Permutation('a b','a b',flips='ab'))
1804
            sage: p.append(iet.Permutation('a b','b a',flips='a'))
1805
            sage: p.append(iet.Permutation('a b','b a',flips='b'))
1806
            sage: p.append(iet.Permutation('a b','b a',flips='ab'))
1807
            sage: h = map(hash, p)
1808
            sage: for i in range(len(h)-1):
1809
            ....:     if h[i] == h[i+1]:
1810
            ....:         print "You choose a bad hash!"
1811
        """
1812
        if self._hash is None:
1813
            f = self._flips
1814
            i = self._intervals
1815
            l = []
1816
            l.extend([str(j*(1+k)) for j,k in zip(f[0],i[0])])
1817
            l.extend([str(-j*(1+k)) for j,k in zip(f[1],i[1])])
1818
            self._hash = hash(''.join(l))
1819

1820
        return self._hash
1821

1822
    def rauzy_move(self,winner=None,side=None):
1823
        r"""
1824
        Returns the Rauzy move.
1825

1826
        INPUT:
1827

1828
        - ``winner`` - 'top' (or 't' or 0) or 'bottom' (or 'b' or 1)
1829

1830
        - ``side`` - (default: 'right') 'right' (or 'r') or 'left' (or 'l')
1831

1832
        OUTPUT:
1833

1834
        permutation -- the Rauzy move of ``self``
1835

1836
        EXAMPLES:
1837

1838
        ::
1839

1840
            sage: p = iet.Permutation('a b','b a',flips='a')
1841
            sage: p.rauzy_move('top')
1842
            -a  b
1843
             b -a
1844
            sage: p.rauzy_move('bottom')
1845
            -b -a
1846
            -b -a
1847

1848
        ::
1849

1850
            sage: p = iet.Permutation('a b c','c b a',flips='b')
1851
            sage: p.rauzy_move('top')
1852
             a -b  c
1853
             c  a -b
1854
            sage: p.rauzy_move('bottom')
1855
             a  c -b
1856
             c -b  a
1857
        """
1858
        winner = interval_conversion(winner)
1859
        side = side_conversion(side)
1860

1861
        result = copy(self)
1862

1863
        winner_letter = result._intervals[winner][side]
1864
        loser_letter = result._intervals[1-winner].pop(side)
1865

1866
        winner_flip = result._flips[winner][side]
1867
        loser_flip = result._flips[1-winner].pop(side)
1868

1869
        loser_twin = result._intervals[winner].index(loser_letter)
1870
        result._flips[winner][loser_twin] = winner_flip * loser_flip
1871

1872
        loser_to = result._intervals[1-winner].index(winner_letter) - side
1873
        if winner_flip == -1: loser_to += 1 + 2*side
1874

1875
        result._intervals[1-winner].insert(loser_to, loser_letter)
1876
        result._flips[1-winner].insert(loser_to, winner_flip * loser_flip)
1877

1878
        return result
1879

1880
    def rauzy_diagram(self, **kargs):
1881
        r"""
1882
        Returns the Rauzy diagram associated to this permutation.
1883

1884
        For more information, try help(iet.RauzyDiagram)
1885

1886
        OUTPUT:
1887

1888
        RauzyDiagram -- the Rauzy diagram of ``self``
1889

1890
        EXAMPLES::
1891

1892
            sage: p = iet.Permutation('a b c', 'c b a',flips='a')
1893
            sage: p.rauzy_diagram()
1894
            Rauzy diagram with 3 permutations
1895
        """
1896
        return FlippedLabelledRauzyDiagram(self, **kargs)
1897

1898
class FlippedLabelledPermutationLI(FlippedLabelledPermutation,
1899
                                   FlippedPermutationLI,
1900
                                   LabelledPermutationLI):
1901
    r"""
1902
    Flipped labelled quadratic (or generalized) permutation.
1903

1904
    EXAMPLES:
1905

1906
    Reducibility testing::
1907

1908
        sage: p = iet.GeneralizedPermutation('a b b', 'c c a', flips='a')
1909
        sage: p.is_irreducible()
1910
        True
1911

1912
    Reducibility testing with associated decomposition::
1913

1914
        sage: p = iet.GeneralizedPermutation('a b c a', 'b d d c', flips='ab')
1915
        sage: p.is_irreducible()
1916
        False
1917
        sage: test, decomp = p.is_irreducible(return_decomposition = True)
1918
        sage: print test
1919
        False
1920
        sage: print decomp
1921
        (['a'], ['c', 'a'], [], ['c'])
1922

1923
    Rauzy movability and Rauzy move::
1924

1925
        sage: p = iet.GeneralizedPermutation('a a b b c c', 'd d', flips='d')
1926
        sage: p.has_rauzy_move(0)
1927
        False
1928
        sage: p.has_rauzy_move(1)
1929
        True
1930
        sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
1931
        sage: p.has_rauzy_move(0)
1932
        True
1933
        sage: p.has_rauzy_move(1)
1934
        True
1935
    """
1936
    def reduced(self):
1937
        r"""
1938
        The associated reduced permutation.
1939

1940
        OUTPUT:
1941

1942
        permutation -- the associated reduced permutation
1943

1944
        EXAMPLE::
1945

1946
            sage: p = iet.GeneralizedPermutation('a a','b b c c',flips='a')
1947
            sage: q = iet.GeneralizedPermutation('a a','b b c c',flips='a',reduced=True)
1948
            sage: p.reduced() == q
1949
            True
1950
        """
1951
        from sage.dynamics.interval_exchanges.reduced import FlippedReducedPermutationLI
1952

1953
        return FlippedReducedPermutationLI(
1954
            intervals=self.list(flips=False),
1955
            flips=self.flips(),
1956
            alphabet=self.alphabet())
1957

1958
    def right_rauzy_move(self, winner):
1959
        r"""
1960
        Perform a Rauzy move on the right (the standard one).
1961

1962
        INPUT:
1963

1964
        - ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
1965

1966
        OUTPUT:
1967

1968
        permutation -- the Rauzy move of ``self``
1969

1970
        EXAMPLES:
1971

1972
        ::
1973

1974
            sage: p = iet.GeneralizedPermutation('a a b','b c c',flips='c')
1975
            sage: p.right_rauzy_move(0)
1976
             a  a  b
1977
            -c  b -c
1978
            sage: p.right_rauzy_move(1)
1979
             a  a
1980
            -b -c -b -c
1981

1982
        ::
1983

1984
            sage: p = iet.GeneralizedPermutation('a b b','c c a',flips='ab')
1985
            sage: p.right_rauzy_move(0)
1986
             a -b  a -b
1987
             c  c
1988
            sage: p.right_rauzy_move(1)
1989
             b -a  b
1990
             c  c -a
1991
        """
1992
        result = copy(self)
1993

1994
        winner_letter = result._intervals[winner][-1]
1995
        winner_flip = result._flips[winner][-1]
1996

1997
        loser_letter = result._intervals[1-winner].pop(-1)
1998
        loser_flip = result._flips[1-winner].pop(-1)
1999

2000
        if loser_letter in result._intervals[winner]:
2001
            loser_twin = result._intervals[winner].index(loser_letter)
2002
            result._flips[winner][loser_twin] = loser_flip*winner_flip
2003
        else:
2004
            loser_twin = result._intervals[1-winner].index(loser_letter)
2005
            result._flips[1-winner][loser_twin] = loser_flip*winner_flip
2006

2007
        if winner_letter in result._intervals[winner][:-1]:
2008
            loser_to = result._intervals[winner].index(winner_letter)
2009
            if winner_flip == -1: loser_to += 1
2010
            result._intervals[winner].insert(loser_to, loser_letter)
2011
            result._flips[winner].insert(loser_to, loser_flip*winner_flip)
2012
        else:
2013
            loser_to = result._intervals[1-winner].index(winner_letter)
2014
            if loser_flip == 1: loser_to += 1
2015
            result._intervals[1-winner].insert(loser_to, loser_letter)
2016
            result._flips[1-winner].insert(loser_to, loser_flip*winner_flip)
2017

2018
        return result
2019

2020
    def left_rauzy_move(self, winner):
2021
        r"""
2022
        Perform a Rauzy move on the left.
2023

2024
        INPUT:
2025

2026
        - ``winner`` - either 'top' or 'bottom' ('t' or 'b' for short)
2027

2028
        OUTPUT:
2029

2030
        -- a permutation
2031

2032
        EXAMPLES:
2033

2034
        ::
2035

2036
            sage: p = iet.GeneralizedPermutation('a a b','b c c')
2037
            sage: p.left_rauzy_move(0)
2038
            a a b b
2039
            c c
2040
            sage: p.left_rauzy_move(1)
2041
            a a b
2042
            b c c
2043

2044
        ::
2045

2046
            sage: p = iet.GeneralizedPermutation('a b b','c c a')
2047
            sage: p.left_rauzy_move(0)
2048
            a b b
2049
            c c a
2050
            sage: p.left_rauzy_move(1)
2051
            b b
2052
            c c a a
2053
        """
2054
        result = copy(self)
2055

2056
        winner_letter = result._intervals[winner][0]
2057
        loser_letter = result._intervals[1-winner].pop(0)
2058

2059
        if winner_letter in result._intervals[winner][1:]:
2060
            loser_to = result._intervals[winner][1:].index(winner_letter)+2
2061
            result._intervals[winner].insert(loser_to, loser_letter)
2062

2063
        else:
2064
            loser_to = result._intervals[1-winner].index(winner_letter)
2065
            result._intervals[1-winner].insert(loser_to, loser_letter)
2066

2067
        return result
2068

2069
    def rauzy_diagram(self, **kargs):
2070
        r"""
2071
        Returns the associated Rauzy diagram.
2072

2073
        For more information, try help(RauzyDiagram)
2074

2075
        OUTPUT :
2076

2077
        -- a RauzyDiagram
2078

2079
        EXAMPLES::
2080

2081
            sage: p = iet.GeneralizedPermutation('a b b a', 'c d c d')
2082
            sage: d = p.rauzy_diagram()
2083
        """
2084
        return FlippedLabelledRauzyDiagram(self, **kargs)
2085

2086
class LabelledRauzyDiagram(RauzyDiagram):
2087
    r"""
2088
    Template for Rauzy diagrams of labelled permutations.
2089

2090
    .. WARNING::
2091

2092
        DO NOT USE
2093
    """
2094
    class Path(RauzyDiagram.Path):
2095
        r"""
2096
        Path in Labelled Rauzy diagram.
2097
        """
2098
        def matrix(self):
2099
            r"""
2100
            Returns the matrix associated to a path.
2101

2102
            The matrix associated to a Rauzy induction, is the linear
2103
            application that allows to recover the lengths of ``self``
2104
            from the lengths of the induced.
2105

2106
            OUTPUT:
2107

2108
            matrix -- a square matrix of integers
2109

2110
            EXAMPLES:
2111

2112
            ::
2113

2114
                sage: p = iet.Permutation('a1 a2','a2 a1')
2115
                sage: d = p.rauzy_diagram()
2116
                sage: g = d.path(p,'top')
2117
                sage: g.matrix()
2118
                [1 0]
2119
                [1 1]
2120
                sage: g = d.path(p,'bottom')
2121
                sage: g.matrix()
2122
                [1 1]
2123
                [0 1]
2124

2125
            ::
2126

2127
                sage: p = iet.Permutation('a b c','c b a')
2128
                sage: d = p.rauzy_diagram()
2129
                sage: g = d.path(p)
2130
                sage: g.matrix() == identity_matrix(3)
2131
                True
2132
                sage: g = d.path(p,'top')
2133
                sage: g.matrix()
2134
                [1 0 0]
2135
                [0 1 0]
2136
                [1 0 1]
2137
                sage: g = d.path(p,'bottom')
2138
                sage: g.matrix()
2139
                [1 0 1]
2140
                [0 1 0]
2141
                [0 0 1]
2142
            """
2143
            return self.composition(self._parent.edge_to_matrix)
2144

2145
        def interval_substitution(self):
2146
            r"""
2147
            Returns the substitution of intervals obtained.
2148

2149
            OUTPUT:
2150

2151
            WordMorphism -- the word morphism corresponding to the interval
2152

2153
            EXAMPLES::
2154

2155
                sage: p = iet.Permutation('a b','b a')
2156
                sage: r = p.rauzy_diagram()
2157
                sage: p0 = r.path(p,0)
2158
                sage: s0 = p0.interval_substitution()
2159
                sage: s0
2160
                WordMorphism: a->a, b->ba
2161
                sage: p1 = r.path(p,1)
2162
                sage: s1 = p1.interval_substitution()
2163
                sage: s1
2164
                WordMorphism: a->ab, b->b
2165
                sage: (p0 + p1).interval_substitution() == s1 * s0
2166
                True
2167
                sage: (p1 + p0).interval_substitution() == s0 * s1
2168
                True
2169
            """
2170
            return self.right_composition(self._parent.edge_to_interval_substitution)
2171

2172
        def orbit_substitution(self):
2173
            r"""
2174
            Returns the substitution on the orbit of the left extremity.
2175

2176
            OUTPUT:
2177

2178
            WordMorhpism -- the word morphism corresponding to the orbit
2179

2180
            EXAMPLES::
2181

2182
                sage: p = iet.Permutation('a b','b a')
2183
                sage: d = p.rauzy_diagram()
2184
                sage: g0 = d.path(p,'top')
2185
                sage: s0 = g0.orbit_substitution()
2186
                sage: s0
2187
                WordMorphism: a->ab, b->b
2188
                sage: g1 = d.path(p,'bottom')
2189
                sage: s1 = g1.orbit_substitution()
2190
                sage: s1
2191
                WordMorphism: a->a, b->ab
2192
                sage: (g0 + g1).orbit_substitution() == s0 * s1
2193
                True
2194
                sage: (g1 + g0).orbit_substitution() == s1 * s0
2195
                True
2196
            """
2197
            return self.composition(self._parent.edge_to_orbit_substitution)
2198

2199
        substitution = orbit_substitution  # standard name
2200
        dual_substitution = interval_substitution  # standard name
2201

2202
        def is_full(self):
2203
            r"""
2204
            Tests the fullness.
2205

2206
            A path is full if all intervals win at least one time.
2207

2208
            OUTPUT:
2209

2210
            boolean -- ``True`` if the path is full and ``False`` else
2211

2212
            EXAMPLE::
2213

2214
                sage: p = iet.Permutation('a b c','c b a')
2215
                sage: r = p.rauzy_diagram()
2216
                sage: g0 = r.path(p,'t','b','t')
2217
                sage: g1 = r.path(p,'b','t','b')
2218
                sage: g0.is_full()
2219
                False
2220
                sage: g1.is_full()
2221
                False
2222
                sage: (g0 + g1).is_full()
2223
                True
2224
                sage: (g1 + g0).is_full()
2225
                True
2226
            """
2227
            return set(self._parent.letters()) == set(self.winners())
2228

2229
    def edge_to_interval_substitution(self, p=None, edge_type=None):
2230
        r"""
2231
        Returns the interval substitution associated to an edge
2232

2233
        OUTPUT:
2234

2235
        WordMorphism -- the WordMorphism corresponding to the edge
2236

2237
        EXAMPLE::
2238

2239
            sage: p = iet.Permutation('a b c','c b a')
2240
            sage: r = p.rauzy_diagram()
2241
            sage: r.edge_to_interval_substitution(None,None)
2242
            WordMorphism: a->a, b->b, c->c
2243
            sage: r.edge_to_interval_substitution(p,0)
2244
            WordMorphism: a->a, b->b, c->ca
2245
            sage: r.edge_to_interval_substitution(p,1)
2246
            WordMorphism: a->ac, b->b, c->c
2247
        """
2248
        if p is None and edge_type is None:
2249
            return WordMorphism(dict((a,a) for a in self.letters()))
2250

2251
        function_name = self._edge_types[edge_type][0] + '_interval_substitution'
2252
        if not hasattr(self._element_class,function_name):
2253
            return WordMorphism(dict((a,a) for a in self.letters()))
2254

2255
        arguments = self._edge_types[edge_type][1]
2256

2257
        return getattr(p,function_name)(*arguments)
2258

2259
    def edge_to_orbit_substitution(self, p=None, edge_type=None):
2260
        r"""
2261
        Returns the interval substitution associated to an edge
2262

2263
        OUTPUT:
2264

2265
        WordMorphism -- the word morphism corresponding to the edge
2266

2267
        EXAMPLE::
2268

2269
            sage: p = iet.Permutation('a b c','c b a')
2270
            sage: r = p.rauzy_diagram()
2271
            sage: r.edge_to_orbit_substitution(None,None)
2272
            WordMorphism: a->a, b->b, c->c
2273
            sage: r.edge_to_orbit_substitution(p,0)
2274
            WordMorphism: a->ac, b->b, c->c
2275
            sage: r.edge_to_orbit_substitution(p,1)
2276
            WordMorphism: a->a, b->b, c->ac
2277
        """
2278
        if p is None and edge_type is None:
2279
            return WordMorphism(dict((a,a) for a in self.letters()))
2280

2281
        function_name = self._edge_types[edge_type][0] + '_orbit_substitution'
2282

2283
        if not hasattr(self._element_class,function_name):
2284
            return WordMorphism(dict((a,a) for a in self.letters()))
2285

2286
        arguments = self._edge_types[edge_type][1]
2287
        return getattr(p,function_name)(*arguments)
2288

2289
    def full_loop_iterator(self, start=None, max_length=1):
2290
        r"""
2291
        Returns an iterator over all full path starting at start.
2292

2293
        INPUT:
2294

2295
        - ``start`` - the start point
2296

2297
        - ``max_length`` - a limit on the length of the paths
2298

2299
        OUTPUT:
2300

2301
        iterator -- iterator over full loops
2302

2303
        EXAMPLE::
2304

2305
            sage: p = iet.Permutation('a b','b a')
2306
            sage: r = p.rauzy_diagram()
2307
            sage: for g in r.full_loop_iterator(p,2):
2308
            ....:     print g.matrix(), "\n*****"
2309
            [1 1]
2310
            [1 2]
2311
            *****
2312
            [2 1]
2313
            [1 1]
2314
            *****
2315
        """
2316
        from itertools import ifilter, imap
2317

2318
        g = self.path(start)
2319

2320
        ifull = ifilter(
2321
            lambda x: x.is_loop() and x.is_full(),
2322
            self._all_path_extension(g,max_length))
2323

2324
        return imap(copy,ifull)
2325

2326
    def full_nloop_iterator(self, start=None, length=1):
2327
        r"""
2328
        Returns an iterator over all full loops of given length.
2329

2330
        INPUT:
2331

2332
        - ``start`` - the initial permutation
2333

2334
        - ``length`` - the length to consider
2335

2336
        OUTPUT:
2337

2338
        iterator -- an iterator over the full loops of given length
2339

2340
        EXAMPLE::
2341

2342
            sage: p = iet.Permutation('a b','b a')
2343
            sage: d = p.rauzy_diagram()
2344
            sage: for g in d.full_nloop_iterator(p,2):
2345
            ....:     print g.matrix(), "\n*****"
2346
            [1 1]
2347
            [1 2]
2348
            *****
2349
            [2 1]
2350
            [1 1]
2351
            *****
2352
        """
2353
        from itertools import ifilter, imap
2354

2355
        g = self.path(start)
2356

2357
        ifull = ifilter(
2358
            lambda x: x.is_loop() and x.is_full(),
2359
            self._all_npath_extension(g,length))
2360

2361
        return imap(copy, ifull)
2362

2363
    def _permutation_to_vertex(self, p):
2364
        r"""
2365
        Translation of a labelled permutation to a vertex
2366

2367
        INPUT:
2368

2369
        - ``p`` - a labelled Permutation
2370

2371
        TESTS::
2372

2373
            sage: p = iet.Permutation('a b c','c b a')
2374
            sage: r = p.rauzy_diagram()
2375
            sage: p in r   #indirect doctest
2376
            True
2377
        """
2378
        return (tuple(p._intervals[0]),tuple(p._intervals[1]))
2379

2380
    def _set_element(self,data):
2381
        r"""
2382
        Sets self._element with data
2383

2384
        TESTS::
2385

2386
            sage: p = iet.Permutation('a b c','c b a')
2387
            sage: r = p.rauzy_diagram()
2388
            sage: r[p][0] == p.rauzy_move(0)   #indirect doctest
2389
            True
2390
            sage: r[p][1] == p.rauzy_move(1)   #indirect doctest
2391
            True
2392
        """
2393
        self._element._intervals = [list(data[0]), list(data[1])]
2394

2395
class FlippedLabelledRauzyDiagram(FlippedRauzyDiagram, LabelledRauzyDiagram):
2396
    r"""
2397
    Rauzy diagram of flipped labelled permutations
2398
    """
2399
    def _permutation_to_vertex(self, p):
2400
        r"""
2401
        Returns what must be stored from p.
2402

2403
        INPUT:
2404

2405
        - ``p`` - a Flipped labelled permutation
2406

2407
        TESTS::
2408

2409
            sage: p = iet.Permutation('a b c','c b a',flips='a')
2410
            sage: r = p.rauzy_diagram()
2411
            sage: p in r   #indirect doctest
2412
            True
2413
        """
2414
        return ((tuple(p._intervals[0]),tuple(p._intervals[1])),
2415
                (tuple(p._flips[0]), tuple(p._flips[1])))
2416

2417
    def _set_element(self, data):
2418
        r"""
2419
        Returns what the vertex i as a permutation.
2420

2421
        TESTS::
2422

2423
            sage: p = iet.Permutation('a b','b a',flips='a')
2424
            sage: r = p.rauzy_diagram()
2425
            sage: p in r   #indirect doctest
2426
            True
2427
        """
2428
        self._element._intervals = [list(data[0][0]), list(data[0][1])]
2429
        self._element._flips = [list(data[1][0]), list(data[1][1])]
2430

2431
Product

Resources

Company
