Opened 3 years ago

Closed 3 years ago

#21615 closed enhancement (fixed)

Implementation of Littlewood-Richardson tableaux

Reported by: aschilling Owned by:
Priority: major Milestone: sage-7.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 aschilling)

This patch implements a new class for Littlewood-Richardson tableaux.

Change History (23)

comment:1 Changed 3 years ago by tscrim

  • Cc tscrim added

comment:2 Changed 3 years ago by aschilling

  • Authors set to Maria Gillespie, Anne Schilling
  • Branch set to u/aschilling/LR-tableaux-21615
  • Commit set to ec8d39c2a09ba88a0b411ceb5717cc408f18fa5d
  • Description modified (diff)
  • Status changed from new to needs_review

This is a first implementation of LR tableaux. Things to improve:

  • allow for skew LR tableaux
  • improve the iterator (it is currently a dumb iterator selecting semistandard tableaux that are LR with respect to a given sequence of weights)

New commits:

ec8d39cfirst implementation of Littlewood-Richardson tableaux

comment:3 follow-up: Changed 3 years ago by tscrim

  • 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 the INPUT: 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 git

  • Commit changed from ec8d39c2a09ba88a0b411ceb5717cc408f18fa5d to d1269233c61e422cea3c39c3c2c6f1491ac20210

Branch pushed to git repo; I updated commit sha1. New commits:

d126923fixed most of Travis' comments

comment:5 in reply to: ↑ 3 Changed 3 years ago by aschilling

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 call for 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 follow-up: Changed 3 years ago by tscrim

  • Branch changed from u/aschilling/LR-tableaux-21615 to public/combinat/LR_tableaux-21615
  • 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:

7e45dc9Merge branch 'u/aschilling/LR-tableaux-21615' of git://trac.sagemath.org/sage into public/combinat/RC_tableaux-21615
3490837Some reviewer changes and fixes.

comment:7 in reply to: ↑ 6 Changed 3 years ago by aschilling

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/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Applications/sage/local/lib/python2.7/site-packages/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/site-packages/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/site-packages/sage/combinat/words/word.py", line 208, in Word
        parent = Words(alphabet)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/words/words.py", line 101, in Words
        return FiniteOrInfiniteWords(alphabet)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/words/words.py", line 1722, in __init__
        AbstractLanguage.__init__(self, alphabet)
      File "/Applications/sage/local/lib/python2.7/site-packages/sage/combinat/words/words.py", line 149, in __init__
        alphabet = build_alphabet(alphabet)
      File "/Applications/sage/local/lib/python2.7/site-packages/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 follow-up: Changed 3 years ago by tscrim

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 git

  • Commit changed from 349083765c0cf1fd0fbb4fe30dee0db9af3d72f7 to ecf10efd208418bd0ff95d2f84abd228dfca6077

Branch pushed to git repo; I updated commit sha1. New commits:

ecf10efSome changes to finite word, including Python3 compatibility.

comment:10 Changed 3 years ago by aschilling

  • 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 tscrim

Then if you're happy with my latest changes, then you can set a positive review.

comment:12 Changed 3 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:13 Changed 3 years ago by git

  • 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:

9c67f19added an implementation of LR tableaux using Buch's lrcalc

comment:14 in reply to: ↑ 8 Changed 3 years ago by j.levinson

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 git

  • Commit changed from 9c67f19c1a804f9ded7323eb164725ddb0e667fc to 1d3fe7cb2ffef65dcb87d008f1bb98db2c16b1b4

Branch pushed to git repo; I updated commit sha1. New commits:

1a8576aMerge branch 'develop' into public/combinat/LR_tableaux-21615
1a222e9Merge branch 'public/combinat/LR_tableaux-21615' of git://trac.sagemath.org/sage into public/combinat/LR_tableaux-21615
90dc8e3Merge branch 'public/combinat/LR_tableaux-21615' of git://trac.sagemath.org/sage into public/combinat/LR_tableaux-21615
8c63ec6Merge branch 'develop' into public/combinat/LR_tableaux-21615
a5666banew iterator along Jake's ideas
1d3fe7cadded Jake's name to authors

comment:16 Changed 3 years ago by aschilling

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 dimpase

  • Milestone changed from sage-7.4 to sage-7.5

comment:18 Changed 3 years ago by vbraun

  • Milestone changed from sage-7.5 to sage-7.6

comment:19 Changed 3 years ago by git

  • Commit changed from 1d3fe7cb2ffef65dcb87d008f1bb98db2c16b1b4 to 40414a3de57343af2078efa2ebffa09eb3c003de

Branch pushed to git repo; I updated commit sha1. New commits:

40414a3Some last little tweaks.

comment:20 Changed 3 years ago by tscrim

  • Authors changed from Maria Gillespie, Anne Schilling to Maria Gillespie, Anne Schilling, Jake Levinson
  • Milestone changed from sage-7.6 to sage-7.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 aschilling

Thanks for the review!

comment:22 Changed 3 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:23 Changed 3 years ago by vbraun

  • Branch changed from public/combinat/LR_tableaux-21615 to 40414a3de57343af2078efa2ebffa09eb3c003de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.