Opened 4 years ago
Last modified 2 years ago
#20041 needs_work enhancement
Shifted tableaux
Reported by:  zhamaker  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage8.0 
Component:  combinatorics  Keywords:  days78 
Cc:  sagecombinat, tscrim, darij, andrew.mathas, aschilling, mantepse  Merged in:  
Authors:  Zachary Hamaker, Tobias Johnson, Andrew Mathas  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  public/combinat/shifted_tableaux20041 (Commits)  Commit:  323bdfd4daabe0eff12726aff65ed5cb487ee75b 
Dependencies:  Stopgaps: 
Description
Implement a class for standard shifted tableaux in SAGE. First features  enumeration, random generation, basic features.
Change History (29)
comment:1 Changed 4 years ago by
 Branch changed from u/zhamaker/shifted_tableau.py to u/zhamaker/shifted_tableau
comment:2 Changed 4 years ago by
 Branch changed from u/zhamaker/shifted_tableau to u/zhamaker/shifted_tableaux
 Commit set to e5c4a0bc28caf0e17a1a81fc3aebe52b76ea9f94
comment:3 Changed 4 years ago by
 Branch changed from u/zhamaker/shifted_tableaux to public/combinat/shifted_tableaux20041
 Commit changed from e5c4a0bc28caf0e17a1a81fc3aebe52b76ea9f94 to 050f0fbc8c72aa5de399c2ac64beb455cddcc62c
comment:4 Changed 4 years ago by
 Cc andrew.mathas added
comment:5 Changed 4 years ago by
Is anyone able to tell me what the status of this ticket is? I've recently become interested in shifted tableaux, so I'd be happy to contribute to finalising this. I have just checked and the code appears to work, after a rebase, on 7.3.beta5 and all doctests pass so I wondered what else needs to be done. Perhaps just the documentation?
comment:6 Changed 4 years ago by
Zach has told me that everything he wants is in there. So, yes, the only thing left is the documentation. Although we probably should copy over the code for pp
from Tableau
(well _repr_diagram
).
comment:7 Changed 4 years ago by
 Keywords days78 added
 Milestone changed from sage7.1 to sage7.3
comment:8 Changed 4 years ago by
 Commit changed from 050f0fbc8c72aa5de399c2ac64beb455cddcc62c to ee21f5ae05cb287d7680a17d121d588be7483f19
Branch pushed to git repo; I updated commit sha1. New commits:
c3d4934  initial version of shifted_tableaux.py, to be modified shortly by Travis

90cdbd2  Merging combinat/all.py

2c2fb90  Renaming file as tableau_shifted and adding methods

82ccc8a  Making more compatible with tableau.py

624a671  Adding more methods and making compatible with Tableaux.options

ee5ffd3  Adding class for StrictPartitions

a372b4f  Adding parent shifted tableaux classes

ee21f5a  Merging

comment:9 Changed 4 years ago by
I have done a fairly major makeover of this code. I have tried to make to more consistent with the rest of the tableaux code by adding options, quite a few new methods as well as some more parent classes:
ShiftedTableaux_all ShiftedTableaux_size ShiftedTableaux_shape
I have also created a StrictPartitions
class, with friends, in partition.py
because the shape of shifted tableaux is always a strict partition. Currently the StrictPartitions
class is not in the global namespace, but of course it could be.
Previously, the following worked:
sage: ShiftedTableau([[1,4,5]]) [[1, 4, 5]]
As Shiftedtabelaux
returns what I would call "standard" shifted tableaux I thought that this was incorrect, so it now raises an error:
sage: ShiftedTableau([[1,4,5]]) Traceback (most recent call last): ... ValueError: [[1, 4, 5]] is not an element of Shifted tableaux of shape [3].
Let me know if this is not what was intended.
Finally, I hope this is OK but I have taken some liberties with the code such as moving some of the helper functions into the ShiftedTableaux_size
class. Perhaps more significantly, I have renamed the main file tableau_shifted.py
as I think this is better organisationally (I know, k_tableau.py
does not follow this pattern).
Currently there is one failing doc text that I have not had time to sort out. I have also added more documentation, although I haven't checked it because to do this I'd need to do a make docclean
and it's late...
My main motivation for doing this is that I want to implement "shaded shifted tableaux", but I haven't started on this yet.
comment:10 Changed 3 years ago by
 Cc aschilling added
comment:11 Changed 3 years ago by
 Commit changed from ee21f5ae05cb287d7680a17d121d588be7483f19 to 1168c5900bf8d99da90629650ea67cb68e70bcb2
Branch pushed to git repo; I updated commit sha1. New commits:
1168c59  Merge branch 'public/combinat/shifted_tableaux20041' of git://trac.sagemath.org/sage into public/combinat/shifted_tableaux20041

comment:12 followup: ↓ 13 Changed 3 years ago by
 Milestone changed from sage7.3 to sage8.0
Rebased. Sorry Andrew, I completely lost track of this.
Related #22921.
comment:13 in reply to: ↑ 12 Changed 3 years ago by
Replying to tscrim:
Rebased. Sorry Andrew, I completely lost track of this.
Related #22921.
Sorry, I forgot about this as well. There seems to be a recursion problem now in generating shifted tableaux  which I don't think happened earlier? I will see if I can fix this but I am swamped with teaching at the moment so it won't happen straight away.
comment:14 Changed 3 years ago by
please see my patchbot's report:
 use python3 syntax for print
 use python3 syntax for metaclass (search in sage code to see how this must be done now)
Plus many failing doctests, including an infinite recursion.
comment:15 Changed 3 years ago by
 Commit changed from 1168c5900bf8d99da90629650ea67cb68e70bcb2 to 48a5451e9387514dd9133bc6e6a857fd2c3f650f
comment:16 Changed 3 years ago by
 Commit changed from 48a5451e9387514dd9133bc6e6a857fd2c3f650f to 02db562f79a1bc9f27e5d79c77ac4a68534671d8
Branch pushed to git repo; I updated commit sha1. New commits:
02db562  Python3 compatibility.

comment:17 Changed 3 years ago by
 Status changed from new to needs_review
So there were a number of things that had changed in the backends that needed to be fixed here.
The first is what caused the infinite loop, which caused by cardinality
> __iter__
> __len__
> cardinality
. I broke this by having a direct counting in cardinality
using the faster iterator (which doesn't create an instance of the element class, avoiding extra overhead).
There was also some issues with how the facade parents were handled and there elements are constructed. Now DisjointUnionEnumeratedSets
better handles facade parents, which exposed the issue. This wasn't too hard to clean up.
My other changes were some other small cleanup on the docstrings.
I don't have an idea about the sage: ShiftedTableau([[1,4,5]])
change from comment:9. Anne, Zach, Darij, any objections/comments?
Otherwise, I think this is ready for review, so I am setting it as such.
comment:18 followup: ↓ 19 Changed 3 years ago by
Sorry for being incommunicado for so long. I'll be back to working on this project in the near future.
I don't have an idea about the
sage: ShiftedTableau([[1,4,5]])
change from comment:9. Anne, Zach, Darij, any objections/comments?
I think we should construct a separate class for StandardShiftedTableau
(or should it be ShiftedStandardTableau
?). In the near term, I plan to implement the various insertion algorithms, which require semistandard tableaux.
comment:19 in reply to: ↑ 18 Changed 3 years ago by
Replying to zhamaker:
I think we should construct a separate class for
StandardShiftedTableau
(or should it beShiftedStandardTableau
?). In the near term, I plan to implement the various insertion algorithms, which require semistandard tableaux.
In that case, in order not to have to deprecate everything in the near future, this should be changed before the ticket is reviewed and the code is incorporated into sage. A quick fix would be to rename all of the existing classes so that they have "Standard" in their name. A proper fix would be to implement new base classes, following the current pattern in the file, and to have the standard versions inherit from them. I don't have time to do this at the moment, but both options should not be too hard to implement.
comment:21 Changed 3 years ago by
 Commit changed from 02db562f79a1bc9f27e5d79c77ac4a68534671d8 to bfcb1ca0a2f8fe7f30ce917b7188b468a22b5b0d
Branch pushed to git repo; I updated commit sha1. New commits:
bfcb1ca  Merge branch 'public/combinat/shifted_tableaux20041' of git://trac.sagemath.org/sage into public/combinat/shifted_tableaux20041

comment:22 followup: ↓ 24 Changed 3 years ago by
I just had a look at this  are there any outstanding issues?
It would be nice to have ascii_art
and unicode_art
work, see Tableau._ascii_art_
.
Observation: StrictPartitions
is the same as Partitions(n, max_slope=1)
, except that StrictPartitions
is much faster.
Question: ShiftedTableau
inherits from ClonableArray
, wheras Tableau
inherits from ClonableList
. Is there a reason to this?
comment:23 Changed 3 years ago by
 Cc mantepse added
comment:24 in reply to: ↑ 22 ; followup: ↓ 25 Changed 3 years ago by
Sorry for my slow reply!
Replying to mantepse:
I just had a look at this  are there any outstanding issues?
I am not currently able to compile sage due to a skylake issue, but the comments above suggest that the branch does not apply to the current sage beta. This is almost certainly due to some more recent changes to partition.py
, so it shouldn't be hard to fix but will need to be done...
Secondly, there is the question/comment above about implementing a separate classes forShiftedStandardTableau
and ShiftedStandardTableau
. Currently, the shifted tableaux are really shifted *stanbdard* tableaux, so this probably should be done. zhamaker suggested doing this but no one has done it yet.
It would be nice to have
ascii_art
andunicode_art
work, seeTableau._ascii_art_
.
This is not something that I feed strongly about but, yes, it would be good to have. I made sure that the latex
method works.
Observation:
StrictPartitions
is the same asPartitions(n, max_slope=1)
, except thatStrictPartitions
is much faster.
I can't remember how Partitions
generates this but as it is generic code it is not surprising that the code here, which from memory uses code from posets, is faster. It is possible that the code in Partitions
could be made faster by using the same approach, but that should be done in a separate ticket, I think.
Question:
ShiftedTableau
inherits fromClonableArray
, whereasTableau
inherits fromClonableList
. Is there a reason to this?
Probably \ClobableList
should be used. I used ClonableArray
because, for me, the entries of such tableaux are always integers but it is probably more sensible to allow the entries to be arbitrary objects, in which case \ClobableList
is better.
comment:25 in reply to: ↑ 24 Changed 3 years ago by
Replying to andrew.mathas:
Secondly, there is the question/comment above about implementing a separate classes for
ShiftedStandardTableau
andShiftedStandardTableau
. Currently, the shifted tableaux are really shifted *stanbdard* tableaux, so this probably should be done. zhamaker suggested doing this but no one has done it yet.
I guess this ticket needs coordinization with #22921, which implements ShiftedPrimedTableaux
.
It would be nice to have
ascii_art
andunicode_art
work, seeTableau._ascii_art_
.This is not something that I feed strongly about but, yes, it would be good to have. I made sure that the
latex
method works.
Note that the ShiftedPrimedTableaux
class has this now. I think it would be quite fruitful to factor out the common functionality into a separate class for "fillingsoftableaulikeshapes', but I'm afraid that's work.
Question:
ShiftedTableau
inherits fromClonableArray
, whereasTableau
inherits fromClonableList
. Is there a reason to this?Probably
\ClobableList
should be used. I usedClonableArray
because, for me, the entries of such tableaux are always integers but it is probably more sensible to allow the entries to be arbitrary objects, in which case\ClobableList
is better.
I'm assuming that you mean ClonableList
. Travis argued at https://trac.sagemath.org/ticket/22921#comment:32 that actually Tableau
should use ClonableArray
...
comment:26 Changed 2 years ago by
Any progress on this? I'd be interested in using this class if it were in Sage.
comment:27 Changed 2 years ago by
What needs to be done now is using the implementation in #22921 as a basis for this and seeing what common functionality should be factored out. It's been a little too long since I looked at this to saying anything intelligent at this point, and I don't currently have time to make any more progress on this unfortunately.
comment:28 Changed 2 years ago by
 Commit changed from bfcb1ca0a2f8fe7f30ce917b7188b468a22b5b0d to 62ff787a217361565e178979c0786fc177125e56
Branch pushed to git repo; I updated commit sha1. New commits:
62ff787  Merge branch 'public/combinat/shifted_tableaux20041' in 8.2.b8

comment:29 Changed 2 years ago by
 Commit changed from 62ff787a217361565e178979c0786fc177125e56 to 323bdfd4daabe0eff12726aff65ed5cb487ee75b
Branch pushed to git repo; I updated commit sha1. New commits:
323bdfd  trac 20041 detail

New commits:
initial version of shifted_tableaux.py, to be modified shortly by Travis