CoCalc -- non_decreasing_parking

GitHub Repository: sagemath/sagelib
Path: blob/master/sage/combinat/non_decreasing_parking_function.py
⁴⁰⁴⁵ views
1
r"""
2
Non-Decreasing Parking Functions
3

4
A *non-decreasing parking function* of size `n` is a non-decreasing
5
function `f` from `\{1,\dots,n\}` to itself such that for all `i`, one
6
has `f(i) \leq i`.
7

8
The number of non-decreasing parking functions of size `n` is the `n`-th
9
:func:`Catalan number<sage.combinat.combinat.catalan_number>`.
10

11
The set of non-decreasing parking functions of size `n` is in bijection with
12
the set of :mod:`Dyck words<sage.combinat.dyck_word>` of size `n`.
13

14
AUTHORS:
15

16
    - Florent Hivert (2009-04)
17
"""
18
#*****************************************************************************
19
#       Copyright (C) 2007 Florent Hivert <[email protected]>, 
20
#
21
#  Distributed under the terms of the GNU General Public License (GPL)
22
#
23
#    This code is distributed in the hope that it will be useful,
24
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
25
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
26
#    General Public License for more details.
27
#
28
#  The full text of the GPL is available at:
29
#
30
#                  http://www.gnu.org/licenses/
31
#*****************************************************************************
32
from sage.rings.integer import Integer
33
from combinat import (CombinatorialClass, CombinatorialObject,
34
                      InfiniteAbstractCombinatorialClass, catalan_number) 
35
from copy import copy
36

37

38
def NonDecreasingParkingFunctions(n=None):
39
    r"""
40
    Returns the combinatorial class of Non-Decreasing Parking Functions. 
41

42
    A *non-decreasing parking function* of size `n` is a non-decreasing
43
    function `f` from `\{1,\dots,n\}` to itself such that for all `i`,
44
    one has `f(i) \leq i`.
45

46
    EXAMPLES:
47

48
    Here are all the-non decreasing parking functions of size 5::
49
    
50
      sage: NonDecreasingParkingFunctions(3).list()
51
      [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
52
    
53
    If no size is specified, then NonDecreasingParkingFunctions
54
    returns the combinatorial class of all non-decreasing parking functions.
55

56
    ::
57
    
58
         sage: PF = NonDecreasingParkingFunctions(); PF
59
         Non-decreasing parking functions
60
         sage: [] in PF
61
         True
62
         sage: [1] in PF
63
         True
64
         sage: [2] in PF
65
         False
66
         sage: [1,1,3] in PF
67
         True
68
         sage: [1,1,4] in PF
69
         False
70

71
    If the size `n` is specified, then NonDecreasingParkingFunctions returns
72
    combinatorial class of all non-decreasing parking functions of size `n`.
73
    
74
    ::
75

76
         sage: PF = NonDecreasingParkingFunctions(0)
77
         sage: PF.list()
78
         [[]]
79
         sage: PF = NonDecreasingParkingFunctions(1)
80
         sage: PF.list()
81
         [[1]]
82
         sage: PF = NonDecreasingParkingFunctions(3)
83
         sage: PF.list()
84
         [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
85
                  
86
         sage: PF3 = NonDecreasingParkingFunctions(3); PF3
87
         Non-decreasing parking functions of size 3
88
         sage: [] in PF3
89
         False
90
         sage: [1] in PF3
91
         False
92
         sage: [1,1,3] in PF3
93
         True
94
         sage: [1,1,4] in PF3
95
         False
96

97
    TESTS::
98
    
99
         sage: PF = NonDecreasingParkingFunctions(5)
100
         sage: len(PF.list()) == PF.cardinality()
101
         True
102
         
103
    """
104
    if n is None:
105
        return NonDecreasingParkingFunctions_all()
106
    else:
107
        assert isinstance(n, (Integer, int)) and n >= 0, '%s is not a non-negative integer.' % n
108
        return NonDecreasingParkingFunctions_n(n)
109

110
def is_a(x, n=None):
111
    """
112
    Check whether a list is a non-decreasing parking function. If a size
113
    `n` is specified, checks if a list is a non-decreasing parking
114
    function of size `n`.
115

116
    TESTS::
117

118
        sage: from sage.combinat.non_decreasing_parking_function import is_a
119
        sage: is_a([1,1,2])
120
        True
121
        sage: is_a([1,1,4])
122
        False
123
        sage: is_a([1,1,3], 3)
124
        True
125
    """
126
    if not isinstance(x, list):
127
        return False
128
    prev = 1
129
    for i, elt in enumerate(x):
130
        if prev > elt or elt > i+1:
131
            return False
132
        prev = elt
133
    if n is not None and n != len(x):
134
        return False
135
    return True
136

137
        
138
class NonDecreasingParkingFunctions_all(InfiniteAbstractCombinatorialClass):
139
    def __init__(self):
140
        """
141
        TESTS::
142
        
143
            sage: DW = NonDecreasingParkingFunctions()
144
            sage: DW == loads(dumps(DW))
145
            True
146
        """
147
        pass
148

149
    def __repr__(self):
150
        """
151
        TESTS::
152
        
153
            sage: repr(NonDecreasingParkingFunctions())
154
            'Non-decreasing parking functions'
155
        """
156
        return "Non-decreasing parking functions"
157

158
    def __contains__(self, x):
159
        """
160
        TESTS::
161
        
162
            sage: [] in NonDecreasingParkingFunctions()
163
            True
164
            sage: [1] in NonDecreasingParkingFunctions()
165
            True
166
            sage: [2] in NonDecreasingParkingFunctions()
167
            False
168
            sage: [1,1,3] in NonDecreasingParkingFunctions()
169
            True
170
            sage: [1,1,4] in NonDecreasingParkingFunctions()
171
            False
172
        """
173
        if isinstance(x, NonDecreasingParkingFunction):
174
            return True
175
        return is_a(x)
176

177
    def _infinite_cclass_slice(self, n):
178
        """
179
        Needed by InfiniteAbstractCombinatorialClass to buid __iter__.
180

181
        TESTS::
182

183
            sage: (NonDecreasingParkingFunctions()._infinite_cclass_slice(4)
184
            ...    == NonDecreasingParkingFunctions(4))
185
            True
186
            sage: it = iter(NonDecreasingParkingFunctions()) # indirect doctest
187
            sage: [it.next() for i in range(8)]
188
            [[], [1], [1, 1], [1, 2], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2]]
189
         """
190
        return NonDecreasingParkingFunctions_n(n)
191

192
        
193
class NonDecreasingParkingFunctions_n(CombinatorialClass):
194
    """
195
    The combinatorial class of non-decreasing parking functions of
196
    size `n`.
197

198
    A *non-decreasing parking function* of size `n` is a non-decreasing
199
    function `f` from `\{1,\dots,n\}` to itself such that for all `i`,
200
    one has `f(i) \leq i`.
201

202
    The number of non-decreasing parking functions of size `n` is the
203
    `n`-th Catalan number.
204
    
205
    EXAMPLES::
206
    
207
        sage: PF = NonDecreasingParkingFunctions(3)
208
        sage: PF.list()
209
        [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
210
        sage: PF = NonDecreasingParkingFunctions(4)
211
        sage: PF.list()
212
        [[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 3, 4], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 2, 4], [1, 2, 3, 3], [1, 2, 3, 4]]
213
        sage: [ NonDecreasingParkingFunctions(i).cardinality() for i in range(10)]
214
        [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
215

216
    .. warning::
217

218
       The precise order in which the parking function are generated or
219
       listed is not fixed, and may change in the future.
220
      
221
    AUTHORS:
222

223
        - Florent Hivert
224
    """
225
    def __init__(self, n):
226
        """
227
        TESTS::
228
        
229
            sage: PF = NonDecreasingParkingFunctions(3)
230
            sage: PF == loads(dumps(PF))
231
            True
232
        """
233
        self.n = n
234

235
    def __repr__(self):
236
        """
237
        TESTS::
238
        
239
            sage: repr(NonDecreasingParkingFunctions(3))
240
            'Non-decreasing parking functions of size 3'
241
        """
242
        return "Non-decreasing parking functions of size %s"%(self.n)
243

244
    def __contains__(self, x):
245
        """
246
        TESTS::
247
        
248
            sage: PF3 = NonDecreasingParkingFunctions(3); PF3
249
            Non-decreasing parking functions of size 3
250
            sage: [] in PF3
251
            False
252
            sage: [1] in PF3
253
            False
254
            sage: [1,1,3] in PF3
255
            True
256
            sage: [1,1,1] in PF3
257
            True
258
            sage: [1,1,4] in PF3
259
            False
260
            sage: all([p in PF3 for p in PF3])
261
            True
262
        """
263
        if isinstance(x, NonDecreasingParkingFunction):
264
            return True
265
        return is_a(x, self.n)
266

267
    def cardinality(self):
268
        """
269
        Returns the number of non-decreasing parking functions of size
270
        `n`. This number is the `n`-th :func:`Catalan
271
        number<sage.combinat.combinat.catalan_number>`.
272

273
        EXAMPLES::
274
        
275
            sage: PF = NonDecreasingParkingFunctions(0)
276
            sage: PF.cardinality()
277
            1
278
            sage: PF = NonDecreasingParkingFunctions(1)
279
            sage: PF.cardinality()
280
            1
281
            sage: PF = NonDecreasingParkingFunctions(3)
282
            sage: PF.cardinality()
283
            5
284
            sage: PF = NonDecreasingParkingFunctions(5)
285
            sage: PF.cardinality()
286
            42
287
        """
288
        return catalan_number(self.n)
289
        
290
    def __iter__(self):
291
        """
292
        Returns an iterator for non-decreasing parking functions of size `n`.
293

294
        .. warning::
295

296
           The precise order in which the parking function are
297
           generated is not fixed, and may change in the future.
298
        
299
        EXAMPLES::
300
        
301
            sage: PF = NonDecreasingParkingFunctions(0)
302
            sage: [e for e in PF]      # indirect doctest
303
            [[]]
304
            sage: PF = NonDecreasingParkingFunctions(1)
305
            sage: [e for e in PF]      # indirect doctest
306
            [[1]]
307
            sage: PF = NonDecreasingParkingFunctions(3)
308
            sage: [e for e in PF]      # indirect doctest
309
            [[1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 2], [1, 2, 3]]
310
            sage: PF = NonDecreasingParkingFunctions(4)
311
            sage: [e for e in PF]      # indirect doctest            
312
            [[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 3], [1, 1, 1, 4], [1, 1, 2, 2], [1, 1, 2, 3], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 3, 4], [1, 2, 2, 2], [1, 2, 2, 3], [1, 2, 2, 4], [1, 2, 3, 3], [1, 2, 3, 4]]
313
            
314
        TESTS::
315
        
316
            sage: PF = NonDecreasingParkingFunctions(5)
317
            sage: [e for e in PF] == PF.list()
318
            True
319
            sage: PF = NonDecreasingParkingFunctions(6)
320
            sage: [e for e in PF] == PF.list()
321
            True
322

323
        Complexity: constant amortized time. 
324
        """
325
# FIXME : currently composition is extremenly slow.
326
# Activate the following code as soon as compositions use
327
# the integer_list_lex machinery      
328
#         for i in range(self.n, self.n*(self.n+1)/2+1):
329
#             for z in Compositions(i, length=self.n, outer=range(1, self.n+1),
330
#                                   min_slope=0).__iter__():
331
#                 yield NonDecreasingParkingFunction(z._list)
332
#         return
333
        def iterator_rec(n):
334
            """
335
            TESTS::
336

337
                sage: PF = NonDecreasingParkingFunctions(2)
338
                sage: [e for e in PF]      # indirect doctest
339
                [[1, 1], [1, 2]]
340
            """
341
            if n==0:
342
                yield [ ]; return
343
            if n==1:
344
                yield [1]; return
345
            for res1 in iterator_rec(n-1):
346
                for i in range(res1[-1], n+1):
347
                    res = copy(res1)
348
                    res.append(i)
349
                    yield res
350
            return
351
        for res in iterator_rec(self.n):
352
            yield NonDecreasingParkingFunction(res)
353
        return    
354
    
355
class NonDecreasingParkingFunction(CombinatorialObject):
356
    """
357
    A *non decreasing parking function* of size `n` is a non-decreasing
358
    function `f` from `\{1,\dots,n\}` to itself such that for all `i`,
359
    one has `f(i) \leq i`.
360

361
    EXAMPLES::
362
    
363
        sage: NonDecreasingParkingFunction([])
364
        []
365
        sage: NonDecreasingParkingFunction([1])
366
        [1]
367
        sage: NonDecreasingParkingFunction([2])
368
        Traceback (most recent call last):
369
        ...
370
        AssertionError: [2] is not a non-decreasing parking function.
371
        sage: NonDecreasingParkingFunction([1,2])
372
        [1, 2]
373
        sage: NonDecreasingParkingFunction([1,1,2])
374
        [1, 1, 2]
375
        sage: NonDecreasingParkingFunction([1,1,4])
376
        Traceback (most recent call last):
377
        ...
378
        AssertionError: [1, 1, 4] is not a non-decreasing parking function.
379
    """
380
    def __init__(self, lst):
381
        """
382
        TESTS::
383

384
            sage: NonDecreasingParkingFunction([1, 1, 2, 2, 5, 6])
385
            [1, 1, 2, 2, 5, 6]
386
        """
387
        assert is_a(lst), '%s is not a non-decreasing parking function.' % lst
388
        CombinatorialObject.__init__(self, lst)
389
        
390
    def __getitem__(self, n):
391
        """
392
        Returns the `n^{th}` item in the underlying list.
393

394
        .. note::
395

396
           Note that this is different than the image of ``n`` under
397
           function.  It is "off by one".
398

399
        EXAMPLES::
400

401
            sage: p = NonDecreasingParkingFunction([1, 1, 2, 2, 5, 6])
402
            sage: p[0]
403
            1
404
            sage: p[2]
405
            2
406
        """
407
        return self._list[n]
408

409
    def __call__(self, n):
410
        """
411
        Returns the image of ``n`` under the parking function.
412
        
413
        EXAMPLES::
414

415
            sage: p = NonDecreasingParkingFunction([1, 1, 2, 2, 5, 6])
416
            sage: p(3)
417
            2
418
            sage: p(6)
419
            6
420
        """        
421
        return self._list[n-1]
422

423
    def __mul__(self, lp):
424
        """
425
        The composition of non-decreasing parking functions.
426
        
427
        EXAMPLES::
428
        
429
            sage: p = NonDecreasingParkingFunction([1,1,3])
430
            sage: q = NonDecreasingParkingFunction([1,2,2])
431
            sage: p * q
432
            [1, 1, 1]
433
            sage: q * p
434
            [1, 1, 2]       
435
        """
436
        lp = lp._list
437
        sp = self._list
438
        lp = lp[:] + [i+1 for i in range(len(lp), len(lp))]
439
        sp = sp[:] + [i+1 for i in range(len(sp), len(lp))]
440
        return NonDecreasingParkingFunction([ sp[i-1] for i in lp ])
441

442
    def to_dyck_word(self):
443
        """
444
        Implements the bijection to :class:`Dyck
445
        words<sage.combinat.dyck_word.DyckWords>`, which is defined as follows.
446
        Take a non decreasing parking function, say [1,1,2,4,5,5], and draw
447
        its graph::
448
        
449
                                                 .
450
                                              .  |
451
                                           .__.__|
452
                                        .__|  .  .
453
                                     .  |  .  .  .
454
                                  .  .__|  .  .  .
455
                               .__.__|  .  .  .  .
456
                                 1  1  2  4  5  5
457

458
        The corresponding Dyck word [1,1,0,1,0,0,1,0,1,1,0,0] is then read off
459
        from the sequence of horizontal and vertical steps. The converse
460
        bijection is :meth:`.from_dyck_word`.
461
        
462
        EXAMPLES::
463
        
464
            sage: NonDecreasingParkingFunction([1,1,2,4,5,5]).to_dyck_word()
465
            [1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0]        
466
            sage: NonDecreasingParkingFunction([]).to_dyck_word()
467
            []
468
            sage: NonDecreasingParkingFunction([1,1,1]).to_dyck_word()
469
            [1, 1, 1, 0, 0, 0]
470
            sage: NonDecreasingParkingFunction([1,2,3]).to_dyck_word()
471
            [1, 0, 1, 0, 1, 0]        
472
            sage: NonDecreasingParkingFunction([1,1,3,3,4,6,6]).to_dyck_word()
473
            [1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]
474

475
        TESTS::
476
        
477
            sage: ndpf=NonDecreasingParkingFunctions(5);
478
            sage: list(ndpf) == [pf.to_dyck_word().to_non_decreasing_parking_function() for pf in ndpf]
479
            True
480
        """
481
        from sage.combinat.dyck_word import DyckWord_class
482
        return DyckWord_class.from_non_decreasing_parking_function(self)
483

484
    @classmethod
485
    def from_dyck_word(cls, dw):
486
        """
487
        Bijection from :class:`Dyck
488
        words<sage.combinat.dyck_word.DyckWords>`. It is the inverse of the
489
        bijection :meth:`.to_dyck_word`. You can find there the mathematical
490
        definition.
491
        
492
        EXAMPLES::
493
        
494
            sage: NonDecreasingParkingFunction.from_dyck_word([])
495
            []
496
            sage: NonDecreasingParkingFunction.from_dyck_word([1,0])
497
            [1]
498
            sage: NonDecreasingParkingFunction.from_dyck_word([1,1,0,0])
499
            [1, 1]
500
            sage: NonDecreasingParkingFunction.from_dyck_word([1,0,1,0])
501
            [1, 2]
502
            sage: NonDecreasingParkingFunction.from_dyck_word([1,0,1,1,0,1,0,0,1,0])
503
            [1, 2, 2, 3, 5]
504

505
        TESTS::
506
        
507
          sage: ndpf=NonDecreasingParkingFunctions(5);
508
          sage: list(ndpf) == [NonDecreasingParkingFunction.from_dyck_word(pf.to_dyck_word()) for pf in ndpf]
509
          True
510
        """
511
        res = []
512
        val = 1
513
        for i in dw:
514
            if i == 0:
515
                val+=1
516
            else:
517
                res.append(val)
518
        return cls(res)
519
    
520

521
Product

Resources

Company
