source: sage/combinat/skew_tableau.py @ 6503:0314612307d2

Revision 6503:0314612307d2, 19.4 KB checked in by was@…, 6 years ago (diff)

Fix for FC7 issue.
Line 
1#*****************************************************************************
2#       Copyright (C) 2007 Mike Hansen <mhansen@gmail.com>,
3#
4#  Distributed under the terms of the GNU General Public License (GPL)
5#
6#    This code is distributed in the hope that it will be useful,
7#    but WITHOUT ANY WARRANTY; without even the implied warranty of
8#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
9#    General Public License for more details.
10#
11#  The full text of the GPL is available at:
12#
13#                  http://www.gnu.org/licenses/
14#*****************************************************************************
15
16from sage.rings.arith import factorial
17from sage.rings.integer import Integer
18from sage.combinat.partition import Partition
19import sage.combinat.tableau
20from sage.combinat.skew_partition import SkewPartition
21import partition
22import misc
23import word
24from sage.misc.all import prod
25import exceptions
26import random
27import copy
28from combinat import CombinatorialObject, CombinatorialClass
29from sage.graphs.graph import DiGraph
30
31def SkewTableau(st):
32    """
33    Returns the skew tableau object corresponding to st.
34
35    EXAMPLES:
36        sage: st = SkewTableau([[None, 1],[2,3]]); st
37        [[None, 1], [2, 3]]
38        sage: st.inner_shape()
39        [1]
40        sage: st.outer_shape()
41        [2, 2]
42    """
43    for row in st:
44        if not isinstance(row, list):
45            raise TypeError, "each element of the skew tableau must be a list"
46        if row == []:
47            raise TypeError, "a skew tableau cannot have an empty list for a row"
48       
49    return SkewTableau_class(st)
50
51class SkewTableau_class(CombinatorialObject):
52    def __init__(self, t):
53        """
54        TESTS:
55            sage: st = SkewTableau([[None, 1],[2,3]])
56            sage: st == loads(dumps(st))
57            True
58        """
59        CombinatorialObject.__init__(self,t)
60
61    def pp(self):
62        """
63        Returns a pretty print string of the tableau.
64        EXAMPLES:
65            sage: t = SkewTableau([[None,2,3],[None,4],[5]])
66            sage: print t.pp()
67              .  2  3
68              .  4
69              5
70        """
71
72        def none_str(x):
73            if x == None:
74                return "  ."
75            else:
76                return "%3s"%str(x)
77           
78        new_rows = [ "".join(map(none_str , row)) for row in self]
79        return '\n'.join(new_rows)
80
81    def outer_shape(self):
82        """
83        Returns the outer shape of the tableau.
84
85        EXAMPLES:
86            sage: SkewTableau([[None,1,2],[None,3],[4]]).outer_shape()
87            [3, 2, 1]
88        """
89       
90        return Partition([len(row) for row in self])
91
92
93    def inner_shape(self):
94        """
95        Returns the inner shape of the tableau.
96
97        EXAMPLES:
98            sage: SkewTableau([[None,1,2],[None,3],[4]]).inner_shape()
99            [1, 1]
100        """
101       
102        return Partition(filter(lambda x: x != 0, [len(filter(lambda x: x==None, row)) for row in self]))
103   
104    def shape(self):
105        r"""
106        Returns the shape of a tableau t.
107
108        EXAMPLES:
109            sage: SkewTableau([[None,1,2],[None,3],[4]]).shape()
110            [[3, 2, 1], [1, 1]]
111        """
112
113        return SkewPartition([self.outer_shape(), self.inner_shape()])
114
115   
116    def outer_size(self):
117        """
118        Returns the size of the outer shape of the skew tableau.
119
120        EXAMPLES:
121            sage: SkewTableau([[None, 2, 4], [None, 3], [1]]).outer_size()
122            6
123            sage: SkewTableau([[None, 2], [1, 3]]).outer_size()
124            4
125
126        """
127        return self.outer_shape().size()
128
129
130    def inner_size(self):
131        """
132        Returns the size of the inner shape of the skew tableau.
133
134        EXAMPLES:
135            sage: SkewTableau([[None, 2, 4], [None, 3], [1]]).inner_size()
136            2
137            sage: SkewTableau([[None, 2], [1, 3]]).inner_size()
138            1
139   
140        """
141        return self.inner_shape().size()
142
143    def size(self):
144        """
145        Returns the number of boxes in the skew tableau.
146
147        EXAMPLES:
148            sage: SkewTableau([[None, 2, 4], [None, 3], [1]]).size()
149            4
150            sage: SkewTableau([[None, 2], [1, 3]]).size()
151            3
152
153        """
154        return sum([len(filter(lambda x: x != None,row)) for row in self])
155
156
157
158    def conjugate(self):
159        """
160        Returns the conjugate of the skew tableau.
161
162        EXAMPLES:
163            sage: SkewTableau([[None,1],[2,3]]).conjugate()
164            [[None, 2], [1, 3]]
165        """
166        conj_shape = self.outer_shape().conjugate()
167
168        conj = [[None]*row_length for row_length in conj_shape]
169
170        for i in range(len(conj)):
171            for j in range(len(conj[i])):
172                conj[i][j] = self[j][i]
173
174
175        return SkewTableau(conj)
176
177    def to_word_by_row(self):
178        """
179        Returns a word obtained from a row reading of the skew tableau.
180
181        EXAMPLES:
182            sage: SkewTableau([[None,1],[2,3]]).to_word_by_row()
183            [1, 2, 3]
184            sage: SkewTableau([[None, 2, 4], [None, 3], [1]]).to_word_by_row()
185            [2, 4, 3, 1]
186        """
187        word = []
188        for row in self:
189            word += filter(lambda x: x!= None, row)
190
191        return word
192
193
194    def to_word_by_column(self):
195        """
196        Returns the word obtained from a column reading of the skew tableau
197
198        EXAMPLES:
199            sage: SkewTableau([[None,1],[2,3]]).to_word_by_column()
200            [2, 1, 3]
201            sage: SkewTableau([[None, 2, 4], [None, 3], [1]]).to_word_by_column()
202            [1, 2, 3, 4]     
203
204        """
205        word = []
206        conj = self.conjugate()
207        for row in conj:
208            word += filter(lambda x: x!= None, row)
209
210        return word
211
212    def to_word(self):
213        """
214        An alias for SkewTableau.to_word_by_row().
215        """
216        return self.to_word_by_row()
217
218    def evaluation(self):
219        """
220        Returns the evaluation of the word from skew tableau.
221
222        EXAMPLES:
223            sage: SkewTableau([[1,2],[3,4]]).evaluation()
224            [1, 1, 1, 1]
225        """
226
227        return word.evaluation(self.to_word())
228
229    def is_standard(self):
230        """
231        Returns True if t is a standard skew tableau and False otherwise.
232
233        EXAMPLES:
234            sage: SkewTableau([[None, 2], [1, 3]]).is_standard()
235            True
236            sage: SkewTableau([[None, 2], [2, 4]]).is_standard()
237            False
238            sage: SkewTableau([[None, 3], [2, 4]]).is_standard()
239            False
240            sage: SkewTableau([[None, 2], [2, 4]]).is_standard()
241            False
242        """
243        t = self
244        #Check to make sure that it is filled with 1...size
245        w = self.to_word()
246        w.sort()
247        if w != range(1, self.size()+1):
248            return False
249
250
251
252        #Check to make sure it is increasing along the rows
253        for row in t:
254            for i in range(1, len(row)):
255                if row[i-1] is not None and row[i] <= row[i-1]:
256                    return False
257
258
259        #Check to make sure it is increasing along the columns
260        conj = t.conjugate()
261        for row in conj:
262            for i in range(1, len(row)):
263                if row[i-1] is not None and row[i] <= row[i-1]:
264                    return False   
265
266        return True
267
268    def to_tableau(self):
269        """
270        Returns a tableau with the same filling.  This only works if the
271        inner shape of the skew tableau has size zero.
272
273        EXAMPLES:
274            sage: SkewTableau([[1,2],[3,4]]).to_tableau()
275            [[1, 2], [3, 4]]
276
277        """
278
279        if self.inner_size() != 0:
280            raise ValueError, "the inner size of the skew tableau must be 0"
281        else:
282            return  sage.combinat.tableau.Tableau(self[:])
283
284    def restrict(self, n):
285        """
286        Returns the restriction of the standard skew tableau to all the numbers less
287        than or equal to n.
288
289        EXAMPLES:
290            sage: SkewTableau([[None,1],[2],[3]]).restrict(2)
291            [[None, 1], [2]]
292            sage: SkewTableau([[None,1],[2],[3]]).restrict(1)
293            [[None, 1]]           
294        """
295        t = self[:]
296        if not self.is_standard():
297            raise ValueError, "the skew tableau must be standard to perform the restriction"
298       
299        return SkewTableau( filter(lambda z: z != [], map(lambda x: filter(lambda y: y is None or y <= n, x), t)) )
300   
301    def to_chain(self):
302        """
303        Returns the chain of skew partitions corresponding to the standard
304        skew tableau.
305
306        EXAMPLES:
307            sage: SkewTableau([[None,1],[2],[3]]).to_chain()
308            [[[1], [1]], [[2], [1]], [[2, 1], [1]], [[2, 1, 1], [1]]]
309        """
310        if not self.is_standard():
311            raise ValueError, "the skew tableau must be standard to convert to a chain"
312
313        return map(lambda x: self.restrict(x).shape(), range(self.size()+1))
314
315    def slide(self, corner=None):
316        """
317
318        Fulton, William. 'Young Tableaux'. p12-13
319       
320        EXAMPLES:
321            sage: st = SkewTableau([[None, None, None, None,2],[None, None, None, None,6], [None, 2, 4, 4], [2, 3, 6], [5,5]])
322            sage: st.slide([2,0])
323            [[None, None, None, None, 2], [None, None, None, None, 6], [2, 2, 4, 4], [3, 5, 6], [5]]
324
325        """
326        new_st = copy.copy(self[:])
327        inner_corners = self.inner_shape().corners()
328        outer_corners = self.outer_shape().corners()
329        if corner != None:
330            if corner not in inner_corners:
331                raise ValueError, "corner must be an inner corner"
332        else:
333            if len(inner_corners) == 0:
334                return self
335            else:
336                corner = inner_corners[0]
337
338        spot = corner[:]
339        while spot not in outer_corners:
340            #print spot
341            #Check to see if there is nothing to the right
342            if spot[1] == len(new_st[spot[0]]) - 1:
343                #print "nr"
344                #Swap the hole with the box below
345                new_st[spot[0]][spot[1]] = new_st[spot[0]+1][spot[1]]
346                new_st[spot[0]+1][spot[1]] = None
347                spot[0] += 1
348                continue
349               
350            #Check to see if there is nothing below
351            if (spot[0] == len(new_st) - 1) or (len(new_st[spot[0]+1]) <= spot[1]):
352                #print "nb"
353                #Swap the hole with the box to the right
354                new_st[spot[0]][spot[1]] = new_st[spot[0]][spot[1]+1]
355                new_st[spot[0]][spot[1]+1] = None
356                spot[1] += 1
357                continue
358
359            #If we get to this stage, we need to compare
360            below = new_st[spot[0]+1][spot[1]]
361            right = new_st[spot[0]][spot[1]+1]
362            if below <= right:
363                #Swap with the box below
364                #print "b"
365                new_st[spot[0]][spot[1]] = new_st[spot[0]+1][spot[1]]
366                new_st[spot[0]+1][spot[1]] = None
367                spot[0] += 1
368                continue
369            else:
370                #Swap with the box to the right
371                #print "r"
372                new_st[spot[0]][spot[1]] = new_st[spot[0]][spot[1]+1]
373                new_st[spot[0]][spot[1]+1] = None
374                spot[1] += 1
375                continue
376           
377        #Clean up to remove the "None" at an outside corner
378        #Remove the last row if there is nothing left in it
379        new_st[spot[0]].pop()
380        if len(new_st[spot[0]]) == 0:
381            new_st.pop()
382       
383        return SkewTableau(new_st)
384               
385
386    def rectify(self):
387        """
388        Returns a Tableau formed by applying the jeu de taquin process to
389        self.
390
391        Fulton, William. 'Young Tableaux'. p15
392
393        EXAMPLES:
394        """
395        rect = copy.deepcopy(self)
396        inner_corners = rect.inner_shape().corners()
397
398        while len(inner_corners) > 0:
399            rect = rect.slide()
400            inner_corners = rect.inner_shape().corners()
401
402        return rect.to_tableau()
403
404
405
406       
407class SkewTableauWithContent(SkewTableau_class):
408    def _setmin(self, y, x, initial=None):
409        #Compute t which is the "minimum" skew tableau with
410        #the given content
411        #t = [ [0]*self.outer[i] for i in range(len(self.outer)) ]
412        if initial == None:
413            t = self.list
414        else:
415            t = initial
416
417        #this algorithm comes from st_setmin
418        #print "Call: (%d, %d)"%(y,x)
419        while ( y < self.rows ):
420            while x >= self.inner[y]:
421                if y == 0 or x < self.inner[y-1]:
422                    e = 0
423                else:
424                    e = t[y-1][x] + 1
425
426                t[y][x] = e
427                try:
428                    self.conts[e] += 1
429                except:
430                    raise IndexError, "(%d,%d): %d, %s"%(y,x, e, str(self.conts))
431
432                x -= 1
433            y += 1
434
435            if y < self.rows:
436                x = self.outer[y] - 1
437        return t
438
439    def __init__(self, outer, inner, conts=None, maxrows=0):
440        self.rows = len(outer)
441
442        if conts != None:
443            self.clen = len(conts)
444        else:
445            self.clen = 0
446        self.clen += self.rows
447     
448        self.conts = [0]*self.clen
449        if conts != None:
450            for i in range(len(conts)):
451                self.conts[i] = conts[i]
452
453        self.outer = outer[:]
454        self.inner = inner[:] + [0]*(len(outer)-len(inner))
455       
456        if len(self.outer) == 0:
457            self.cols = 0
458        else:
459            self.cols = self.outer[0]
460
461
462        initial = [ [0]*self.outer[i] for i in range(len(self.outer)) ]
463        t = self._setmin(0, self.outer[0]-1, initial=initial)
464        SkewTableau.__init__(self,t)
465
466        self.outer_conj = None
467       
468        self.maxrows = maxrows
469        if (maxrows >= self.clen):
470            self.maxrows = 0
471
472        if self.maxrows == 0:
473            return
474
475        if self.conts[self.maxrows] != 0:
476            raise ValueError, " self.conts[self.maxrows] != 0 "
477
478        self.outer_conj = Partition(self.outer).conjugate()
479
480    def next(self):
481        """
482        Returns the next semistandard skew tableau
483        """
484        #new_st = copy.copy(self)
485        #IMPLEMENTATION SPECIFIC
486        l = self.list
487
488        for y in reversed(range(self.rows)):
489            xlim = self.outer[y]
490
491            for x in range(self.inner[y], xlim):
492                if self.maxrows == 0:
493                    elim = len(self.conts) -1
494                else:
495                    elim = self.maxrows + y - self.outer_conj[x]
496
497                if x != xlim - 1:
498                    next_cell = l[y][x+1]
499                    if next_cell < elim:
500                        elim = next_cell
501
502                e = l[y][x]
503                self.conts[e] -= 1
504
505                e += 1
506                while ( e <= elim and
507                        self.conts[e] == self.conts[e-1] ):
508                    e += 1
509
510                if e <= elim:
511                    l[y][x] = e
512                    self.conts[e] += 1
513
514                    #IMPLEMENTATION SPECIFIC
515                    #new_st._setmin(y, x-1)
516                    self._setmin(y,x-1)
517                    return self
518                    #return new_st
519
520        return False
521                   
522                   
523def st_iterator(outer, inner, conts=None, maxrows=0):
524    st = SkewTableauWithContent(outer,inner,conts=conts,maxrows=maxrows)
525    yield st
526
527    next = st.next()
528    while next != False:
529        yield next
530        next = next.next()
531       
532
533
534def _label_skew(list, sk):
535    """
536    Returns a filled in a standard skew tableaux given an ordered list of the
537    coordinates to filled in.
538
539    EXAMPLES:
540        sage: l = [ '0,0', '1,1', '1,0', '0,1' ]
541        sage: empty = [[None,None],[None,None]]
542        sage: skew_tableau._label_skew(l, empty)
543        [[1, 4], [3, 2]]
544    """
545    i = 1
546    skew = copy.deepcopy(sk)
547    for coordstring in list:
548            coords = coordstring.split(",")
549            row = int(coords[0])
550            column = int(coords[1])
551            skew[row][column] = i
552            i += 1
553    return skew
554
555def StandardSkewTableaux(skp):
556    """
557    Returns the combinatorial class of standard skew tableaux of
558    shape skp (where skp is a skew partition).
559
560    EXAMPLES:
561        sage: StandardSkewTableaux([[3, 2, 1], [1, 1]]).list()
562        [[[None, 1, 2], [None, 3], [4]],
563         [[None, 1, 2], [None, 4], [3]],
564         [[None, 1, 3], [None, 2], [4]],
565         [[None, 1, 4], [None, 2], [3]],
566         [[None, 1, 3], [None, 4], [2]],
567         [[None, 1, 4], [None, 3], [2]],
568         [[None, 2, 3], [None, 4], [1]],
569         [[None, 2, 4], [None, 3], [1]]]
570    """
571    return StandardSkewTableaux_skewpartition(SkewPartition(skp))
572
573class StandardSkewTableaux_skewpartition(CombinatorialClass):
574    object_class = SkewTableau_class
575    def __init__(self, skp):
576        """
577        TESTS:
578            sage: S = StandardSkewTableaux([[3, 2, 1], [1, 1]])
579            sage: S == loads(dumps(S))
580            True
581        """
582        self.skp = skp
583
584    def list(self):
585        """
586        Returns a list for all the standard skew tableaux with shape
587        of the skew partition skp. The standard skew tableaux are
588        ordered lexicographically by the word obtained from their
589        row reading.
590
591        EXAMPLES:
592            sage: StandardSkewTableaux([[3, 2, 1], [1, 1]]).list()
593            [[[None, 1, 2], [None, 3], [4]],
594             [[None, 1, 2], [None, 4], [3]],
595             [[None, 1, 3], [None, 2], [4]],
596             [[None, 1, 4], [None, 2], [3]],
597             [[None, 1, 3], [None, 4], [2]],
598             [[None, 1, 4], [None, 3], [2]],
599             [[None, 2, 3], [None, 4], [1]],
600             [[None, 2, 4], [None, 3], [1]]]
601
602        """
603        return [st for st in self]
604
605    def count(self):
606        """
607        Returns the number of standard skew tableaux with shape of the
608        skew partition skp.
609
610        EXAMPLES:
611            sage: StandardSkewTableaux([[3, 2, 1], [1, 1]]).count()
612            8
613        """
614
615        return sum([1 for st in self])
616
617    def iterator(self):
618        """
619        An iterator for all the standard skew tableau with shape of the
620        skew partition skp. The standard skew tableaux are
621        ordered lexicographically by the word obtained from their
622        row reading.
623
624        EXAMPLES:
625            sage: [st for st in StandardSkewTableaux([[3, 2, 1], [1, 1]])]
626            [[[None, 1, 2], [None, 3], [4]],
627             [[None, 1, 2], [None, 4], [3]],
628             [[None, 1, 3], [None, 2], [4]],
629             [[None, 1, 4], [None, 2], [3]],
630             [[None, 1, 3], [None, 4], [2]],
631             [[None, 1, 4], [None, 3], [2]],
632             [[None, 2, 3], [None, 4], [1]],
633             [[None, 2, 4], [None, 3], [1]]]
634        """
635        skp = self.skp
636       
637        dag = skp.to_dag()
638        le_list = list(dag.topological_sort_generator())
639
640        empty = [[None]*row_length for row_length in skp.outer()]
641
642        for le in le_list:
643            yield SkewTableau(_label_skew(le, empty))
644
645   
646
647def from_shape_and_word(shape, word):
648    """
649    Returns the skew tableau correspnding to the skew partition
650    shape and the word obtained from the row reading.
651
652    EXAMPLES:
653        sage: t = SkewTableau([[None, 2, 4], [None, 3], [1]])
654        sage: shape = t.shape()
655        sage: word  = t.to_word()
656        sage: skew_tableau.from_shape_and_word(shape, word)
657        [[None, 2, 4], [None, 3], [1]]
658
659    """
660    st = [ [None]*row_length for row_length in shape[0] ]
661    w_count = 0
662    for i in range(len(shape[0])):
663        for j in range(shape[0][i]):
664            if i >= len(shape[1]) or j >= shape[1][i]:
665                st[i][j] = word[w_count]
666                w_count += 1
667    return SkewTableau(st)
668   
Note: See TracBrowser for help on using the repository browser.