Change the method cardinality to StandardTableaux of fixed size

[g.chatel]

Change the method cardinality in the class StandardTableaux_size

Before:

sage: timeit('StandardTableaux(8).cardinality()')
125 loops, best of 3: 3.53 ms per loop
sage: timeit('StandardTableaux(10).cardinality()')
125 loops, best of 3: 7.58 ms per loop
sage: timeit('StandardTableaux(12).cardinality()')
25 loops, best of 3: 15.5 ms per loop

With the patch:

sage: timeit('StandardTableaux(8).cardinality()') 
625 loops, best of 3: 119 µs per loop
sage: timeit('StandardTableaux(10).cardinality()')
625 loops, best of 3: 136 µs per loop
sage: timeit('StandardTableaux(12).cardinality()')
625 loops, best of 3: 153 µs per loop
sage: timeit('StandardTableaux(50).cardinality()')
625 loops, best of 3: 642 µs per loop

---

Apply:

• cardinality_for_standard_tableaux-gc.patch​
• trac_14461-review-mh.patch​
• trac_14461-cardinality_standard_tableaux-review-ts.patch​

[tscrim]

Hey,

Could you make the following changes:

• describe the algorithm that you are using the doc,
• add a test to show that your computation agrees with the constructed number (for some smaller n than 50 of course),
• put your (real) name in the authors block.

Thanks,
Travis

[g.chatel]

Here is a new version of my patch with tests. Sorry, I'm not a native speaker and this would my first contribution.

Instead of using hook formula on every shape of Young tableau my algorithm counts the number of involution of size n which are in bijection with standard tableau of size n.

Sage seems do be limited around size 35 :

sage: timeit('StandardTableaux(35).cardinality()')
5 loops, best of 3: 5.83 s per loop

With the patch

sage: timeit('StandardTableaux(35).cardinality()')         
625 loops, best of 3: 390 µs per loop

[tscrim]

Hey Gregory,

This is a great speedup, and I was surprised that involutions, or at least counting them, is not currently in Sage (there must surely be a ticket for this...). Anyways, I've uploaded a review patch which adds the description of the cardinality. If you are happy with the changes, feel free to set this to positive review.

Best,
Travis

In case you are unaware, to check you should apply my review patch after yours, run sage -b, then run sage -docbuild reference/combinat html and look at your (local) documentation. Feel free to ask me questions if you need to.

[mhansen]

Heh, I just added my own review patch (on top of the original, not yours). I added a reference to Fulton's Young Tableaux as well as made some minor changes. These give about a 3x speedup on the original (new) implementation. I also didn't test nearly as many values since it adds like an extra 3 seconds to the files tests.

[tscrim]

Hey Mike,

I'll merge your review patch with some of my doc additions and repost that (especially since you get a 3x speedup). Should be up within 15 minutes.

[tscrim]

Hey Mike,

I've tweaked my review patch to apply after yours. If your happy with my changes, then you can set this to positive review.

Thanks,
Travis

[mhansen]

Looks good.

[tscrim]

Thanks Mike. Thanks Gregory, and welcome to the sage development community.

[mhansen]

I just updated the reference for Fulton's Young Tableaux.

[jdemeyer]

trac_14461-review-mh.patch​ needs a proper commit message.

[mhansen]

Done