Opened 3 years ago
Closed 3 years ago
#21615 closed enhancement (fixed)
Implementation of LittlewoodRichardson tableaux
Reported by:  aschilling  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  combinatorics  Keywords:  
Cc:  MariaMonks, j.levinson, tscrim  Merged in:  
Authors:  Maria Gillespie, Anne Schilling, Jake Levinson  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  40414a3 (Commits)  Commit:  40414a3de57343af2078efa2ebffa09eb3c003de 
Dependencies:  Stopgaps: 
Description (last modified by )
This patch implements a new class for LittlewoodRichardson tableaux.
Change History (23)
comment:1 Changed 3 years ago by
 Cc tscrim added
comment:2 Changed 3 years ago by
 Branch set to u/aschilling/LRtableaux21615
 Commit set to ec8d39c2a09ba88a0b411ceb5717cc408f18fa5d
 Description modified (diff)
 Status changed from new to needs_review
comment:3 followup: ↓ 5 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to needs_work
Hey Maria and Anne,
I've taken a look over this and there are a few polishing things that need to be done.
 You should have documentation for each of the classes. This is important both for locality of documentation and so
LittlewoodRichardsonTableau?
does not show the__init__
documentation. You can just put theINPUT:
block at the class level doc as well.  For error messages, they are typically not considered complete sentences, and should not start with a capital letter or end with punctuation.
 In the documentation, double backticks is code formatting, single is latex. So you should change, e.g.,
`self`
to``self``
.  For inputs, we are trying to standardize them to the form
 ``arg``  (optional) some explanation
(note, also no punctuation).
It also seems like what you want LR tableaux to inherit from is SemistandardTableaux_shape_weight
. This way you can just use the base class iterator instead of creating a new parent. Actually, better yet, you could just call for t in symmetrica.kostka_tab(self.shape, self.weight):
. As of right now, your iterator does not create instances of LittlewoodRichardsonTableau
:
sage: from sage.combinat.lr_tableau import LittlewoodRichardsonTableaux sage: LR = LittlewoodRichardsonTableaux([3,2,1],[[2,1],[2,1]]) sage: LR[0] [[1, 1, 3], [2, 3], [4]] sage: type(_) <class 'sage.combinat.tableau.SemistandardTableaux_shape_weight_with_category.element_class'>
comment:4 Changed 3 years ago by
 Commit changed from ec8d39c2a09ba88a0b411ceb5717cc408f18fa5d to d1269233c61e422cea3c39c3c2c6f1491ac20210
Branch pushed to git repo; I updated commit sha1. New commits:
d126923  fixed most of Travis' comments

comment:5 in reply to: ↑ 3 Changed 3 years ago by
Hi Travis,
Thanks for your comments. I fixed most of the issues you mention.
It also seems like what you want LR tableaux to inherit from is
SemistandardTableaux_shape_weight
. This way you can just use the base class iterator instead of creating a new parent. Actually, better yet, you could just callfor t in symmetrica.kostka_tab(self.shape, self.weight):
.
This suggestion does not seem to work. We are anyway planning to implement a smarter iterator, so it is probably not worth it to call symmetrica.
Anne
comment:6 followup: ↓ 7 Changed 3 years ago by
 Branch changed from u/aschilling/LRtableaux21615 to public/combinat/LR_tableaux21615
 Commit changed from d1269233c61e422cea3c39c3c2c6f1491ac20210 to 349083765c0cf1fd0fbb4fe30dee0db9af3d72f7
I reworked things around a bit so that the iterator doesn't create intermediate instances of SemistandardTableau
. I also added a __contains__
method and subsequently reworked the check
to avoid duplication. I also did a few other doc and little things, including lazily importing the LR tableaux into the global namespace. Let me know if you want to do the iterator on this ticket or on a followup.
New commits:
7e45dc9  Merge branch 'u/aschilling/LRtableaux21615' of git://trac.sagemath.org/sage into public/combinat/RC_tableaux21615

3490837  Some reviewer changes and fixes.

comment:7 in reply to: ↑ 6 Changed 3 years ago by
There seems to be a doctest failure now:
sage t finite_word.py ********************************************************************** File "finite_word.py", line 606, in sage.combinat.words.finite_word.FiniteWord_class.is_yamanouchi Failed example: w.is_yamanouchi(n=3) Exception raised: Traceback (most recent call last): File "/Applications/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run self.compile_and_execute(example, compiler, test.globs) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 861, in compile_and_execute exec(compiled, globs) File "<doctest sage.combinat.words.finite_word.FiniteWord_class.is_yamanouchi[5]>", line 1, in <module> w.is_yamanouchi(n=Integer(3)) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/finite_word.py", line 619, in is_yamanouchi w = Word(self, alphabet = range(1,n+1)) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/word.py", line 208, in Word parent = Words(alphabet) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/words.py", line 101, in Words return FiniteOrInfiniteWords(alphabet) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/words.py", line 1722, in __init__ AbstractLanguage.__init__(self, alphabet) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/words.py", line 149, in __init__ alphabet = build_alphabet(alphabet) File "/Applications/sage/local/lib/python2.7/sitepackages/sage/combinat/words/alphabet.py", line 268, in build_alphabet raise ValueError("unable to construct an alphabet from the given parameters") ValueError: unable to construct an alphabet from the given parameters ********************************************************************** 1 item had failures: 1 of 12 in sage.combinat.words.finite_word.FiniteWord_class.is_yamanouchi [1270 tests, 1 failure, 3.31 s]
I do not recall that it was there before, but I could be mistaken!
comment:8 followup: ↓ 14 Changed 3 years ago by
This comes from the fact that I used a new beta of sage, where words are now using Python3 style range
. It is not a list anymore, so the simplest fix is to wrap it in a list
.
comment:9 Changed 3 years ago by
 Commit changed from 349083765c0cf1fd0fbb4fe30dee0db9af3d72f7 to ecf10efd208418bd0ff95d2f84abd228dfca6077
Branch pushed to git repo; I updated commit sha1. New commits:
ecf10ef  Some changes to finite word, including Python3 compatibility.

comment:10 Changed 3 years ago by
 Status changed from needs_work to needs_review
I think this can go in now. We can reimplement the iterator later!
comment:11 Changed 3 years ago by
Then if you're happy with my latest changes, then you can set a positive review.
comment:12 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:13 Changed 3 years ago by
 Commit changed from ecf10efd208418bd0ff95d2f84abd228dfca6077 to 9c67f19c1a804f9ded7323eb164725ddb0e667fc
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
9c67f19  added an implementation of LR tableaux using Buch's lrcalc

comment:14 in reply to: ↑ 8 Changed 3 years ago by
Hi all,
I wrote an iterator, LRtabs_multi
, that calls Anders Buch's fast lrcalc code (which can compute LR tableaux with specified skew shape). The tableaux we want can be found using a sequence of lrcalc calls.
I didn't rewrite the current __iter__
method because this new one is slightly more general (it can compute skew tableaux rather than straight shape tableaux).
Jake
comment:15 Changed 3 years ago by
 Commit changed from 9c67f19c1a804f9ded7323eb164725ddb0e667fc to 1d3fe7cb2ffef65dcb87d008f1bb98db2c16b1b4
Branch pushed to git repo; I updated commit sha1. New commits:
1a8576a  Merge branch 'develop' into public/combinat/LR_tableaux21615

1a222e9  Merge branch 'public/combinat/LR_tableaux21615' of git://trac.sagemath.org/sage into public/combinat/LR_tableaux21615

90dc8e3  Merge branch 'public/combinat/LR_tableaux21615' of git://trac.sagemath.org/sage into public/combinat/LR_tableaux21615

8c63ec6  Merge branch 'develop' into public/combinat/LR_tableaux21615

a5666ba  new iterator along Jake's ideas

1d3fe7c  added Jake's name to authors

comment:16 Changed 3 years ago by
Hi Jake and all,
Thank you for your improvements. I rewrote the iter method that uses lrskew and your method _tableauJoin (which I renamed _tableau_join). It seems shorter than what you had as it does not need standardization or destandardization. See what you think. It should be relatively easy to upgrade the whole class to allow for SkewTableaux? as well. But perhaps we can leave that for another ticket?
Best,
Anne
comment:17 Changed 3 years ago by
 Milestone changed from sage7.4 to sage7.5
comment:18 Changed 3 years ago by
 Milestone changed from sage7.5 to sage7.6
comment:19 Changed 3 years ago by
 Commit changed from 1d3fe7cb2ffef65dcb87d008f1bb98db2c16b1b4 to 40414a3de57343af2078efa2ebffa09eb3c003de
Branch pushed to git repo; I updated commit sha1. New commits:
40414a3  Some last little tweaks.

comment:20 Changed 3 years ago by
 Milestone changed from sage7.6 to sage7.5
I made a few little more tweaks. If my changes look good, you can set it back to a positive review.
comment:21 Changed 3 years ago by
Thanks for the review!
comment:22 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:23 Changed 3 years ago by
 Branch changed from public/combinat/LR_tableaux21615 to 40414a3de57343af2078efa2ebffa09eb3c003de
 Resolution set to fixed
 Status changed from positive_review to closed
This is a first implementation of LR tableaux. Things to improve:
New commits:
first implementation of LittlewoodRichardson tableaux