Opened 8 years ago

Closed 8 years ago

#14574 closed enhancement (fixed)

Bender-Knuth involutions and standardization of semistandard Young tableaux

Reported by: darij Owned by: sage-combinat
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords: tableaux, partitions, combinat
Cc: tscrim Merged in: sage-5.10.beta5
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by darij)

I've implemented standardization and Bender-Knuth involutions on straight and skew semistandard tableaux. I've also fixed two typos in error strings and copied some methods for straight tableaux into the skew tableaux file (though I believe much more should be done in this direction).

EDIT: Finished, thanks to Travis.

Apply:

Attachments (7)

trac_14574_preliminary_version.patch (12.4 KB) - added by darij 8 years ago.
not yet merge ready
trac_14574-bender_knuth_et_al-v1.patch (24.5 KB) - added by darij 8 years ago.
trac_14574-bender_knuth_et_al-v1.2.patch (24.5 KB) - added by darij 8 years ago.
Finished version -- please review
trac_14574-bender_knuth-review-ts.patch (33.2 KB) - added by tscrim 8 years ago.
for_comparison.patch (20.1 KB) - added by darij 8 years ago.
just for comparison
trac_14574-folded.patch.txt (20.4 KB) - added by darij 8 years ago.
trac_14574-folded.patch (20.4 KB) - added by darij 8 years ago.
folded version with a few more corrections

Download all attachments as: .zip

Change History (19)

Changed 8 years ago by darij

not yet merge ready

comment:1 Changed 8 years ago by darij

  • Description modified (diff)

Changed 8 years ago by darij

Changed 8 years ago by darij

Finished version -- please review

comment:2 Changed 8 years ago by darij

  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 8 years ago by darij

[trac_14574-bender_knuth_et_al-v1.2.patch] and [trac_14574-bender_knuth_et_al-v1.patch] are the same file; I derped again when uploading.

comment:4 Changed 8 years ago by tscrim

  • Authors changed from darij to Darij Grinberg
  • Reviewers set to Travis Scrimshaw

Hey Darij,

I've made some changes in my review patch to the implementations. In particular, here's a comparison of my implementation of the Bender-Knuth inversions. Here's mine:

sage: T = SemistandardTableaux(shape=[6,3,3,1], max_entry=5)
sage: T.cardinality()
4000
sage: %time L = [x.bender_knuth_involution(2) for x in T]
CPU times: user 4.49 s, sys: 0.21 s, total: 4.70 s
Wall time: 4.94 s

Yours:

sage: %time L = [x.bender_knuth_involution(2) for x in T]
CPU times: user 4.78 s, sys: 0.11 s, total: 4.88 s
Wall time: 5.16 s

So there's not much difference, but I'd guess mine could be shown (eventually) to be slightly faster on larger sets. Anyways, if you agree with my changes, you can set this to positive review.

Thanks,
Travis

PS - For future reference, you'll need your real name in the authors section.

comment:5 Changed 8 years ago by tscrim

  • Description modified (diff)

comment:6 Changed 8 years ago by darij

Hi Travis! That was quick.

skew_tableau.py:

Oops, I have no idea how I managed to add a second to_row method instead of changing the old one; thanks for being more attentive than I was. But could you add these tests

            sage: SkewTableau([[None, None, None], [None]]).to_word_by_row()
            word: 
            sage: SkewTableau([]).to_word_by_row()
            word: 

into the to_word_by_row method? Thanks. (Maybe also into to_word_by_column?)

My reasoning behind the straight=False keyword is that when I call standardization on a standard tableau, I don't want the output to be checked for standardness twice (once for standardness as a skew standard tableau, and then again for standardness when transformed into a standard tableau). Is this a moot point? I am not sure if our classes actually do all that checking, but even if they don't I assume they eventually will.

Here's something I should have done myself: In the docstring of to_permutation, can you explain what "reading order" means? The notation is not as standard as people think it is; for instance, van Leeuwen's Littlewood-Richardson paper ( http://www-math.univ-poitiers.fr/~maavl/pdf/lrr.pdf ) defines "a reading order" rather than "the reading order". (And our reading order is neither Semitic nor Kanji; I don't think anyone ever wrote in that order...)

On line 504 in your revision, replace "self" by "T".

On the next line, "revsersed" should be "reversed".

On line 515, "True" should be backticked from both sides.

Line 576 in your revision: "*Bender-Knuth involution*" should be "*k-th Bender-Knuth involution*". Sorry, that one is my own oversight.

Line 587: "over all i" -> "over all i ranging over this iterable" (or however this is normally said).

Line 591 of revision: Again, "True" needs more backticks.

Line 659: Why do you import bisect_right when you don't use it?

Lines 663-694: Is the compiler smart enough that replacing all those calls of result_tab[i] by result_tab_i after first declaring result_tab_i to be result_tab[i] won't add any performance? If so, this could save me some work in the future.

Line 681: Add whitespaces to k+1 for consistency.

tableau.py:

On the docstrings, most of the above stuff applies again (sorry for duplication).

Line 885: Why the "skew"?

Line 892: why did you add "skew"?

Line 938: Could you pass the check variable as well? Or is this automatic?

Good point that the theorems belong into the Examples, not the Tests section. Good job on the docs as well.

Last edited 8 years ago by darij (previous) (diff)

comment:7 Changed 8 years ago by tscrim

This should take care of everything.

For the straight issue, I did not like this way of doing things. However there are other issues in the safety checks being made which I think should be on another ticket. I'm pretty sure some things are checked twice, and there should be a way which naturally converts from (semi)standard skew tableaux to (semi)standard tableaux without (semi)standardness (and tableaux) checks.

Anyways, if you'd want, you can pull out the involution part as a separate function which returns a list of lists. It's up to you if you're fine with my implementation or to change it.

Best,
Travis

Changed 8 years ago by tscrim

Changed 8 years ago by darij

just for comparison

comment:8 Changed 8 years ago by darij

Thanks for the speedy review. I've folded the review with my old file and thrown in a couple more corrections. I guess I'll open a separate ticket for unchecked generation of tableau objects; this makes more sense to solve on a global scale.

Here for_comparison.patch is just the result of folding, without my corrections.

comment:9 Changed 8 years ago by tscrim

Very minor nitpick, but could you make the commit message more about what the patch does? Once you've done that, you can set this to positive review. Thanks Darij.

Changed 8 years ago by darij

Changed 8 years ago by darij

folded version with a few more corrections

comment:10 Changed 8 years ago by darij

  • Description modified (diff)
  • Status changed from needs_review to positive_review

comment:11 Changed 8 years ago by vbraun

patchbot:

apply trac_14574-folded.patch

comment:12 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.10.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.