CoCalc -- affine_permutation.py

GitHub Repository: sagemath/sagesmc
Path: blob/master/src/sage/combinat/affine_permutation.py
⁸⁸¹⁷ views
1
r"""
2
Affine Permutations
3
"""
4

5
#*****************************************************************************
6
#       Copyright (C) 2013 Tom Denton <[email protected]>
7
#
8
#  Distributed under the terms of the GNU General Public License (GPL)
9
#  as published by the Free Software Foundation; either version 2 of
10
#  the License, or (at your option) any later version.
11
#                  http://www.gnu.org/licenses/
12
#*****************************************************************************
13

14
from sage.misc.cachefunc import cached_method
15
from sage.misc.misc_c import prod
16
from sage.misc.constant_function import ConstantFunction
17
from sage.misc.prandom import randint
18

19
from sage.categories.affine_weyl_groups import AffineWeylGroups
20
from sage.structure.list_clone import ClonableArray
21
from sage.structure.unique_representation import UniqueRepresentation
22
from sage.structure.parent import Parent
23

24
from sage.groups.perm_gps.permgroup_named import SymmetricGroup
25
from sage.rings.arith import binomial
26
from sage.combinat.root_system.cartan_type import CartanType
27
from sage.combinat.root_system.weyl_group import WeylGroup
28
from sage.combinat.composition import Composition
29
from sage.combinat.partition import Partition
30

31
class AffinePermutation(ClonableArray):
32
    r"""
33
    An affine permutation, representated in the window notation, and
34
    considered as a bijection from `\ZZ` to `\ZZ`.
35

36
    EXAMPLES::
37

38
        sage: A=AffinePermutationGroup(['A',7,1])
39
        sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
40
        sage: p
41
        Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
42
    """
43
    def __init__(self, parent, lst, check=True):
44
        r"""
45
        Initialize ``self``
46

47
        INPUT:
48

49
        - ``parent`` -- The parent affine permutation group.
50

51
        - ``lst`` -- List giving the base window of the affine permutation.
52

53
        - ``check``-- Chooses whether to test that the affine permutation is legit.
54

55
        EXAMPLES::
56

57
            sage: A=AffinePermutationGroup(['A',7,1])
58
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9]) #indirect doctest
59
            sage: p
60
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
61
        """
62
        self._lst=lst
63
        self.k=parent.k
64
        self.n=self.k+1
65
        #This N doesn't matter for type A, but comes up in all other types.
66
        if parent.cartan_type()[0]=='A':
67
            self.N=self.n
68
        elif parent.cartan_type()[0] in ['B', 'C', 'D']:
69
            self.N=2*self.k+1
70
        elif parent.cartan_type()[0]=='G':
71
            self.N=6
72
        else:
73
            raise NotImplementedError, 'Unsupported Cartan Type.'
74
        ClonableArray.__init__(self, parent, lst, check)
75

76
    def _repr_(self):
77
        r"""
78
        EXAMPLES::
79

80
            sage: A=AffinePermutationGroup(['A',7,1])
81
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
82
            sage: p
83
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
84
        """
85
        return "Type "+ self.parent().cartan_type().letter +" affine permutation with window " + str([i for i in self])
86

87
    def __rmul__(self, q):
88
        r"""
89
        Given ``self`` and `q`, returns ``self*q``.
90

91
        INPUT:
92

93
        - ``q`` -- An element of ``self.parent()``
94

95
        EXAMPLES::
96

97
            sage: A=AffinePermutationGroup(['A',7,1])
98
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
99
            sage: q=A([0, 2, 3, 4, 5, 6, 7, 9])
100
            sage: p.__rmul__(q)
101
            Type A affine permutation with window [1, -1, 0, 6, 5, 4, 10, 11]
102
        """
103
        l=[self.value(q.value(i)) for i in xrange(1,len(self._lst)+1)]
104
        return self.parent()(l, check=False)
105

106
    def __lmul__(self, q):
107
        r"""
108
        Given ``self`` and `q`, returns ``q*self``.
109

110
        INPUT:
111

112
        - ``q`` -- An element of ``self.parent()``
113

114
        EXAMPLES::
115

116
            sage: A=AffinePermutationGroup(['A',7,1])
117
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
118
            sage: q=A([0,2,3,4,5,6,7,9])
119
            sage: p.__lmul__(q)
120
            Type A affine permutation with window [3, -1, 1, 6, 5, 4, 10, 8]
121
        """
122
        #if self.parent().right_to_left:
123
        #    self,q=q,self
124
        #... product rule
125
        l=[q.value(self.value(i)) for i in xrange(1,len(self._lst)+1)]
126
        return self.parent()(l, check=False)
127

128
    def __mul__(self, q):
129
        r"""
130
        Given ``self`` and `q`, returns ``self*q``.
131

132
        INPUT:
133

134
        - ``q`` -- An element of ``self.parent()``
135

136
        EXAMPLES::
137

138
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
139
            sage: s1=AffinePermutationGroup(['A',7,1]).one().apply_simple_reflection(1)
140
            sage: p*s1
141
            Type A affine permutation with window [-1, 3, 0, 6, 5, 4, 10, 9]
142
            sage: p.apply_simple_reflection(1, 'right')
143
            Type A affine permutation with window [-1, 3, 0, 6, 5, 4, 10, 9]
144

145
        """
146
        return self.__rmul__(q)
147

148
    @cached_method
149
    def inverse(self):
150
        r"""
151
        Finds the inverse affine permutation.
152

153
        EXAMPLES::
154

155
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
156
            sage: p.inverse()
157
            Type A affine permutation with window [0, -1, 1, 6, 5, 4, 10, 11]
158
        """
159
        inv=[self.position(i) for i in xrange(1,len(self._lst)+1)]
160
        return self.parent()(inv, check=False)
161

162
    __invert__=inverse
163

164
    def apply_simple_reflection(self, i, side='right'):
165
        r"""
166
        Applies a simple reflection.
167

168
        INPUT:
169

170
        - ``i`` -- an integer.
171
        - ``side`` -- Determines whether to apply the reflection on the 'right' or 'left'.  Default 'right'.
172

173
        EXAMPLES::
174

175
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
176
            sage: p.apply_simple_reflection(3)
177
            Type A affine permutation with window [3, -1, 6, 0, 5, 4, 10, 9]
178
            sage: p.apply_simple_reflection(11)
179
            Type A affine permutation with window [3, -1, 6, 0, 5, 4, 10, 9]
180
            sage: p.apply_simple_reflection(3, 'left')
181
            Type A affine permutation with window [4, -1, 0, 6, 5, 3, 10, 9]
182
            sage: p.apply_simple_reflection(11, 'left')
183
            Type A affine permutation with window [4, -1, 0, 6, 5, 3, 10, 9]
184
        """
185
        if side=='right':
186
            return self.apply_simple_reflection_right(i)
187
        if side=='left':
188
            return self.apply_simple_reflection_left(i)
189

190
    def __call__(self, i):
191
        r"""
192
        Returns the image of the integer `i` under this permutation.
193

194
        EXAMPLES::
195

196
            sage: A=AffinePermutationGroup(['A',7,1])
197
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
198
            sage: p.value(1) #indirect doctest
199
            3
200
            sage: p.value(9)
201
            11
202
        """
203
        return self.value(i)
204

205
    def is_i_grassmannian(self, i=0, side="right"):
206
        r"""
207
        Test whether ``self`` is `i`-grassmannian, ie, either is the identity or has
208
        ``i`` as the sole descent.
209

210
        INPUT:
211

212
        - ``i`` -- An element of the index set.
213
        - ``side`` -- determines the side on which to check the descents.
214

215
        EXAMPLES::
216

217
            sage: A=AffinePermutationGroup(['A',7,1])
218
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
219
            sage: p.is_i_grassmannian()
220
            False
221
            sage: q=A.from_word([3,2,1,0])
222
            sage: q.is_i_grassmannian()
223
            True
224
            sage: q=A.from_word([2,3,4,5])
225
            sage: q.is_i_grassmannian(5)
226
            True
227
            sage: q.is_i_grassmannian(2, side='left')
228
            True
229
        """
230
        if self==self.parent().one(): return True
231
        if self.descents(side)==[i]: return True
232
        return False
233

234
    def index_set(self):
235
        r"""
236
        Index set of the affine permutation group.
237

238
        EXAMPLES::
239

240
            sage: A=AffinePermutationGroup(['A',7,1])
241
            sage: A.index_set()
242
            (0, 1, 2, 3, 4, 5, 6, 7)
243
        """
244
        return tuple(range(self.k+1))
245

246
    def lower_covers(self,side="right"):
247
        r"""
248
        Return lower covers of ``self``.
249

250
        The set of affine permutations of one less length related by
251
        multiplication by a simple transposition on the indicated side.
252
        These are the elements that ``self`` covers in weak order.
253

254
        EXAMPLES::
255

256
            sage: A=AffinePermutationGroup(['A',7,1])
257
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
258
            sage: p.lower_covers()
259
            [Type A affine permutation with window [-1, 3, 0, 6, 5, 4, 10, 9], Type A affine permutation with window [3, -1, 0, 5, 6, 4, 10, 9], Type A affine permutation with window [3, -1, 0, 6, 4, 5, 10, 9], Type A affine permutation with window [3, -1, 0, 6, 5, 4, 9, 10]]
260

261
        """
262
        S=self.descents(side)
263
        return [self.apply_simple_reflection(i, side) for i in S]
264

265
    def is_one(self):
266
        r"""
267
        Tests whether the affine permutation is the identity.
268

269
        EXAMPLES::
270

271
            sage: A=AffinePermutationGroup(['A',7,1])
272
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
273
            sage: p.is_one()
274
            False
275
            sage: q=A.one()
276
            sage: q.is_one()
277
            True
278
        """
279
        return self==self.parent().one()
280

281
    def reduced_word(self):
282
        r"""
283
        Returns a reduced word for the affine permutation.
284

285
        EXAMPLES::
286

287
            sage: A=AffinePermutationGroup(['A',7,1])
288
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
289
            sage: p.reduced_word()
290
            [0, 7, 4, 1, 0, 7, 5, 4, 2, 1]
291
        """
292
        #This is about 25% faster than the default algorithm.
293
        x=self
294
        i=0
295
        word=[]
296
        while not x.is_one():
297
            if x.has_descent(i):
298
                x=x.apply_simple_reflection_right(i)
299
                word.append(i)
300
            i=(i+1)%(self.k+1)
301
        word.reverse()
302
        return word
303

304
    def signature(self):
305
        r"""
306
        Signature of the affine permutation, `(-1)^l`, where `l` is the length of the permutation.
307

308
        EXAMPLES::
309

310
            sage: A=AffinePermutationGroup(['A',7,1])
311
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
312
            sage: p.signature()
313
            1
314
        """
315
        return (-1)**self.length()
316

317
    @cached_method
318
    def to_weyl_group_element(self):
319
        r"""
320
        The affine Weyl group element corresponding to the affine permutation.
321

322
        EXAMPLES::
323

324
            sage: A=AffinePermutationGroup(['A',7,1])
325
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
326
            sage: p.to_weyl_group_element()
327
            [ 0 -1  0  1  0  0  1  0]
328
            [ 1 -1  0  1  0  0  1 -1]
329
            [ 1 -1  0  1  0  0  0  0]
330
            [ 0  0  0  1  0  0  0  0]
331
            [ 0  0  0  1  0 -1  1  0]
332
            [ 0  0  0  1 -1  0  1  0]
333
            [ 0  0  0  0  0  0  1  0]
334
            [ 0 -1  1  0  0  0  1  0]
335
        """
336
        W=self.parent().weyl_group()
337
        return W.from_reduced_word(self.reduced_word())
338

339
    def grassmannian_quotient(self, i=0, side='right'):
340
        r"""
341
        Return Grassmannian quotient.
342

343
        Factors ``self`` into a unique product of a Grassmannian and a finite-type
344
        element.  Returns a tuple containing the Grassmannain and finite
345
        elements, in order according to side.
346

347
        INPUT:
348

349
        - ``i`` -- An element of the index set; the descent checked for.  Defaults to 0.
350

351
        EXAMPLES::
352

353
            sage: A=AffinePermutationGroup(['A',7,1])
354
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
355
            sage: gq=p.grassmannian_quotient()
356
            sage: gq
357
            (Type A affine permutation with window [-1, 0, 3, 4, 5, 6, 9, 10], Type A affine permutation with window [3, 1, 2, 6, 5, 4, 8, 7])
358
            sage: gq[0].is_i_grassmannian()
359
            True
360
            sage: 0 not in gq[1].reduced_word()
361
            True
362
            sage: prod(gq)==p
363
            True
364

365
            sage: gqLeft=p.grassmannian_quotient(side='left')
366
            sage: 0 not in gqLeft[0].reduced_word()
367
            True
368
            sage: gqLeft[1].is_i_grassmannian(side='left')
369
            True
370
            sage: prod(gqLeft)==p
371
            True
372
        """
373
        fin=self.parent().one()
374
        gr=self
375
        D=gr.descents(side=side)
376
        while not (D==[i] or D==[]):
377
            m=D[0]
378
            if m==i: m=D[1]
379
            if side=='right':
380
                fin=fin.apply_simple_reflection(m, side='left')
381
                gr =gr.apply_simple_reflection(m, side='right')
382
            else:
383
                fin=fin.apply_simple_reflection(m, side='right')
384
                gr =gr.apply_simple_reflection(m, side='left')
385
            D=gr.descents(side=side)
386
        if side=='right':
387
            return (gr, fin)
388
        else:
389
            return (fin, gr)
390

391

392

393
class AffinePermutationTypeA(AffinePermutation):
394
    #----------------------
395
    #Type-specific methods.
396
    #(Methods existing in all types, but with type-specific definition.)
397
    #----------------------
398
    def check(self):
399
        r"""
400
        Check that ``self`` is an affine permutation.
401

402
        EXAMPLES::
403

404
            sage: A=AffinePermutationGroup(['A',7,1])
405
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
406
            sage: p
407
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
408
            sage: q=A([1,2,3])
409
            Traceback (most recent call last):
410
            ...
411
            ValueError: Length of list must be k+1=8.
412
            sage: q=A([1,2,3,4,5,6,7,0])
413
            Traceback (most recent call last):
414
            ...
415
            ValueError: Window does not sum to 36.
416
            sage: q=A([1,1,3,4,5,6,7,9])
417
            Traceback (most recent call last):
418
            ...
419
            ValueError: Entries must have distinct residues.
420
        """
421
        if not self:
422
            return
423
        k=self.parent().k
424
        #Type A.
425
        if not len(self)==k+1: raise ValueError("Length of list must be k+1="+str(k+1)+".")
426
        if not (binomial(k+2,2) == sum(self)): raise ValueError("Window does not sum to "+str(binomial((k+2),2))+".")
427
        l=[i%(k+1) for i in self]
428
        l.sort()
429
        if not l == range(k+1): raise ValueError("Entries must have distinct residues.")
430

431

432
    def value(self, i, base_window=False):
433
        r"""
434
        Return the image of the integer ``i`` under this permutation.
435

436
        INPUT:
437

438
        - ``base_window`` -- a Boolean, indicating whether `i` is in the base window.
439
          If True, will run a bit faster, but the method will screw up if `i` is not
440
          actually in the index set.
441

442
        EXAMPLES::
443

444
            sage: A=AffinePermutationGroup(['A',7,1])
445
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
446
            sage: p.value(1)
447
            3
448
            sage: p.value(9)
449
            11
450
        """
451
        if base_window: self[i-1]
452
        window=(i-1)//(self.k+1)
453
        return self[(i-1)%(self.k+1)]+window*(self.k+1)
454

455
    def position(self, i):
456
        r"""
457
        Find the position `j` such the ``self.value(j)=i``
458

459
        EXAMPLES::
460

461
            sage: A=AffinePermutationGroup(['A',7,1])
462
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
463
            sage: p.position(3)
464
            1
465
            sage: p.position(11)
466
            9
467
        """
468
        for r in xrange(self.k+1):
469
            if (self[r]%(self.k+1))==i%(self.k+1):
470
                #i sits in position i, but some number of windows away.
471
                diff=(i-self[r])//(self.k+1)
472
                return r+diff*(self.k+1)+1
473
        return False
474

475
    def apply_simple_reflection_right(self, i):
476
        r"""
477
        Applies the simple reflection to positions `i`, `i+1`.
478
        `i` is allowed to be any integer.
479

480
        EXAMPLES::
481

482
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
483
            sage: p.apply_simple_reflection_right(3)
484
            Type A affine permutation with window [3, -1, 6, 0, 5, 4, 10, 9]
485
            sage: p.apply_simple_reflection_right(11)
486
            Type A affine permutation with window [3, -1, 6, 0, 5, 4, 10, 9]
487
        """
488
        j=i%(self.k+1)
489
        #Cloning is currently kinda broken, in that caches don't clear which
490
        #leads to strangeness with the cloned object.
491
        #The clone approach is quite a bit (2x) faster, though, so this should
492
        #switch once the caching situation is fixed.
493
        #with self.clone(check=False) as l:
494
        l = self[:]
495
        if j==0:
496
            a = l[0]
497
            l[0] = l[-1] - (self.k+1)
498
            l[-1] = a +(self.k+1)
499
        else:
500
            a = l[j-1]
501
            l[j-1] = l[j]
502
            l[j] = a
503
        #return l
504
        return self.parent()(l,check=False)
505

506
    def apply_simple_reflection_left(self, i):
507
        r"""
508
        Applies simple reflection to the values `i`, `i+1`.
509

510
        EXAMPLES::
511

512
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
513
            sage: p.apply_simple_reflection_left(3)
514
            Type A affine permutation with window [4, -1, 0, 6, 5, 3, 10, 9]
515
            sage: p.apply_simple_reflection_left(11)
516
            Type A affine permutation with window [4, -1, 0, 6, 5, 3, 10, 9]
517
        """
518
        #Here are a couple other methods we tried out, but turned out
519
        #to be slower than the current implementation.
520
        #1) This one was very bad:
521
        #   return self.inverse().apply_simple_reflection_right(i).inverse()
522
        #2) Also bad, though not quite so bad:
523
        #   return (self.parent().simple_reflection(i))*self
524
        i=i%(self.k+1)
525
        #Cloning is currently kinda broken, in that caches don't clear which
526
        #leads to strangeness with the cloned object.
527
        #The clone approach is quite a bit faster, though, so this should switch
528
        #once the caching situation is fixed.
529
        #with self.clone(check=False) as l:
530
        l=[]
531
        if i!=self.k:
532
            for m in xrange(self.k+1):
533
                res=self[m]%(self.k+1)
534
                if res==i  :
535
                    l.append(self[m]+1)
536
                elif res==i+1:
537
                    l.append(self[m]-1)
538
                else:
539
                    l.append(self[m])
540
        if i==self.k:
541
            for m in xrange(self.k+1):
542
                res=self[m]%(self.k+1)
543
                if res==i  :
544
                    l.append(self[m]+1)
545
                elif res==0:
546
                    l.append(self[m]-1)
547
                else:
548
                    l.append(self[m])
549
        return self.parent()(l, check=False)
550

551
    def has_right_descent(self, i):
552
        r"""
553
        Determines whether there is a descent at `i`.
554

555
        INPUT:
556

557
        - ``i`` -- an integer.
558

559
        EXAMPLES::
560

561
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
562
            sage: p.has_right_descent(1)
563
            True
564
            sage: p.has_right_descent(9)
565
            True
566
            sage: p.has_right_descent(0)
567
            False
568
        """
569
        return self.value(i)>self.value(i+1)
570

571
    def has_left_descent(self, i):
572
        r"""
573
        Determines whether there is a descent at `i`.
574

575
        INPUT:
576

577
        - ``i`` -- an integer.
578

579
        EXAMPLES::
580

581
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
582
            sage: p.has_left_descent(1)
583
            True
584
            sage: p.has_left_descent(9)
585
            True
586
            sage: p.has_left_descent(0)
587
            True
588
        """
589
        #This is much faster thant he default method of taking the inverse and
590
        #then finding right descents...
591
        return self.position(i)>self.position(i+1)
592

593
    def to_type_a(self):
594
        r"""
595
        Returns an embedding of ``self`` into the affine permutation group of
596
        type A.  (For Type `A`, just returns self.)
597

598
        EXAMPLES::
599

600
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
601
            sage: p.to_type_a()==p
602
            True
603
        """
604
        return self
605

606
    #----------------------
607
    #Type-A-specific methods.
608
    #Only available in Type A.
609
    #----------------------
610

611
    def flip_automorphism(self):
612
        r"""
613
        The Dynkin diagram automorphism which fixes `s_0` and reverses all
614
        other indices.
615

616
        EXAMPLES::
617

618
            sage: A=AffinePermutationGroup(['A',7,1])
619
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
620
            sage: p.flip_automorphism()
621
            Type A affine permutation with window [0, -1, 5, 4, 3, 9, 10, 6]
622
        """
623
        #Note: There should be a more combinatorial (ie, faster) way to do this.
624
        w=[(self.k+1-i)%(self.k+1) for i in self.reduced_word()]
625
        return self.parent().from_word(w)
626

627
    def promotion(self):
628
        r"""
629
        The Dynkin diagram automorphism which sends `s_i` to `s_{i+1}`.
630

631
        EXAMPLES::
632

633
            sage: A=AffinePermutationGroup(['A',7,1])
634
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
635
            sage: p.promotion()
636
            Type A affine permutation with window [2, 4, 0, 1, 7, 6, 5, 11]
637
        """
638
        l=[]
639
        l.append(self._lst[-1]-self.k)
640
        for i in xrange(1,self.k+1):
641
            l.append(self._lst[i-1]+1)
642
        return self.parent()(l)
643

644
    def maximal_cyclic_factor(self, typ='decreasing', side='right', verbose=False):
645
        r"""
646
        For an affine permutation `x`, finds the unique maximal subset `A`
647
        of the index set such that `x=yd_A` is a reduced product.
648

649
        INPUT:
650

651
        - ``typ`` -- 'increasing' or 'decreasing.'  Determines the type of
652
          maximal cyclic element found.
653

654
        - ``side`` -- 'right' or 'left'.
655

656
        - ``verbose`` -- True or False.  If True, outputs information about how
657
          the cyclically increasing element was found.
658

659
        EXAMPLES::
660

661
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
662
            sage: p.maximal_cyclic_factor()
663
            [7, 5, 4, 2, 1]
664
            sage: p.maximal_cyclic_factor(side='left')
665
            [1, 0, 7, 5, 4]
666
            sage: p.maximal_cyclic_factor('increasing','right')
667
            [4, 5, 7, 0, 1]
668
            sage: p.maximal_cyclic_factor('increasing','left')
669
            [0, 1, 2, 4, 5]
670
        """
671
        k=self.k
672
        if side[0]=='r':
673
            Descents=self.descents(side='right')
674
            side='right'
675
        else:
676
            Descents=self.descents(side='left')
677
            side='left'
678
        #for now, assume side is 'right')
679
        best_T=[]
680
        for i in Descents:
681
            y=self.clone().apply_simple_reflection(i,side)
682
            T=[i]
683
            j=i
684
            for count in xrange(1,self.k):
685
                if (typ[0],side[0])==('d','r'):  j=(j+1)%(k+1)
686
                if (typ[0],side[0])==('i','r'):  j=(j-1)%(k+1)
687
                if (typ[0],side[0])==('d','l'):  j=(j-1)%(k+1)
688
                if (typ[0],side[0])==('i','l'):  j=(j+1)%(k+1)
689
                if y.has_descent(j, side):
690
                    y=y.apply_simple_reflection(j,side)
691
                    T.append(j%(k+1))
692
            if verbose:
693
                print i, T
694
            if len(T)>len(best_T):
695
                best_T=T
696
        #if (typ[0],side[0])==('i','r'): best_T.reverse()
697
        #if (typ[0],side[0])==('d','l'): best_T.reverse()
698
        #if typ[0]=='d': best_T.reverse()
699
        if side[0]=='r': best_T.reverse()
700
        return best_T
701

702

703
    def maximal_cyclic_decomposition(self, typ='decreasing', side='right', verbose=False):
704
        r"""
705
        Finds the unique maximal decomposition of ``self`` into cyclically
706
        decreasing/increasing elements.
707

708
        INPUT:
709

710
        - ``typ`` -- 'increasing' or 'decreasing' (default: 'decreasing'.)
711
          Chooses whether to find increasing or deacreasing sets.
712

713
        - ``side`` -- 'right' or 'left' (default: 'right'.)  Chooses whether to
714
          find maximal sets starting from the left or the right.
715

716
        - ``verbose`` -- Print extra information while finding the decomposition.
717

718
        EXAMPLES::
719

720
            sage: p=AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
721
            sage: p.maximal_cyclic_decomposition()
722
            [[0, 7], [4, 1, 0], [7, 5, 4, 2, 1]]
723
            sage: p.maximal_cyclic_decomposition(side='left')
724
            [[1, 0, 7, 5, 4], [1, 0, 5], [2, 1]]
725
            sage: p.maximal_cyclic_decomposition(typ='increasing', side='right')
726
            [[1], [5, 0, 1, 2], [4, 5, 7, 0, 1]]
727
            sage: p.maximal_cyclic_decomposition(typ='increasing', side='left')
728
            [[0, 1, 2, 4, 5], [4, 7, 0, 1], [7]]
729

730
        TESTS::
731

732
            sage: A=AffinePermutationGroup(['A',7,1])
733
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
734
            sage: S=p.maximal_cyclic_decomposition()
735
            sage: p==prod(A.from_word(l) for l in S)
736
            True
737
            sage: S=p.maximal_cyclic_decomposition(typ='increasing', side='left')
738
            sage: p==prod(A.from_word(l) for l in S)
739
            True
740
            sage: S=p.maximal_cyclic_decomposition(typ='increasing', side='right')
741
            sage: p==prod(A.from_word(l) for l in S)
742
            True
743
            sage: S=p.maximal_cyclic_decomposition(typ='decreasing', side='right')
744
            sage: p==prod(A.from_word(l) for l in S)
745
            True
746
        """
747
        y=self.clone()
748
        listy=[]
749
        if verbose: print 'length of x:', self.length()
750
        while not y.is_one():
751
            S=y.maximal_cyclic_factor(typ, side, verbose)
752
            listy.append(S[:])
753
            if side[0]=='r':  S.reverse()
754
            for i in S:
755
                if side[0]=='r':
756
                    y=y.apply_simple_reflection_right(i)
757
                else:
758
                    y=y.apply_simple_reflection_left(i)
759
            if verbose: print S, y.length()
760
        if side[0]=='r': listy.reverse()
761
        return listy
762

763
    def to_lehmer_code(self, typ='decreasing', side='right'):
764
        r"""
765
        Returns the affine Lehmer code.
766

767
        There are four such codes; the options ``typ`` and ``side`` determine which
768
        code is generated.  The codes generated are the shape of the maximal
769
        cyclic decompositions of ``self`` according to the given ``typ`` and ``side``
770
        options.
771

772
        INPUT:
773

774
        - ``typ`` -- 'increasing' or 'decreasing' (default: 'decreasing'.)
775
          Chooses whether to find increasing or deacreasing sets.
776

777
        - ``side`` -- 'right' or 'left' (default: 'right'.)  Chooses whether to
778
          find maximal sets starting from the left or the right.
779

780
        EXAMPLES::
781

782
            sage: A=AffinePermutationGroup(['A',7,1])
783
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
784
            sage: CP=CartesianProduct( ('increasing','decreasing'),('left','right') )
785
            sage: for a in CP:
786
            ....:   p.to_lehmer_code(a[0],a[1])
787
            [2, 3, 2, 0, 1, 2, 0, 0]
788
            [2, 2, 0, 0, 2, 1, 0, 3]
789
            [3, 1, 0, 0, 2, 1, 0, 3]
790
            [0, 3, 3, 0, 1, 2, 0, 1]
791
            sage: for a in CP:
792
            ....:   A.from_lehmer_code(p.to_lehmer_code(a[0],a[1]), a[0],a[1])==p
793
            True
794
            True
795
            True
796
            True
797
        """
798
        code=[0 for i in xrange(0,self.k+1)]
799
        if typ[0]=='i' and side[0]=='r':
800
            #Find number of positions to the right of position i with smaller
801
            #value than the number in position i.
802
            for i in xrange(0,self.k+1):
803
                a=self(i)
804
                for j in xrange(i+1, i+self.k+1):
805
                    b=self(j)
806
                    if b<a: code[i]+=((a-b)//(self.k+1)+1)
807
        if typ[0]=='d' and side[0]=='r':
808
            #Find number of positions to the left of position i with larger
809
            #value than the number in position i.  Then cyclically shift
810
            #the resulting vector.
811
            for i in xrange(0,self.k+1):
812
                a=self(i)
813
                for j in xrange(i-self.k, i):
814
                    b=self(j)
815
                    #A small rotation is necessary for the reduced word from
816
                    #the lehmer code to match the element.
817
                    if a<b: code[i-1]+=((b-a)//(self.k+1)+1)
818
        if typ[0]=='i' and side[0]=='l':
819
            #Find number of positions to the right of i smaller than i, then
820
            #cyclically shift the resulting vector.
821
            for i in xrange(0,self.k+1):
822
                pos=self.position(i)
823
                for j in xrange(pos+1, pos+self.k+1):
824
                    b=self(j)
825
                    #A small rotation is necessary for the reduced word from
826
                    #the lehmer code to match the element.
827
                    if b<i: code[i-1]+=((i-b)//(self.k+1)+1)
828
        if typ[0]=='d' and side[0]=='l':
829
            #Find number of positions to the left of i larger than i.
830
            for i in xrange(0,self.k+1):
831
                pos=self.position(i)
832
                for j in xrange(pos-self.k, pos):
833
                    b=self(j)
834
                    if b>i: code[i]+=((b-i)//(self.k+1)+1)
835
        return Composition(code)
836

837
    def is_fully_commutative(self):
838
        r"""
839
        Determines whether ``self`` is fully commutative, ie, has no reduced words
840
        with a braid.
841

842
        EXAMPLES::
843

844
            sage: A=AffinePermutationGroup(['A',7,1])
845
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
846
            sage: p.is_fully_commutative()
847
            False
848
            sage: q=A([-3, -2, 0, 7, 9, 2, 11, 12])
849
            sage: q.is_fully_commutative()
850
            True
851
        """
852
        if self==self.parent().one(): return True
853
        c=self.to_lehmer_code()
854
        firstnonzero=None
855
        m=-1
856
        for i in range(self.n):
857
            if c[i]>0:
858
                if firstnonzero==None: firstnonzero=i
859
                if m!=-1 and c[i]-(i-m) >= c[m]: return False
860
                m=i
861
        #now check m (the last non-zero) against firstnonzero.
862
        d=self.n-(m-firstnonzero)
863
        if c[firstnonzero]-d >= c[m]: return False
864
        return True
865

866
    def to_bounded_partition(self, typ='decreasing', side='right'):
867
        r"""
868
        Returns the `k`-bounded partition associated to the dominant element
869
        obtained by sorting the Lehmer code.
870

871
        INPUT:
872

873
        - ``typ`` -- 'increasing' or 'decreasing' (default: 'decreasing'.)
874
          Chooses whether to find increasing or deacreasing sets.
875

876
        - ``side`` -- 'right' or 'left' (default: 'right'.)  Chooses whether to
877
          find maximal sets starting from the left or the right.
878

879
        EXAMPLES::
880

881
            sage: A=AffinePermutationGroup(['A',2,1])
882
            sage: p=A.from_lehmer_code([4,1,0])
883
            sage: p.to_bounded_partition()
884
            [2, 1, 1, 1]
885
        """
886
        c=list(self.to_lehmer_code(typ,side))
887
        c.sort()
888
        c.reverse()
889
        return Partition(c).conjugate()
890

891
    def to_core(self, typ='decreasing', side='right'):
892
        r"""
893
        Returns the core associated to the dominant element obtained by sorting
894
        the Lehmer code.
895

896
        INPUT:
897

898
        - ``typ`` -- 'increasing' or 'decreasing' (default: 'decreasing'.)
899

900
        - ``side`` -- 'right' or 'left' (default: 'right'.)  Chooses whether to
901
          find maximal sets starting from the left or the right.
902

903
        EXAMPLES::
904

905
            sage: A=AffinePermutationGroup(['A',2,1])
906
            sage: p=A.from_lehmer_code([4,1,0])
907
            sage: p.to_bounded_partition()
908
            [2, 1, 1, 1]
909
            sage: p.to_core()
910
            [4, 2, 1, 1]
911
        """
912
        return self.to_bounded_partition(typ,side).to_core(self.k)
913

914
    def to_dominant(self, typ='decreasing', side='right'):
915
        r"""
916
        Finds the Lehmer code and then sorts it.  Returns the affine permutation
917
        with the given sorted Lehmer code; this element is 0-dominant.
918

919
        INPUT:
920

921
        - ``typ`` -- 'increasing' or 'decreasing' (default: 'decreasing'.)
922
          Chooses whether to find increasing or deacreasing sets.
923

924
        - ``side`` -- 'right' or 'left' (default: 'right'.)  Chooses whether to
925
          find maximal sets starting from the left or the right.
926

927
        EXAMPLES::
928

929
            sage: A=AffinePermutationGroup(['A',7,1])
930
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
931
            sage: p.to_dominant()
932
            Type A affine permutation with window [-2, -1, 1, 3, 4, 8, 10, 13]
933
            sage: p.to_dominant(typ='increasing', side='left')
934
            Type A affine permutation with window [3, 4, -1, 5, 0, 9, 6, 10]
935
        """
936
        if self.is_i_grassmannian(side=side): return self
937
        c=list(self.to_lehmer_code(typ,side))
938
        c.sort()
939
        c.reverse()
940
        return self.parent().from_lehmer_code(c, typ, side)
941

942
    def tableau_of_word(self, w, typ='decreasing', side='right', alpha=None):
943
        r"""
944
        Finds a tableau on the Lehmer code of ``self`` corresponding to the given
945
        reduced word.
946

947
        For a full description of this algorithm, see [D2012]_.
948

949
        INPUT:
950

951
        - ``w`` -- a reduced word for self.
952
        - ``typ`` --  'increasing' or 'decreasing.'  The type of Lehmer code used.
953
        - ``side`` -- 'right' or 'left.'
954
        - ``alpha`` -- A content vector.  w should be of type alpha.  Specifying
955
          alpha produces semistandard tableaux.
956

957
        REFERENCES:
958

959
        .. [D2012] tom denton. Canonical Decompositions of Affine Permutations,
960
           Affine Codes, and Split `k`-Schur Functions.  Electronic Journal of
961
           Combinatorics, 2012.
962

963
        EXAMPLES::
964

965
            sage: A=AffinePermutationGroup(['A',7,1])
966
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
967
            sage: p.tableau_of_word(p.reduced_word())
968
            [[], [1, 6, 9], [2, 7, 10], [], [3], [4, 8], [], [5]]
969
            sage: A=AffinePermutationGroup(['A',7,1])
970
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
971
            sage: w=p.reduced_word()
972
            sage: w
973
            [0, 7, 4, 1, 0, 7, 5, 4, 2, 1]
974
            sage: alpha=[5,3,2]
975
            sage: p.tableau_of_word(p.reduced_word(), alpha=alpha)
976
            [[], [1, 2, 3], [1, 2, 3], [], [1], [1, 2], [], [1]]
977
            sage: p.tableau_of_word(p.reduced_word(), side='left')
978
            [[1, 4, 9], [6], [], [], [3, 7], [8], [], [2, 5, 10]]
979
            sage: p.tableau_of_word(p.reduced_word(), typ='increasing', side='right')
980
            [[9, 10], [1, 2], [], [], [3, 4], [8], [], [5, 6, 7]]
981
            sage: p.tableau_of_word(p.reduced_word(), typ='increasing', side='left')
982
            [[1, 2], [4, 5, 6], [9, 10], [], [3], [7, 8], [], []]
983
        """
984
        g=self.parent().simple_reflections()
985
        #check w is reduced....:should probably throw an exception otherwise.
986
        x0=prod([g[i] for i in w])
987
        if x0.length()!=len(w): raise ValueError("Word was not reduced.")
988
        if alpha==None:
989
            alpha=Composition([1 for i in w])
990
        else:
991
            if sum(alpha)!=len(w): raise ValueError("Size of alpha must match length of w.")
992
            alpha=Composition(alpha)
993
        #TODO: We should probably check that w is of type alpha! probably a different function.
994
        #Now we actually build the recording tableau.
995
        tab=[ [] for i in xrange(self.k+1) ]
996
        label=1
997
        al_index=0
998
        j=0
999
        x=self.parent().one()
1000
        cx=x.to_lehmer_code(typ, side)
1001
        n=len(w)-1
1002
        for i in xrange(len(w)):
1003
            if side[0]=='r':
1004
                #y=g[w[n-i]]*x
1005
                y=x.apply_simple_reflection_left(w[n-i])
1006
            else:
1007
                y=x.apply_simple_reflection_right(w[i])
1008
            cy=y.to_lehmer_code(typ, side)
1009
            for r in xrange(self.k+1):
1010
                if cy[r]>cx[r]:
1011
                    tab[r].append(label)
1012
                    j+=1
1013
                    if j==alpha[al_index]:
1014
                        al_index+=1
1015
                        j=0
1016
                        label+=1
1017
                    break
1018
            x=y
1019
            cx=cy
1020
        return tab
1021

1022
#-------------------------------------------------------------------------------
1023
class AffinePermutationTypeC(AffinePermutation):
1024
    #----------------------
1025
    #Type-specific methods.
1026
    #(Methods existing in all types, but with type-specific definition.)
1027
    #----------------------
1028
    def check(self):
1029
        r"""
1030
        Check that ``self`` is an affine permutation.
1031

1032
        EXAMPLES::
1033

1034
            sage: C=AffinePermutationGroup(['C',4,1])
1035
            sage: x=C([-1,5,3,7])
1036
            sage: x
1037
            Type C affine permutation with window [-1, 5, 3, 7]
1038
        """
1039
        if not self:
1040
            return
1041
        k=self.parent().k
1042
        if not len(self)==k: raise ValueError( "Length of list must be k="+str(k)+".")
1043
        reslist=[]
1044
        for i in self:
1045
            r=i%self.N
1046
            if r==0: raise ValueError( "Entries may not have residue 0 mod 2k+1.")
1047
            if not (r not in reslist and self.N-r not in reslist): raise ValueError( "Entries must have distinct residues.")
1048
            reslist.append(r)
1049

1050
    def value(self, i):
1051
        r"""
1052
        Returns the image of the integer `i` under this permutation.
1053

1054
        EXAMPLES::
1055

1056
            sage: C=AffinePermutationGroup(['C',4,1])
1057
            sage: x=C.one()
1058
            sage: [x.value(i) for i in range(-10,10)]==range(-10,10)
1059
            True
1060
        """
1061
        N=(2*self.k+1)
1062
        window=i//N
1063
        index=i%N
1064
        if index==0: return i
1065
        if index<=self.k:
1066
            return self[index-1]+window*N
1067
        if index>self.k:
1068
            return -(self[N-index-1]-N)+window*N
1069

1070
    def position(self, i):
1071
        r"""
1072
        Find the position `j` such the ``self.value(j)=i``
1073

1074
        EXAMPLES::
1075

1076
            sage: C=AffinePermutationGroup(['C',4,1])
1077
            sage: x=C.one()
1078
            sage: [x.position(i) for i in range(-10,10)]==range(-10,10)
1079
            True
1080
        """
1081
        N=(2*self.k+1)
1082
        index=i%N
1083
        if index==0: return i
1084
        for r in xrange(len(self)):
1085
            if (self[r]%N)==index:
1086
                #i sits in position i, but some number of windows away.
1087
                diff=(i-self[r])//N
1088
                return r+diff*N+1
1089
            if (self[r]%N)==N-index:
1090
                #then we sit some number of windows from position -r.
1091
                diff=(i+self[r])//N
1092
                return -r+diff*N-1
1093
        return False
1094

1095
    def apply_simple_reflection_right(self, i):
1096
        r"""
1097
        Applies the simple reflection indexed by `i` on positions.
1098

1099
        EXAMPLES::
1100

1101
            sage: C=AffinePermutationGroup(['C',4,1])
1102
            sage: x=C([-1,5,3,7])
1103
            sage: for i in C.index_set(): x.apply_simple_reflection_right(i)
1104
            Type C affine permutation with window [1, 5, 3, 7]
1105
            Type C affine permutation with window [5, -1, 3, 7]
1106
            Type C affine permutation with window [-1, 3, 5, 7]
1107
            Type C affine permutation with window [-1, 5, 7, 3]
1108
            Type C affine permutation with window [-1, 5, 3, 2]
1109
        """
1110
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1111
        j=i
1112
        l = self[:]
1113
        if j!=0 and j!=self.k:
1114
            a = l[j-1]
1115
            l[j-1] = l[j]
1116
            l[j] = a
1117
        if j==0:
1118
            l[0]=-l[0]
1119
        if j==self.k:
1120
            l[self.k-1]=self(self.k+1)
1121
        #return l
1122
        return self.parent()(l,check=False)
1123

1124
    def apply_simple_reflection_left(self, i):
1125
        r"""
1126
        Applies simple reflection indexed by `i` on values.
1127

1128
        EXAMPLES::
1129

1130
            sage: C=AffinePermutationGroup(['C',4,1])
1131
            sage: x=C([-1,5,3,7])
1132
            sage: for i in C.index_set(): x.apply_simple_reflection_left(i)
1133
            Type C affine permutation with window [1, 5, 3, 7]
1134
            Type C affine permutation with window [-2, 5, 3, 8]
1135
            Type C affine permutation with window [-1, 5, 2, 6]
1136
            Type C affine permutation with window [-1, 6, 4, 7]
1137
            Type C affine permutation with window [-1, 4, 3, 7]
1138
        """
1139
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1140
        j=self.N-i
1141
        l=[]
1142
        if i!=self.k and i!=0:
1143
            for m in xrange(self.k):
1144
                res=self[m]%self.N
1145
                if res==i  :
1146
                    l.append(self[m]+1)
1147
                elif res==i+1:
1148
                    l.append(self[m]-1)
1149
                elif res==j:
1150
                    l.append(self[m]-1)
1151
                elif res==j-1:
1152
                    l.append(self[m]+1)
1153
                else:
1154
                    l.append(self[m])
1155
        elif i==0:
1156
            for m in xrange(self.k):
1157
                res=self[m]%self.N
1158
                if res==1:
1159
                    l.append(self[m]-2)
1160
                elif res==self.N-1:
1161
                    l.append(self[m]+2)
1162
                else:
1163
                    l.append(self[m])
1164
        elif i==self.k:
1165
            for m in xrange(self.k):
1166
                res=self[m]%self.N
1167
                if res==i:
1168
                    l.append(self[m]+1)
1169
                elif res==j:
1170
                    l.append(self[m]-1)
1171
                else:
1172
                    l.append(self[m])
1173
        return self.parent()(l, check=False)
1174

1175
    def has_right_descent(self, i):
1176
        r"""
1177
        Determines whether there is a descent at index `i`.
1178

1179
        INPUT:
1180

1181
        - ``i`` -- an integer.
1182

1183
        EXAMPLES::
1184

1185
            sage: C=AffinePermutationGroup(['C',4,1])
1186
            sage: x=C([-1,5,3,7])
1187
            sage: for i in C.index_set(): x.has_right_descent(i)
1188
            True
1189
            False
1190
            True
1191
            False
1192
            True
1193
        """
1194
        return self.value(i)>self.value(i+1)
1195

1196
    def has_left_descent(self, i):
1197
        r"""
1198
        Determines whether there is a descent at `i`.
1199

1200
        INPUT:
1201

1202
        - ``i`` -- an integer.
1203

1204
        EXAMPLES::
1205

1206
            sage: C=AffinePermutationGroup(['C',4,1])
1207
            sage: x=C([-1,5,3,7])
1208
            sage: for i in C.index_set(): x.has_left_descent(i)
1209
            True
1210
            False
1211
            True
1212
            False
1213
            True
1214
        """
1215
        #This is much faster thant he default method of taking the inverse and
1216
        #then finding right descents...
1217
        return self.position(i)>self.position(i+1)
1218

1219
    def to_type_a(self):
1220
        r"""
1221
        Returns an embedding of ``self`` into the affine permutation group of
1222
        type `A`.
1223

1224
        EXAMPLES::
1225

1226
            sage: C=AffinePermutationGroup(['C',4,1])
1227
            sage: x=C([-1,5,3,7])
1228
            sage: x.to_type_a()
1229
            Type A affine permutation with window [-1, 5, 3, 7, 2, 6, 4, 10, 9]
1230
        """
1231
        A=AffinePermutationGroup(['A', self.N-1, 1])
1232
        return A([self.value(i) for i in range(1,self.N+1)])
1233

1234

1235
class AffinePermutationTypeB(AffinePermutationTypeC):
1236
    #----------------------
1237
    #Type-specific methods.
1238
    #(Methods existing in all types, but with type-specific definition.)
1239
    #----------------------
1240
    def check(self):
1241
        r"""
1242
        Check that ``self`` is an affine permutation.
1243

1244
        EXAMPLES::
1245

1246
            sage: B=AffinePermutationGroup(['B',4,1])
1247
            sage: x=B([-5,1,6,-2])
1248
            sage: x
1249
            Type B affine permutation with window [-5, 1, 6, -2]
1250
        """
1251
        if not self:
1252
            return
1253
        k=self.parent().k
1254
        #Check window length.
1255
        if not len(self)==k: raise ValueError( "Length of list must be k="+str(k)+".")
1256
        #Check for repeated residues.
1257
        reslist=[]
1258
        for i in self:
1259
            r=i%self.N
1260
            if r==0: raise ValueError( "Entries may not have residue 0 mod 2k+1.")
1261
            if not( r not in reslist and self.N-r not in reslist ): raise ValueError( "Entries must have distinct residues.")
1262
            reslist.append(r)
1263
        #Check that we have an even number of 'small' elements right of the zeroth entry.
1264
        s=sum([-i//self.N+1 for i in [self.value(j) for j in range(1,self.N+1)] if i<0])
1265
        if not s%2==0: raise ValueError( 'Type B affine permutations have an even number of entries less than 0 to the right of the 0th position.')
1266

1267

1268
    def apply_simple_reflection_right(self, i):
1269
        r"""
1270
        Applies the simple reflection indexed by `i` on positions.
1271

1272
        EXAMPLES::
1273

1274
            sage: B=AffinePermutationGroup(['B',4,1])
1275
            sage: p=B([-5,1,6,-2])
1276
            sage: p.apply_simple_reflection_right(1)
1277
            Type B affine permutation with window [1, -5, 6, -2]
1278
            sage: p.apply_simple_reflection_right(0)
1279
            Type B affine permutation with window [-1, 5, 6, -2]
1280
            sage: p.apply_simple_reflection_right(4)
1281
            Type B affine permutation with window [-5, 1, 6, 11]
1282
        """
1283
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1284
        j=i
1285
        l = self[:]
1286
        if j!=0 and j!=self.k:
1287
            #just swap l[j], l[j-1]
1288
            (l[j-1],l[j])=(l[j],l[j-1])
1289
        if j==0:
1290
            l[0]=-self(2)
1291
            l[1]=-self(1)
1292
        if j==self.k:
1293
            l[self.k-1]=self(self.k+1)
1294
        #return l
1295
        return self.parent()(l,check=False)
1296

1297
    def apply_simple_reflection_left(self, i):
1298
        r"""
1299
        Applies simple reflection indexed by `i` on values.
1300

1301
        EXAMPLES::
1302

1303
            sage: B=AffinePermutationGroup(['B',4,1])
1304
            sage: p=B([-5,1,6,-2])
1305
            sage: p.apply_simple_reflection_left(0)
1306
            Type B affine permutation with window [-5, -2, 6, 1]
1307
            sage: p.apply_simple_reflection_left(2)
1308
            Type B affine permutation with window [-5, 1, 7, -3]
1309
            sage: p.apply_simple_reflection_left(4)
1310
            Type B affine permutation with window [-4, 1, 6, -2]
1311
        """
1312
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1313
        j=self.N-i
1314
        l=[]
1315
        if i!=self.k and i!=0:
1316
            for m in xrange(self.k):
1317
                res=self[m]%self.N
1318
                if res==i  :
1319
                    l.append(self[m]+1)
1320
                elif res==i+1:
1321
                    l.append(self[m]-1)
1322
                elif res==j:
1323
                    l.append(self[m]-1)
1324
                elif res==j-1:
1325
                    l.append(self[m]+1)
1326
                else:
1327
                    l.append(self[m])
1328
        elif i==0:
1329
            for m in xrange(self.k):
1330
                res=self[m]%self.N
1331
                if res==1:
1332
                    l.append(self[m]-3)
1333
                elif res==self.N-2:
1334
                    l.append(self[m]+3)
1335
                elif res==2:
1336
                    l.append(self[m]-3)
1337
                elif res==self.N-1:
1338
                    l.append(self[m]+3)
1339
                else:
1340
                    l.append(self[m])
1341
        elif i==self.k:
1342
            for m in xrange(self.k):
1343
                res=self[m]%self.N
1344
                if res==i:
1345
                    l.append(self[m]+1)
1346
                elif res==j:
1347
                    l.append(self[m]-1)
1348
                else:
1349
                    l.append(self[m])
1350
        return self.parent()(l, check=False)
1351

1352
    def has_right_descent(self, i):
1353
        r"""
1354
        Determines whether there is a descent at index `i`.
1355

1356
        INPUT:
1357

1358
        - ``i`` -- an integer.
1359

1360
        EXAMPLES::
1361

1362
            sage: B=AffinePermutationGroup(['B',4,1])
1363
            sage: p=B([-5,1,6,-2])
1364
            sage: [p.has_right_descent(i) for i in B.index_set()]
1365
            [True, False, False, True, False]
1366
        """
1367
        if i==0: return self.value(-2)>self.value(1)
1368
        return self.value(i)>self.value(i+1)
1369

1370
    def has_left_descent(self, i):
1371
        r"""
1372
        Determines whether there is a descent at `i`.
1373

1374
        INPUT:
1375

1376
        - ``i`` -- an integer.
1377

1378
        EXAMPLES::
1379

1380
            sage: B=AffinePermutationGroup(['B',4,1])
1381
            sage: p=B([-5,1,6,-2])
1382
            sage: [p.has_left_descent(i) for i in B.index_set()]
1383
            [True, True, False, False, True]
1384
        """
1385
        if i==0: return self.position(-2)>self.position(1)
1386
        return self.position(i)>self.position(i+1)
1387

1388

1389
class AffinePermutationTypeD(AffinePermutationTypeC):
1390
    #----------------------
1391
    #Type-specific methods.
1392
    #(Methods existing in all types, but with type-specific definition.)
1393
    #----------------------
1394
    def check(self):
1395
        r"""
1396
        Check that ``self`` is an affine permutation.
1397

1398
        EXAMPLES::
1399

1400
            sage: D=AffinePermutationGroup(['D',4,1])
1401
            sage: p=D([1,-6,5,-2])
1402
            sage: p
1403
            Type D affine permutation with window [1, -6, 5, -2]
1404
        """
1405
        if not self:
1406
            return
1407
        k=self.parent().k
1408
        #Check window length.
1409
        if len(self)!=k: raise ValueError( "Length of list must be k="+str(k)+".")
1410
        #Check for repeated residues.
1411
        reslist=[]
1412
        for i in self:
1413
            r=i%self.N
1414
            if r==0: raise ValueError( "Entries may not have residue 0 mod 2k+1.")
1415
            if not ( r not in reslist and self.N-r not in reslist ): raise ValueError( "Entries must have distinct residues.")
1416
            reslist.append(r)
1417
        #Check that we have an even number of 'big' elements left of the kth entry.
1418
        s=sum([i//self.N+1-(i%self.N<=self.k) for i in [self.value(j) for j in range(-self.k,self.k+1)] if i>self.k])
1419
        if not s%2==0: raise ValueError( 'Type D affine permutations have an even number of entries greater than x.k weakly to the left of the x.k position.')
1420
        #Check that we have an even number of 'small' elements right of the zeroth entry.
1421
        s=sum([-i//self.N+1 for i in [self.value(j) for j in range(1,self.N+1)] if i<0])
1422
        if not s%2==0: raise ValueError( 'Type D affine permutations have an even number of entries less than 0 to the right of the 0th position.')
1423

1424
    def apply_simple_reflection_right(self, i):
1425
        r"""
1426
        Applies the simple reflection indexed by `i` on positions.
1427

1428
        EXAMPLES::
1429

1430
            sage: D=AffinePermutationGroup(['D',4,1])
1431
            sage: p=D([1,-6,5,-2])
1432
            sage: p.apply_simple_reflection_right(0)
1433
            Type D affine permutation with window [6, -1, 5, -2]
1434
            sage: p.apply_simple_reflection_right(1)
1435
            Type D affine permutation with window [-6, 1, 5, -2]
1436
            sage: p.apply_simple_reflection_right(4)
1437
            Type D affine permutation with window [1, -6, 11, 4]
1438
        """
1439
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1440
        j=i
1441
        l = self[:]
1442
        if j!=0 and j!=self.k:
1443
            a = l[j-1]
1444
            l[j-1] = l[j]
1445
            l[j] = a
1446
        if j==0:
1447
            c=l[0]
1448
            l[0]=-l[1]
1449
            l[1]=-c
1450
        if j==self.k:
1451
            l[self.k-2]=self(self.k+1)
1452
            l[self.k-1]=self(self.k+2)
1453
        #return l
1454
        return self.parent()(l,check=False)
1455

1456
    def apply_simple_reflection_left(self, i):
1457
        r"""
1458
        Applies simple reflection indexed by `i` on values.
1459

1460
        EXAMPLES::
1461

1462
            sage: D=AffinePermutationGroup(['D',4,1])
1463
            sage: p=D([1,-6,5,-2])
1464
            sage: p.apply_simple_reflection_left(0)
1465
            Type D affine permutation with window [-2, -6, 5, 1]
1466
            sage: p.apply_simple_reflection_left(1)
1467
            Type D affine permutation with window [2, -6, 5, -1]
1468
            sage: p.apply_simple_reflection_left(4)
1469
            Type D affine permutation with window [1, -4, 3, -2]
1470
        """
1471
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1472
        j=self.N-i
1473
        l=[]
1474
        if i!=self.k and i!=0:
1475
            for m in xrange(self.k):
1476
                res=self[m]%self.N
1477
                if res==i  :
1478
                    l.append(self[m]+1)
1479
                elif res==i+1:
1480
                    l.append(self[m]-1)
1481
                elif res==j:
1482
                    l.append(self[m]-1)
1483
                elif res==j-1:
1484
                    l.append(self[m]+1)
1485
                else:
1486
                    l.append(self[m])
1487
        elif i==0:
1488
            for m in xrange(self.k):
1489
                res=self[m]%self.N
1490
                if res==1:
1491
                    l.append(self[m]-3)
1492
                elif res==self.N-2:
1493
                    l.append(self[m]+3)
1494
                elif res==2:
1495
                    l.append(self[m]-3)
1496
                elif res==self.N-1:
1497
                    l.append(self[m]+3)
1498
                else:
1499
                    l.append(self[m])
1500
        elif i==self.k:
1501
            for m in xrange(self.k):
1502
                res=self[m]%self.N
1503
                if res==self.k:
1504
                    l.append(self[m]+2)
1505
                elif res==self.k+2:
1506
                    l.append(self[m]-2)
1507
                elif res==self.k-1:
1508
                    l.append(self[m]+2)
1509
                elif res==self.k+1:
1510
                    l.append(self[m]-2)
1511
                else:
1512
                    l.append(self[m])
1513
        return self.parent()(l, check=False)
1514

1515
    def has_right_descent(self, i):
1516
        r"""
1517
        Determines whether there is a descent at index `i`.
1518

1519
        INPUT:
1520

1521
        - ``i`` -- an integer.
1522

1523
        EXAMPLES::
1524

1525
            sage: D=AffinePermutationGroup(['D',4,1])
1526
            sage: p=D([1,-6,5,-2])
1527
            sage: [p.has_right_descent(i) for i in D.index_set()]
1528
            [True, True, False, True, False]
1529
        """
1530
        if i==0: return self.value(-2)>self.value(1)
1531
        if i==self.k: return self.value(i)>self.value(i+2)
1532
        return self.value(i)>self.value(i+1)
1533

1534
    def has_left_descent(self, i):
1535
        r"""
1536
        Determines whether there is a descent at `i`.
1537

1538
        INPUT:
1539

1540
        - ``i`` -- an integer.
1541

1542
        EXAMPLES::
1543

1544
            sage: D=AffinePermutationGroup(['D',4,1])
1545
            sage: p=D([1,-6,5,-2])
1546
            sage: [p.has_left_descent(i) for i in D.index_set()]
1547
            [True, True, False, True, True]
1548
        """
1549
        if i==0: return self.position(-2)>self.position(1)
1550
        if i==self.k: return self.position(i)>self.position(i+2)
1551
        return self.position(i)>self.position(i+1)
1552

1553

1554
class AffinePermutationTypeG(AffinePermutation):
1555
    #----------------------
1556
    #Type-specific methods.
1557
    #(Methods existing in all types, but with type-specific definition.)
1558
    #----------------------
1559
    def check(self):
1560
        r"""
1561
        Check that ``self`` is an affine permutation.
1562

1563
        EXAMPLES::
1564

1565
            sage: G=AffinePermutationGroup(['G',2,1])
1566
            sage: p=G([2, 10, -5, 12, -3, 5])
1567
            sage: p
1568
            Type G affine permutation with window [2, 10, -5, 12, -3, 5]
1569
        """
1570
        if not self:
1571
            return
1572
        if not len(self)==6: raise ValueError( "Length of list must be 6.")
1573
        #Check that we have an even number of 'big' elements left of the 7th entry.
1574
        s=sum([i//6-(i%6==0) for i in self._lst if i>6])
1575
        if not s%2==0: raise ValueError( 'Type G affine permutations have an even number of entries greater than 6 to the left of the 7th position.')
1576
        #Check that we have an even number of 'small' elements right of the zeroth entry.
1577
        s=sum([-i//6+1 for i in self._lst if i<=0])
1578
        if not s%2==0: raise ValueError( 'Type G affine permutations have an even number of entries less than 0 to the right of the 0th position.')
1579

1580
    def value(self, i, base_window=False):
1581
        r"""
1582
        Returns the image of the integer `i` under this permutation.
1583

1584
        INPUT:
1585

1586
        - ``base_window`` -- a Boolean indicating whether `i` is between 1 and
1587
          `k+1`.  If True, will run a bit faster, but the method will screw up
1588
          if `i` is not actually in the index set.
1589

1590
        EXAMPLES::
1591

1592
            sage: G=AffinePermutationGroup(['G',2,1])
1593
            sage: p=G([2, 10, -5, 12, -3, 5])
1594
            sage: [p.value(i) for i in [1..12]]
1595
            [2, 10, -5, 12, -3, 5, 8, 16, 1, 18, 3, 11]
1596
        """
1597
        N=6
1598
        if base_window: self[i-1]
1599
        window=(i-1)//N
1600
        return self[(i-1)%N]+window*(N)
1601

1602
    def position(self, i):
1603
        r"""
1604
        Find the position `j` such the ``self.value(j)=i``
1605

1606
        EXAMPLES::
1607

1608
            sage: G=AffinePermutationGroup(['G',2,1])
1609
            sage: p=G([2, 10, -5, 12, -3, 5])
1610
            sage: [p.position(i) for i in p._lst]
1611
            [1, 2, 3, 4, 5, 6]
1612
        """
1613
        N=6
1614
        for r in xrange(N):
1615
            if self[r]%N==i%N:
1616
                #i sits in position i, but some number of windows away.
1617
                diff=(i-self[r])//N
1618
                return r+diff*N+1
1619
        return False
1620

1621
    def apply_simple_reflection_right(self, i):
1622
        r"""
1623
        Applies the simple reflection indexed by `i` on positions.
1624

1625
        EXAMPLES::
1626

1627
            sage: G=AffinePermutationGroup(['G',2,1])
1628
            sage: p=G([2, 10, -5, 12, -3, 5])
1629
            sage: p.apply_simple_reflection_right(0)
1630
            Type G affine permutation with window [-9, -1, -5, 12, 8, 16]
1631
            sage: p.apply_simple_reflection_right(1)
1632
            Type G affine permutation with window [10, 2, 12, -5, 5, -3]
1633
            sage: p.apply_simple_reflection_right(2)
1634
            Type G affine permutation with window [2, -5, 10, -3, 12, 5]
1635
        """
1636
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1637
        j=i
1638
        l = self[:]
1639
        if j==1:
1640
            l[0]=self(2)
1641
            l[1]=self(1)
1642
            l[2]=self(4)
1643
            l[3]=self(3)
1644
            l[4]=self(6)
1645
            l[5]=self(5)
1646
        elif j==2:
1647
            l[1]=self(3)
1648
            l[2]=self(2)
1649
            l[3]=self(5)
1650
            l[4]=self(4)
1651
        elif j==0:
1652
            l[0]=self(-1)
1653
            l[1]=self(0)
1654
            l[4]=self(7)
1655
            l[5]=self(8)
1656
        #return l
1657
        return self.parent()(l,check=False)
1658

1659
    def apply_simple_reflection_left(self, i):
1660
        r"""
1661
        Applies simple reflection indexed by `i` on values.
1662

1663
        EXAMPLES::
1664

1665
            sage: G=AffinePermutationGroup(['G',2,1])
1666
            sage: p=G([2, 10, -5, 12, -3, 5])
1667
            sage: p.apply_simple_reflection_left(0)
1668
            Type G affine permutation with window [0, 10, -7, 14, -3, 7]
1669
            sage: p.apply_simple_reflection_left(1)
1670
            Type G affine permutation with window [1, 9, -4, 11, -2, 6]
1671
            sage: p.apply_simple_reflection_left(2)
1672
            Type G affine permutation with window [3, 11, -5, 12, -4, 4]
1673
        """
1674
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1675
        l=[]
1676
        if i==1:
1677
            for m in xrange(6):
1678
                res=self[m]%6
1679
                if res==1 or res==3 or res==5:
1680
                    l.append(self[m]+1)
1681
                elif res==2 or res==4 or res==0:
1682
                    l.append(self[m]-1)
1683
                else:
1684
                    l.append(self[m])
1685
        elif i==2:
1686
            for m in xrange(6):
1687
                res=self[m]%6
1688
                if res==2 or res==4:
1689
                    l.append(self[m]+1)
1690
                elif res==3 or res==5:
1691
                    l.append(self[m]-1)
1692
                else:
1693
                    l.append(self[m])
1694
        elif i==0:
1695
            for m in xrange(6):
1696
                res=self[m]%6
1697
                if res==1 or res==2:
1698
                    l.append(self[m]-2)
1699
                elif res==5 or res==0:
1700
                    l.append(self[m]+2)
1701
                else:
1702
                    l.append(self[m])
1703
        return self.parent()(l, check=False)
1704

1705
    def has_right_descent(self, i):
1706
        r"""
1707
        Determines whether there is a descent at index `i`.
1708

1709
        INPUT:
1710

1711
        - ``i`` -- an integer.
1712

1713
        EXAMPLES::
1714

1715
            sage: G=AffinePermutationGroup(['G',2,1])
1716
            sage: p=G([2, 10, -5, 12, -3, 5])
1717
            sage: [p.has_right_descent(i) for i in G.index_set()]
1718
            [False, False, True]
1719
        """
1720
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1721
        if i==0: return self.value(0)>self.value(2)
1722
        return self.value(i)>self.value(i+1)
1723

1724
    def has_left_descent(self, i):
1725
        r"""
1726
        Determines whether there is a descent at `i`.
1727

1728
        INPUT:
1729

1730
        - ``i`` -- an integer.
1731

1732
        EXAMPLES::
1733

1734
            sage: G=AffinePermutationGroup(['G',2,1])
1735
            sage: p=G([2, 10, -5, 12, -3, 5])
1736
            sage: [p.has_left_descent(i) for i in G.index_set()]
1737
            [False, True, False]
1738
        """
1739
        if not i in self.parent().index_set(): raise ValueError('Index not in index set.')
1740
        if i==0: return self.position(0)>self.position(2)
1741
        return self.position(i)>self.position(i+1)
1742

1743
    def to_type_a(self):
1744
        r"""
1745
        Returns an embedding of ``self`` into the affine permutation group of
1746
        type A.
1747

1748
        EXAMPLES::
1749

1750
            sage: G=AffinePermutationGroup(['G',2,1])
1751
            sage: p=G([2, 10, -5, 12, -3, 5])
1752
            sage: p.to_type_a()
1753
            Type A affine permutation with window [2, 10, -5, 12, -3, 5]
1754
        """
1755
        A=AffinePermutationGroup(['A', 5, 1])
1756
        return A(self._lst)
1757

1758

1759

1760

1761
#-------------------------------------------------------------------------
1762
#    Class of all affine permutations.
1763
#-------------------------------------------------------------------------
1764

1765
def AffinePermutationGroup(cartan_type):
1766
    """
1767
    Wrapper function for specific affine permutation groups.
1768

1769
    These are combinatorial implmentations of the affine Weyl groups of
1770
    types `A`, `B`, `C`, `D`, and `G` as permutations of the set of all integers.
1771
    the basic algorithms are derived from [BjBr]_ and [Erik]_.
1772

1773
    REFERENCES:
1774

1775
    .. [BjBr] Bjorner and Brenti. Combinatorics of Coxeter Groups. Springer, 2005.
1776
    .. [Erik] H. Erikson.  Computational and Combinatorial Aspects of Coxeter
1777
       Groups.  Thesis, 1995.
1778

1779
    EXAMPLES::
1780

1781
        sage: ct=CartanType(['A',7,1])
1782
        sage: A=AffinePermutationGroup(ct)
1783
        sage: A
1784
        The group of affine permutations of type ['A', 7, 1]
1785

1786
    We define an element of ``A``:
1787
    ::
1788

1789
        sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
1790
        sage: p
1791
        Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
1792

1793
    We find the value `p(1)`, considering `p` as a bijection on the integers.  This
1794
    is the same as calling the 'value' method:
1795
    ::
1796

1797
        sage: p.value(1)
1798
        3
1799
        sage: p(1)==p.value(1)
1800
        True
1801

1802
    We can also find the position of the integer 3 in  `p` considered as a sequence,
1803
    equivalent to finding `p^{-1}(3)`:
1804
    ::
1805

1806
        sage: p.position(3)
1807
        1
1808
        sage: (p^-1)(3)
1809
        1
1810

1811
    Since the affine permutation group is a group, we demonstrate its group properties:
1812
    ::
1813

1814
        sage: A.one()
1815
        Type A affine permutation with window [1, 2, 3, 4, 5, 6, 7, 8]
1816

1817
        sage: q=A([0, 2, 3, 4, 5, 6, 7, 9])
1818
        sage: p*q
1819
        Type A affine permutation with window [1, -1, 0, 6, 5, 4, 10, 11]
1820
        sage: q*p
1821
        Type A affine permutation with window [3, -1, 1, 6, 5, 4, 10, 8]
1822

1823
        sage: p^-1
1824
        Type A affine permutation with window [0, -1, 1, 6, 5, 4, 10, 11]
1825
        sage: p^-1*p==A.one()
1826
        True
1827
        sage: p*p^-1==A.one()
1828
        True
1829

1830
    If we decide we prefer the Weyl Group implementation of the affine Weyl
1831
    group, we can easily get it:
1832
    ::
1833

1834
        sage: p.to_weyl_group_element()
1835
        [ 0 -1  0  1  0  0  1  0]
1836
        [ 1 -1  0  1  0  0  1 -1]
1837
        [ 1 -1  0  1  0  0  0  0]
1838
        [ 0  0  0  1  0  0  0  0]
1839
        [ 0  0  0  1  0 -1  1  0]
1840
        [ 0  0  0  1 -1  0  1  0]
1841
        [ 0  0  0  0  0  0  1  0]
1842
        [ 0 -1  1  0  0  0  1  0]
1843

1844
    We can find a reduced word and do all of the other things one expects in
1845
    a Coxeter group:
1846
    ::
1847

1848
        sage: p.has_right_descent(1)
1849
        True
1850
        sage: p.apply_simple_reflection(1)
1851
        Type A affine permutation with window [-1, 3, 0, 6, 5, 4, 10, 9]
1852
        sage: p.apply_simple_reflection(0)
1853
        Type A affine permutation with window [1, -1, 0, 6, 5, 4, 10, 11]
1854
        sage: p.reduced_word()
1855
        [0, 7, 4, 1, 0, 7, 5, 4, 2, 1]
1856
        sage: p.length()
1857
        10
1858

1859
    The following methods are particular to Type `A`.
1860
    We can check if the element is fully commutative:
1861
    ::
1862

1863
        sage: p.is_fully_commutative()
1864
        False
1865
        sage: q.is_fully_commutative()
1866
        True
1867

1868
    And we can also compute the affine Lehmer code of the permutation, a weak
1869
    composition with `k+1` entries:
1870
    ::
1871

1872
        sage: p.to_lehmer_code()
1873
        [0, 3, 3, 0, 1, 2, 0, 1]
1874

1875
    Once we have the Lehmer code, we can obtain a `k`-bounded partition by
1876
    sorting the Lehmer code, and then reading the row lengths.
1877
    There is a unique 0-Grassmanian (dominant) affine permutation associated
1878
    to this `k`-bounded partition, and a `k`-core as well.
1879
    ::
1880

1881
        sage: p.to_bounded_partition()
1882
        [5, 3, 2]
1883
        sage: p.to_dominant()
1884
        Type A affine permutation with window [-2, -1, 1, 3, 4, 8, 10, 13]
1885
        sage: p.to_core()
1886
        [5, 3, 2]
1887

1888
    Finally, we can take a reduced word for `p` and insert it to find a
1889
    standard composition tableau associated uniquely to that word.
1890
    ::
1891

1892
        sage: p.tableau_of_word(p.reduced_word())
1893
        [[], [1, 6, 9], [2, 7, 10], [], [3], [4, 8], [], [5]]
1894

1895
    We can also form affine permutation groups in types `B`, `C`, `D`, and `G`.
1896
    ::
1897

1898
        sage: B=AffinePermutationGroup(['B',4,1])
1899
        sage: B.an_element()
1900
        Type B affine permutation with window [-1, 3, 4, 11]
1901

1902
        sage: C=AffinePermutationGroup(['C',4,1])
1903
        sage: C.an_element()
1904
        Type C affine permutation with window [2, 3, 4, 10]
1905

1906
        sage: D=AffinePermutationGroup(['D',4,1])
1907
        sage: D.an_element()
1908
        Type D affine permutation with window [-1, 3, 11, 5]
1909

1910
        sage: G=AffinePermutationGroup(['G',2,1])
1911
        sage: G.an_element()
1912
        Type G affine permutation with window [0, 4, -1, 8, 3, 7]
1913
    """
1914
    ct=CartanType(cartan_type)
1915
    if ct.letter=='A': return AffinePermutationGroupTypeA(ct)
1916
    if ct.letter=='B': return AffinePermutationGroupTypeB(ct)
1917
    if ct.letter=='C': return AffinePermutationGroupTypeC(ct)
1918
    if ct.letter=='D': return AffinePermutationGroupTypeD(ct)
1919
    if ct.letter=='G': return AffinePermutationGroupTypeG(ct)
1920
    raise NotImplementedError('Cartan type provided is not implemented as an affine permutation group.')
1921

1922

1923
class AffinePermutationGroupGeneric(UniqueRepresentation, Parent):
1924
    """
1925
    The generic affine permutation group class, in which we define all type-free
1926
    methods for the specific affine permutation groups.
1927
    """
1928

1929
    #----------------------
1930
    #Type-free methods.
1931
    #----------------------
1932

1933
    def __init__(self, cartan_type):
1934
        r"""
1935
        TESTS::
1936

1937
            sage: AffinePermutationGroup(['A',7,1])
1938
            The group of affine permutations of type ['A', 7, 1]
1939
        """
1940
        Parent.__init__(self, category = AffineWeylGroups())
1941
        ct=CartanType(cartan_type)
1942
        self.k=ct.n
1943
        self.n=ct.rank()
1944
        #This N doesn't matter for type A, but comes up in all other types.
1945
        if ct.letter=='A':
1946
            self.N=self.k+1
1947
        elif ct.letter=='B' or ct.letter=='C' or ct.letter=='D':
1948
            self.N=2*self.k+1
1949
        elif ct.letter=='G':
1950
            self.N=6
1951
        self._cartan_type=ct
1952

1953
    def _element_constructor_(self, *args, **keywords):
1954
        r"""
1955
        TESTS::
1956

1957
            sage: AffinePermutationGroup(['A',7,1])([3, -1, 0, 6, 5, 4, 10, 9])
1958
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
1959
        """
1960
        return self.element_class(self, *args, **keywords)
1961

1962
    def _repr_(self):
1963
        r"""
1964
        TESTS::
1965

1966
            sage: AffinePermutationGroup(['A',7,1])
1967
            The group of affine permutations of type ['A', 7, 1]
1968
        """
1969
        return "The group of affine permutations of type "+str(self.cartan_type())
1970

1971
    def _test_coxeter_relations(self, tester=None):
1972
        r"""
1973
        Tests whether the Coxeter relations hold for ``self``.
1974
        This should probably be implemented at the Coxeter groups level.
1975

1976
        TESTS::
1977

1978
            sage: A=AffinePermutationGroup(['A',7,1])
1979
            sage: A._test_coxeter_relations()
1980
        """
1981
        ct=self.cartan_type()
1982
        D=ct.coxeter_diagram()
1983
        s=self.simple_reflections()
1984
        for e in D.edges():
1985
            l=s[e[0]]*s[e[1]]
1986
            assert l**(e[2])==self.one(), 'Dynkin relation fails.'
1987

1988
    def _test_enumeration(self, n=4, tester=None):
1989
        r"""
1990
        Test that ``self`` has same number of elements of length ``n`` as the
1991
        Weyl Group implementation.
1992

1993
        Combined with ``self._test_coxeter_relations`` this shows isomorphism
1994
        up to length ``n``.
1995

1996
        TESTS::
1997

1998
            sage: A=AffinePermutationGroup(['A',7,1])
1999
            sage: A._test_coxeter_relations(3)
2000
        """
2001
        n1=len(list(self.elements_of_length(n)))
2002
        W=self.weyl_group()
2003
        I=W.weak_order_ideal(ConstantFunction(True), side='right')
2004
        n2=len(list(I.elements_of_depth_iterator(n)))
2005
        assert n1==n2, 'Number of (ranked) elements of affine permutation group disagrees with Weyl group.'
2006

2007
    def weyl_group(self):
2008
        r"""
2009
        Returns the Weyl Group of the same type as ``self``.
2010

2011
        EXAMPLES::
2012

2013
            sage: A=AffinePermutationGroup(['A',7,1])
2014
            sage: A.weyl_group()
2015
            Weyl Group of type ['A', 7, 1] (as a matrix group acting on the root space)
2016
        """
2017
        return WeylGroup(self._cartan_type)
2018

2019
    def classical(self):
2020
        r"""
2021
        Returns the finite permutation group.
2022

2023
        EXAMPLES::
2024

2025
            sage: A=AffinePermutationGroup(['A',7,1])
2026
            sage: A.classical()
2027
            Symmetric group of order 8! as a permutation group
2028
        """
2029
        if self._cartan_type.letter=='A':
2030
            return SymmetricGroup(self.k+1)
2031
        return WeylGroup(self._cartan_type.classical())
2032

2033
    def cartan_type(self):
2034
        r"""
2035
        Returns the Cartan type of ``self``.
2036

2037
        EXAMPLES::
2038

2039
            sage: AffinePermutationGroup(['A',7,1]).cartan_type()
2040
            ['A', 7, 1]
2041
        """
2042
        return self._cartan_type
2043

2044
    def cartan_matrix(self):
2045
        r"""
2046
        Returns the Cartan matrix of ``self``.
2047

2048
        EXAMPLES::
2049

2050
            sage: AffinePermutationGroup(['A',7,1]).cartan_matrix()
2051
            [ 2 -1  0  0  0  0  0 -1]
2052
            [-1  2 -1  0  0  0  0  0]
2053
            [ 0 -1  2 -1  0  0  0  0]
2054
            [ 0  0 -1  2 -1  0  0  0]
2055
            [ 0  0  0 -1  2 -1  0  0]
2056
            [ 0  0  0  0 -1  2 -1  0]
2057
            [ 0  0  0  0  0 -1  2 -1]
2058
            [-1  0  0  0  0  0 -1  2]
2059
        """
2060
        return self.cartan_type().cartan_matrix()
2061

2062
    def is_crystallographic(self):
2063
        r"""
2064
        Tells whether the affine permutation group is crystallographic.
2065

2066
        EXAMPLES::
2067

2068
            sage: AffinePermutationGroup(['A',7,1]).is_crystallographic()
2069
            True
2070
        """
2071
        return self.cartan_type().is_crystallographic()
2072

2073
    def index_set(self):
2074
        r"""
2075
        EXAMPLES::
2076

2077
            sage: AffinePermutationGroup(['A',7,1]).index_set()
2078
            (0, 1, 2, 3, 4, 5, 6, 7)
2079
        """
2080
        return self.cartan_type().index_set()
2081

2082
    _index_set=index_set
2083

2084
    def reflection_index_set(self):
2085
        r"""
2086
        EXAMPLES::
2087

2088
            sage: AffinePermutationGroup(['A',7,1]).index_set()
2089
            (0, 1, 2, 3, 4, 5, 6, 7)
2090
        """
2091
        return self.cartan_type().index_set()
2092

2093
    def rank(self):
2094
        r"""
2095
        Rank of the affine permutation group, equal to `k+1`.
2096

2097
        EXAMPLES::
2098

2099
            sage: AffinePermutationGroup(['A',7,1]).rank()
2100
            8
2101
        """
2102
        return self.k+1
2103

2104
    def random_element(self, n):
2105
        r"""
2106
        Returns a random affine permutation of length `n`.
2107

2108
        Starts at the identity, then chooses an upper cover at random.
2109
        Not very uniform: actually constructs a uniformly random reduced word
2110
        of length `n`.  Thus we most likely get elements with lots of reduced
2111
        words!
2112

2113
        EXAMPLES::
2114

2115
            sage: A=AffinePermutationGroup(['A',7,1])
2116
            sage: p=A.random_element(10)
2117
            sage: p.length()==10
2118
            True
2119
        """
2120
        x=self.one()
2121
        for i in xrange(1,n+1):
2122
            antiD=x.descents(positive=True)
2123
            x=x.apply_simple_reflection_right(antiD[ randint(0, len(antiD)-1) ])
2124
        return x
2125

2126
    def from_word(self, w):
2127
        r"""
2128
        Builds an affine permutation from a given word.
2129
        Note: Already in category as ``from_reduced_word``, but this is less
2130
        typing!
2131

2132
        EXAMPLES::
2133

2134
            sage: A=AffinePermutationGroup(['A',7,1])
2135
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
2136
            sage: A.from_word([0, 7, 4, 1, 0, 7, 5, 4, 2, 1])
2137
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
2138
        """
2139
        return self.from_reduced_word(w)
2140

2141
    @cached_method
2142
    def _an_element_(self):
2143
        r"""
2144
        Returns a Coxeter element.
2145

2146
        EXAMPLES::
2147

2148
            sage: A=AffinePermutationGroup(['A',7,1])
2149
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
2150
            sage: A.from_word([0, 7, 4, 1, 0, 7, 5, 4, 2, 1])
2151
            Type A affine permutation with window [3, -1, 0, 6, 5, 4, 10, 9]
2152
        """
2153
        return self.from_reduced_word(self.index_set())
2154

2155
    def elements_of_length(self, n):
2156
        r"""
2157
        Returns all elements of length `n`.
2158

2159
        EXAMPLES::
2160

2161
            sage: A=AffinePermutationGroup(['A',2,1])
2162
            sage: [len(list(A.elements_of_length(i))) for i in [0..5]]
2163
            [1, 3, 6, 9, 12, 15]
2164
        """
2165
        #Note: This is type-free, and should probably be included in Coxeter Groups.
2166
        I=self.weak_order_ideal(ConstantFunction(True), side='right')
2167
        return I.elements_of_depth_iterator(n)
2168

2169

2170
class AffinePermutationGroupTypeA(AffinePermutationGroupGeneric):
2171
    #------------------------
2172
    #Type-specific methods.
2173
    #(Methods in all types, but with specific definition.)
2174
    #------------------------
2175

2176
    def one(self):
2177
        r"""
2178
        Returns the identity element.
2179

2180
        EXAMPLES::
2181

2182
            sage: AffinePermutationGroup(['A',7,1]).one()
2183
            Type A affine permutation with window [1, 2, 3, 4, 5, 6, 7, 8]
2184

2185
        TESTS::
2186

2187
            sage: A=AffinePermutationGroup(['A',5,1])
2188
            sage: A==loads(dumps(A))
2189
            True
2190
            sage: TestSuite(A).run()
2191
        """
2192
        return self([i for i in xrange(1,self.k+2)])
2193

2194
    #------------------------
2195
    #Type-unique methods.
2196
    #(Methods which do not exist in all types.)
2197
    #------------------------
2198
    def from_lehmer_code(self, C, typ='decreasing', side='right'):
2199
        r"""
2200
        Returns the affine permutation with the supplied Lehmer code (a weak
2201
        composition with `k+1` parts, at least one of which is 0).
2202

2203
        INPUT:
2204

2205
        - ``typ`` -- 'increasing' or 'decreasing': type of product.
2206
            (default: 'decreasing'.)
2207
        - ``side`` -- 'right' or 'left': Whether the decomposition is from
2208
            the right or left. (default: 'right'.)
2209

2210
        EXAMPLES::
2211

2212
            sage: A=AffinePermutationGroup(['A',7,1])
2213
            sage: p=A([3, -1, 0, 6, 5, 4, 10, 9])
2214
            sage: p.to_lehmer_code()
2215
            [0, 3, 3, 0, 1, 2, 0, 1]
2216
            sage: A.from_lehmer_code(p.to_lehmer_code())==p
2217
            True
2218
            sage: CP=CartesianProduct( ('increasing','decreasing'),('left','right') )
2219
            sage: for a in CP:
2220
            ....:   A.from_lehmer_code(p.to_lehmer_code(a[0],a[1]),a[0],a[1])==p
2221
            True
2222
            True
2223
            True
2224
            True
2225
        """
2226
        if not len(C)-1==self.k: raise ValueError( "Composition must have "+str(self.k+1)+" entries." )
2227
        if not 0 in C: raise ValueError( "Composition must contain a zero entry." )
2228
        k=self.k
2229
        #Find a zero entry in C.
2230
        for r in xrange(self.k+1):
2231
            if C[r]==0: break
2232
        D=list(C)
2233
        #The s0 and t0 are +-1, dependent on typ and side.
2234
        if (typ[0],side[0])==('d','r'): (t0,s0)=(-1, 1)
2235
        if (typ[0],side[0])==('i','r'): (t0,s0)=( 1, 1)
2236
        if (typ[0],side[0])==('d','l'): (t0,s0)=(-1,-1)
2237
        if (typ[0],side[0])==('i','l'): (t0,s0)=( 1,-1)
2238
        row=0
2239
        #Method is to build a reduced word from the composition.
2240
        #We create a list of cyclically in/decreasing words appearing in
2241
        #the decomposition corresponding to the composition C,
2242
        #and then build the element.
2243
        listy=[]
2244
        while sum(D)>0:
2245
            l=['x' for i in xrange(self.k+1)]
2246
            ll=[]
2247
            #read off a row of C.
2248
            for j in xrange(self.k+1):
2249
                pos=(r + s0*t0*j)%(k+1)
2250
                residue=( r + s0*t0*(row + j) )%(k+1)
2251
                if D[pos]!=0:
2252
                    ll.append(residue)
2253
                    l[pos]=[residue]
2254
                    D[pos]-=1
2255
            if side[0]=='l': ll.reverse()
2256
            listy.append(ll)
2257
            row+=1
2258
        if side[0]=='r': listy.reverse()
2259
        x=self.one()
2260
        for ll in listy:
2261
            for i in ll:
2262
                x=x.apply_simple_reflection_right(i)
2263
        return x
2264

2265
    Element = AffinePermutationTypeA
2266

2267
class AffinePermutationGroupTypeC(AffinePermutationGroupGeneric):
2268
    #------------------------
2269
    #Type-specific methods.
2270
    #(Methods in all types, but with specific definition.)
2271
    #------------------------
2272

2273
    def one(self):
2274
        r"""
2275
        Returns the identity element.
2276

2277
        EXAMPLES::
2278

2279
            sage: ct=CartanType(['C',4,1])
2280
            sage: C=AffinePermutationGroup(ct)
2281
            sage: C.one()
2282
            Type C affine permutation with window [1, 2, 3, 4]
2283
            sage: C.one()*C.one()==C.one()
2284
            True
2285

2286
        TESTS::
2287

2288
            sage: C=AffinePermutationGroup(['C',4,1])
2289
            sage: C==loads(dumps(C))
2290
            True
2291
            sage: TestSuite(C).run()
2292
        """
2293
        return self([i for i in xrange(1,self.k+1)])
2294

2295
    Element = AffinePermutationTypeC
2296

2297

2298
class AffinePermutationGroupTypeB(AffinePermutationGroupTypeC):
2299
    #------------------------
2300
    #Type-specific methods.
2301
    #(Methods in all types, but with specific definition.)
2302
    #------------------------
2303
    Element = AffinePermutationTypeB
2304

2305
class AffinePermutationGroupTypeC(AffinePermutationGroupTypeC):
2306
    #------------------------
2307
    #Type-specific methods.
2308
    #(Methods in all types, but with specific definition.)
2309
    #------------------------
2310
    Element = AffinePermutationTypeC
2311

2312
class AffinePermutationGroupTypeD(AffinePermutationGroupTypeC):
2313
    #------------------------
2314
    #Type-specific methods.
2315
    #(Methods in all types, but with specific definition.)
2316
    #------------------------
2317
    Element = AffinePermutationTypeD
2318

2319
class AffinePermutationGroupTypeG(AffinePermutationGroupGeneric):
2320
    #------------------------
2321
    #Type-specific methods.
2322
    #(Methods in all types, but with specific definition.)
2323
    #------------------------
2324
    def one(self):
2325
        r"""
2326
        Returns the identity element.
2327

2328
        EXAMPLES::
2329

2330
            sage: AffinePermutationGroup(['G',2,1]).one()
2331
            Type G affine permutation with window [1, 2, 3, 4, 5, 6]
2332

2333
        TESTS::
2334

2335
            sage: G=AffinePermutationGroup(['G',2,1])
2336
            sage: G==loads(dumps(G))
2337
            True
2338
            sage: TestSuite(G).run()
2339
        """
2340
        return self([1,2,3,4,5,6])
2341
    Element = AffinePermutationTypeG
2342

2343

2344
Product

Resources

Company
