source: sage/combinat/ribbon.py @ 8006:90d75762f161

Revision 8006:90d75762f161, 14.7 KB checked in by Mike Hansen <mhansen@…>, 5 years ago (diff)

Restructuring symmetric functions and misc. combinatorics updates ( #1685 )
Line 
1r"""
2Ribbon Tableaux
3"""
4#*****************************************************************************
5#       Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
6#
7#  Distributed under the terms of the GNU General Public License (GPL)
8#
9#    This code is distributed in the hope that it will be useful,
10#    but WITHOUT ANY WARRANTY; without even the implied warranty of
11#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12#    General Public License for more details.
13#
14#  The full text of the GPL is available at:
15#
16#                  http://www.gnu.org/licenses/
17#*****************************************************************************
18
19import sage.combinat.misc as misc
20import sage.combinat.skew_tableau
21import sage.combinat.word as word
22import sage.combinat.permutation as permutation
23import sage.combinat.partition as partition
24import sage.combinat.skew_tableau
25import sage.combinat.skew_partition
26import sage.rings.integer
27from combinat import CombinatorialClass, CombinatorialObject
28
29SkewTableau   = sage.combinat.skew_tableau.SkewTableau
30from_expr     = sage.combinat.skew_tableau.from_expr
31SkewPartition = sage.combinat.skew_partition.SkewPartition
32Integer       = sage.rings.integer.Integer
33
34def Ribbon(r):
35    """
36    Returns a ribbon tableau object.
37
38    EXAMPLES:
39        sage: Ribbon([[2,3],[1,4,5]])
40        [[2, 3], [1, 4, 5]]
41    """
42    return Ribbon_class(r)
43       
44class Ribbon_class(CombinatorialObject):
45    def ribbon_shape(self):
46        """
47        Returns the ribbon shape.  The ribbon shape is given
48        just by the number of boxes in each row.
49
50        EXAMPLES:
51            sage: Ribbon([[2,3],[1,4,5]]).ribbon_shape()
52            [2, 3]
53        """
54
55        return [len(row) for row in self]
56
57    def height(self):
58        """
59        Returns the height of the ribbon.
60
61        EXAMPLES:
62            sage: Ribbon([[2,3],[1,4,5]]).height()
63            2
64        """
65        return len(self)
66
67    def spin(self):
68        """
69        """
70        return Integer(self.height()-1)/2
71
72    def width(self):
73        """
74        Returns the width of the ribbon.
75
76        EXAMPLES:
77            sage: Ribbon([[2,3],[1,4,5]]).width()
78            4
79        """
80        return 1+sum([len(r)-1 for r in self])
81
82    def size(self):
83        """
84        Returns the size ( number of boxes ) in the ribbon.
85
86        EXAMPLES:
87            sage: Ribbon([[2,3],[1,4,5]]).size()
88            5
89        """
90        return sum([len(r) for r in self])
91
92    def is_standard(self):
93        """
94        Returns True is the ribbon is standard and False otherwise.
95        ribbon are standard if they are filled with the numbers
96        1...size and they are increasing along both rows and columns.
97
98        EXAMPLES:
99            sage: Ribbon([[2,3],[1,4,5]]).is_standard()
100            True
101            sage: Ribbon([[2,2],[1,4,5]]).is_standard()
102            False
103            sage: Ribbon([[4,5],[1,2,3]]).is_standard()
104            False
105        """
106
107        return self.to_skew_tableau().is_standard()
108
109    def to_skew_tableau(self):
110        """
111        Returns the skew tableau corresponding to the ribbon
112        tableau.
113
114        EXAMPLES:
115            sage: Ribbon([[2,3],[1,4,5]]).to_skew_tableau()
116            [[None, None, 2, 3], [1, 4, 5]]
117        """
118        st = []
119        space_count = 0
120        for row in reversed(self):
121            st.append( [None]*space_count + row )
122            space_count += len(row) - 1
123        st.reverse()
124        return sage.combinat.skew_tableau.SkewTableau(st)
125
126    def to_permutation(self):
127        """
128        Returns the permutation corresponding to the ribbon
129        tableau.
130
131        EXAMPLES:
132            sage: r = Ribbon([[1], [2,3], [4, 5, 6]])
133            sage: r.to_permutation()
134            [1, 2, 3, 4, 5, 6]
135        """
136        return permutation.Permutation(self.to_word())
137   
138    def shape(self):
139        """
140        Returns the skew partition corresponding to the shape of the
141        ribbon.
142
143        EXAMPLES:
144            sage: Ribbon([[2,3],[1,4,5]]).shape()
145            [[4, 3], [2]]
146        """
147        return self.to_skew_tableau().shape()
148
149    def to_word_by_row(self):
150        """
151        Returns a word obtained from a row reading of the ribbon.
152
153        EXAMPLES:
154            sage: Ribbon([[1],[2,3]]).to_word_by_row()
155            [1, 2, 3]
156            sage: Ribbon([[2, 4], [3], [1]]).to_word_by_row()
157            [2, 4, 3, 1]
158        """
159        word = []
160        for row in self:
161            word += row
162
163        return word
164
165
166    def to_word_by_column(self):
167        """
168        Returns the word obtained from a column reading of the ribbon
169
170        EXAMPLES:
171            sage: Ribbon([[1],[2,3]]).to_word_by_column()
172            [2, 1, 3]
173            sage: Ribbon([[2, 4], [3], [1]]).to_word_by_column()
174            [2, 3, 1, 4]     
175
176        """
177        return self.to_skew_tableau().to_word_by_column()
178
179    def to_word(self):
180        """
181        An alias for Ribbon.to_word_by_row().
182
183        EXAMPLES:
184            sage: Ribbon([[1],[2,3]]).to_word_by_row()
185            [1, 2, 3]
186            sage: Ribbon([[2, 4], [3], [1]]).to_word_by_row()
187            [2, 4, 3, 1]
188        """
189        return self.to_word_by_row()
190
191    def evaluation(self):
192        """
193        Returns the evaluation of the word from ribbon.
194
195        EXAMPLES:
196            sage: Ribbon([[1,2],[3,4]]).evaluation()
197            [1, 1, 1, 1]
198        """
199
200        return word.evaluation(self.to_word())
201
202   
203
204def from_shape_and_word(shape, word):
205    """
206    Returns the ribbon corresponding to the given
207    ribbon shape and word.
208
209    EXAMPLES:
210        sage: ribbon.from_shape_and_word([2,3],[1,2,3,4,5])
211        [[1, 2], [3, 4, 5]]
212    """
213    pos = 0
214    r = []
215    for l in shape:
216        r.append(word[pos:pos+l])
217        pos += l
218    return Ribbon(r)
219
220def StandardRibbonTableaux(shape):
221    """
222    Returns the combinatorial class of standard ribbon
223    tableaux of shape shape.
224
225    EXAMPLES:
226        sage: StandardRibbonTableaux([2,2])
227        Standard ribbon tableaux of shape [2, 2]
228        sage: StandardRibbonTableaux([2,2]).first()
229        [[1, 3], [2, 4]]
230        sage: StandardRibbonTableaux([2,2]).last()
231        [[3, 4], [1, 2]]
232        sage: StandardRibbonTableaux([2,2]).count()
233        5
234        sage: StandardRibbonTableaux([2,2]).list()
235        [[[1, 3], [2, 4]],
236         [[1, 4], [2, 3]],
237         [[2, 3], [1, 4]],
238         [[2, 4], [1, 3]],
239         [[3, 4], [1, 2]]]
240
241        sage: StandardRibbonTableaux([2,2]).list()
242        [[[1, 3], [2, 4]],
243         [[1, 4], [2, 3]],
244         [[2, 3], [1, 4]],
245         [[2, 4], [1, 3]],
246         [[3, 4], [1, 2]]]   
247        sage: StandardRibbonTableaux([3,2,2]).count()
248        155
249
250    """
251    return StandardRibbonTableaux_shape(shape)
252
253class StandardRibbonTableaux_shape(CombinatorialClass):
254    def __init__(self, shape):
255        """
256        TESTS:
257            sage: S = StandardRibbonTableaux([2,2])
258            sage: S == loads(dumps(S))
259            True
260        """
261        self.shape = shape
262
263    def __repr__(self):
264        """
265        TESTS:
266            sage: repr(StandardRibbonTableaux([2,2]))
267            'Standard ribbon tableaux of shape [2, 2]'
268        """
269        return "Standard ribbon tableaux of shape %s"%self.shape
270
271
272    def first(self):
273        """
274        Returns the first standard ribbon of
275        ribbon shape shape.
276
277        EXAMPLES:
278            sage: StandardRibbonTableaux([2,2]).first()
279            [[1, 3], [2, 4]]
280
281        """
282        return from_permutation(permutation.descents_composition_first(self.shape))
283
284    def last(self):
285        """
286        Returns the first standard ribbon of
287        ribbon shape shape.
288
289        EXAMPLES:
290            sage: StandardRibbonTableaux([2,2]).last()
291            [[3, 4], [1, 2]]
292        """
293        return from_permutation(permutation.descents_composition_last(self.shape))
294
295
296    def iterator(self):
297        """
298        An iterator for the standard ribbon of ribbon
299        shape shape.
300
301        EXAMPLES:
302            sage: [t for t in StandardRibbonTableaux([2,2])]
303            [[[1, 3], [2, 4]],
304             [[1, 4], [2, 3]],
305             [[2, 3], [1, 4]],
306             [[2, 4], [1, 3]],
307             [[3, 4], [1, 2]]]   
308        """
309
310        for p in permutation.descents_composition_list(self.shape):
311            yield from_permutation(p)
312
313def from_permutation(p):
314    """
315    Returns a standard ribbon of size len(p) from a Permutation p.
316    The lengths of each row are given by the distance between the descents
317    of the permutation p.
318   
319    EXAMPLES:
320        sage: [ribbon.from_permutation(p) for p in Permutations(3)]
321        [[[1, 2, 3]],
322         [[1, 3], [2]],
323         [[2], [1, 3]],
324         [[2, 3], [1]],
325         [[3], [1, 2]],
326         [[3], [2], [1]]]
327
328    """
329    if p == []:
330        return Ribbon([])
331   
332    comp = p.descents()
333
334    if comp == []:
335        return Ribbon([p[:]])
336
337   
338    #[p[j]$j=compo[i]+1..compo[i+1]] $i=1..nops(compo)-1, [p[j]$j=compo[nops(compo)]+1..nops(p)]
339    r = [] 
340    r.append([p[j] for j in range(comp[0]+1)])
341    for i in range(len(comp)-1):
342        r.append([ p[j] for j in range(comp[i]+1,comp[i+1]+1) ])
343    r.append( [ p[j] for j in range(comp[-1]+1, len(p))] )
344
345    return Ribbon(r)
346
347
348
349#####################
350# Under Development #
351#####################
352class RibbonTableaux_shapeweightlength(CombinatorialClass):
353    def __init__(self, shape, weight, length):
354        self.shape = shape
355        self.weight = weight
356        self.length = length
357
358    def list(self):
359        pass
360
361
362
363def list(skp, weight, length):
364    if skp in partition.Partitions():
365        skp = partition.Partition(skp)
366        skp = SkewPartition([skp, skp.rcore(length)])
367    else:
368        skp = SkewPartition(skp)
369           
370    #skp_expr = skp.to_expr()
371   
372    if skp.size() != length*sum(weight):
373        raise ValueError
374
375    return map(lambda x: from_expr( [skp[1], x[1]]), graph_implementation_rec(skp, weight, length, list_rec))
376
377
378
379
380
381
382
383
384
385def insertion_tableau(skp, perm, evaluation, tableau, length):
386    """
387
388    INPUT:
389        skp -- skew partitions
390        perm, evaluation -- non-negative integers
391        tableau -- skew tableau
392        length -- integer
393       
394    """
395    print "insertion_tableau(%s, %s, %s, %s, %s)"%(skp, perm, evaluation, tableau, length)
396    psave = skp[1]
397    partc = skp[1] + [0]*(len(skp[0])-len(skp[1]))
398
399    tableau = tableau.to_expr()[1]
400    for k in range(len(tableau)):
401        tableau[-(k+1)] += [0]* ( skp[0][k] - partc[k] - len(tableau[-(k+1)]))
402
403    ## We construct a tableau from the southwest corner to the northeast one
404    #[ op( revert([[0$(partition[1][k] - partc[k]) ] $k = nops(tableau)+1..nops(partition[1])])) , op(tableau) ];
405    tableau =  [[0]*(skp[0][k] - partc[k]) for k in reversed(range(len(tableau), len(skp[0])+1))] + tableau
406
407    tableau = SkewTableau(expr=[skp[1], tableau]).conjugate()
408    tableau = tableau.to_expr()[1]
409
410    skp = skp.conjugate().to_list()
411    skp[1].append( [0]*(len(skp[0])-len(skp[1])) )
412
413    if len(perm) > len(skp[0]):
414        return None
415
416    for k in range(len(perm)):
417        if perm[ -(k+1) ] !=0:
418            #tableau ... = evaluation
419            tableau[len(tableau)-len(perm)+k-1][ spk[0][len(perm)-k] - skp[1][ len(perm)-k ] ] = evaluation
420            pass
421
422    return SkewTableau(expr=[psave.conjugate(),tableau]).conjugate()
423   
424   
425       
426
427def list_rec(nexts, current, part, weight, length):
428    """
429
430    INPUT:
431        nexts, current, part -- skew partitions
432        weight -- non-negative integer list
433        length -- integer
434    """
435    print "list_rec(%s, %s, %s, %s, %s)"%(nexts, current, part, weight, length)
436    if current == [] and nexts == [] and weight == []:
437        return [part[1],[]]
438
439    ## Test if the current nodes is not an empty node
440    if current == []:
441        return []
442
443   
444    ## Test if the current nodes drive us to new solutions
445    if next != []:
446        res = []
447        for i in range(len(current)):
448            for j in range(len(nexts[i])):
449                res.append( interstion_tableau(part, current[i][1], len(weight), nexts[i][j], length) )
450        return res
451    else:
452        ## The current nodes are at the bottom of the tree
453        res = []
454        for i in range(len(current)):
455            res.append( insertion_tableau(part, current[i][1], len(weight), [[],[]], length) )
456        return res
457
458
459##     //////////////////////////////////////////////////////////////////////////////////////////
460##     // Generic function for driving into the graph of partitions coding all ribbons
461##     // tableaux of a given shape and weight
462##     //////////////////////////////////////////////////////////////////////////////////////////
463                                                 
464##     //This function construct the graph of the set of k-ribbon tableaux
465##     //of a given skew shape and a given weight.
466##     //The first argument is alaways a skew partition.
467##     //In the case where the inner partition is empty there is no branch without solutions
468##     //In the other cases there is in average a lot of branches without solutions
469##     /////////////////////////////////////////////////////////////////////////////////////////
470
471
472
473def graph_implementation_rec(skp, weight, length, function):
474    print "graph_implementation_rec(%s, %s, %s, %s)"%(skp, weight, length, function)
475
476    if sum(weight) == 0:
477        weight = []
478
479    partp = partition.Partition(skp[1]).conjugate()
480
481    ## Some tests in order to know if the shape and the weight are compatible.
482    if weight != [] and weight[-1] <= len(partp):
483        perms = permutation.Permutations([0]*(len(partp)-weight[-1]) + [length]*(weight[-1])).list()
484    else:
485        return function([], [], part, weight, length)
486
487    selection = []
488
489    for j in range(len(perms)):
490        retire = [(partp[i]+ len(partp) - (i+1) - perms[j][i]) for i in range(len(partp))]
491        retire.sort(reverse=True)
492        retire = [ retire[i] - len(partp) + (i+1) for i in range(len(retire))]
493
494        if retire[-1] >= 0 and retire == [i for i in reversed(sorted(retire))]:
495            retire = partition.Partition(filter(lambda x: x != 0, retire)).conjugate()
496           
497
498            # Cutting branches if the retired partition has a line strictly included into the inner one
499            append = True
500            padded_retire = retire + [0]*(len(skp[1])-len(retire))
501            for k in range(len(skp[1])):
502                if padded_retire[k] - skp[1][k] < 0:
503                    append = False
504                    break
505            if append:
506                selection.append([retire, perms[j]])
507
508
509    #selection contains the list of current nodes
510
511
512    if len(weight) == 1:
513        return function([], selection, part, weight, length)
514    else:
515        #The recursive calls permit us to construct the list of the sons
516        #of all current nodes in selection
517        a = [graph_implementation_rec([p[0], part[1]], [weight[i]]*(len(weight)-1), length, function) for p in selection]
518        return function(a, selection, skp, weight, length)
519
520   
521
522
523
524
525
526
527
528
529
530
531
Note: See TracBrowser for help on using the repository browser.