Opened 4 years ago

Last modified 2 years ago

#20041 needs_work enhancement

Shifted tableaux

Reported by: zhamaker Owned by: sage-combinat
Priority: major Milestone: sage-8.0
Component: combinatorics Keywords: days78
Cc: sage-combinat, 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_tableaux-20041 (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 zhamaker

  • Branch changed from u/zhamaker/shifted_tableau.py to u/zhamaker/shifted_tableau

comment:2 Changed 4 years ago by zhamaker

  • Branch changed from u/zhamaker/shifted_tableau to u/zhamaker/shifted_tableaux
  • Commit set to e5c4a0bc28caf0e17a1a81fc3aebe52b76ea9f94

New commits:

e5c4a0binitial version of shifted_tableaux.py, to be modified shortly by Travis

comment:3 Changed 4 years ago by tscrim

  • Branch changed from u/zhamaker/shifted_tableaux to public/combinat/shifted_tableaux-20041
  • Commit changed from e5c4a0bc28caf0e17a1a81fc3aebe52b76ea9f94 to 050f0fbc8c72aa5de399c2ac64beb455cddcc62c

New commits:

24bfda7Merge branch 'u/zhamaker/shifted_tableaux' of trac.sagemath.org:sage into public/combinat/shifted_tableaux-20041
050f0fbFirst round of reviewer changes.

comment:4 Changed 4 years ago by andrew.mathas

  • Cc andrew.mathas added

comment:5 Changed 4 years ago by andrew.mathas

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 doc-tests pass so I wondered what else needs to be done. Perhaps just the documentation?

comment:6 Changed 4 years ago by tscrim

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 tscrim

  • Keywords days78 added
  • Milestone changed from sage-7.1 to sage-7.3

comment:8 Changed 4 years ago by git

  • Commit changed from 050f0fbc8c72aa5de399c2ac64beb455cddcc62c to ee21f5ae05cb287d7680a17d121d588be7483f19

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

c3d4934initial version of shifted_tableaux.py, to be modified shortly by Travis
90cdbd2Merging combinat/all.py
2c2fb90Renaming file as tableau_shifted and adding methods
82ccc8aMaking more compatible with tableau.py
624a671Adding more methods and making compatible with Tableaux.options
ee5ffd3Adding class for StrictPartitions
a372b4fAdding parent shifted tableaux classes
ee21f5aMerging

comment:9 Changed 4 years ago by andrew.mathas

I have done a fairly major make-over 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 doc-clean 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 tscrim

  • Cc aschilling added

comment:11 Changed 3 years ago by git

  • Commit changed from ee21f5ae05cb287d7680a17d121d588be7483f19 to 1168c5900bf8d99da90629650ea67cb68e70bcb2

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

1168c59Merge branch 'public/combinat/shifted_tableaux-20041' of git://trac.sagemath.org/sage into public/combinat/shifted_tableaux-20041

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

  • Authors changed from Zachary Hamaker, Tobias Johnson to Zachary Hamaker, Tobias Johnson, Andrew Mathas
  • Milestone changed from sage-7.3 to sage-8.0

Rebased. Sorry Andrew, I completely lost track of this.

Related #22921.

comment:13 in reply to: ↑ 12 Changed 3 years ago by andrew.mathas

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 chapoton

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 git

  • Commit changed from 1168c5900bf8d99da90629650ea67cb68e70bcb2 to 48a5451e9387514dd9133bc6e6a857fd2c3f650f

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

5a2da1aFixing infinite recursion and some other reviewer changes.
5672c9dFixing facade and element constructor for shifted tableaux.
48a5451Removed old file and some last details.

comment:16 Changed 3 years ago by git

  • Commit changed from 48a5451e9387514dd9133bc6e6a857fd2c3f650f to 02db562f79a1bc9f27e5d79c77ac4a68534671d8

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

02db562Python3 compatibility.

comment:17 Changed 3 years ago by tscrim

  • 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 follow-up: Changed 3 years ago by zhamaker

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 semi-standard tableaux.

comment:19 in reply to: ↑ 18 Changed 3 years ago by andrew.mathas

Replying to zhamaker:

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 semi-standard 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:20 Changed 3 years ago by chapoton

  • Status changed from needs_review to needs_work

does not apply

comment:21 Changed 3 years ago by git

  • Commit changed from 02db562f79a1bc9f27e5d79c77ac4a68534671d8 to bfcb1ca0a2f8fe7f30ce917b7188b468a22b5b0d

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

bfcb1caMerge branch 'public/combinat/shifted_tableaux-20041' of git://trac.sagemath.org/sage into public/combinat/shifted_tableaux-20041

comment:22 follow-up: Changed 3 years ago by mantepse

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 mantepse

  • Cc mantepse added

comment:24 in reply to: ↑ 22 ; follow-up: Changed 3 years ago by andrew.mathas

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 and unicode_art work, see Tableau._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 as Partitions(n, max_slope=-1), except that StrictPartitions 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 from ClonableArray, whereas Tableau inherits from ClonableList. 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 mantepse

Replying to andrew.mathas:

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.

I guess this ticket needs coordinization with #22921, which implements ShiftedPrimedTableaux.

It would be nice to have ascii_art and unicode_art work, see Tableau._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 "fillings-of-tableau-like-shapes', but I'm afraid that's work.

Question: ShiftedTableau inherits from ClonableArray, whereas Tableau inherits from ClonableList. 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.

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 jessicapalencia

Any progress on this? I'd be interested in using this class if it were in Sage.

comment:27 Changed 2 years ago by tscrim

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 git

  • Commit changed from bfcb1ca0a2f8fe7f30ce917b7188b468a22b5b0d to 62ff787a217361565e178979c0786fc177125e56

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

62ff787Merge branch 'public/combinat/shifted_tableaux-20041' in 8.2.b8

comment:29 Changed 2 years ago by git

  • Commit changed from 62ff787a217361565e178979c0786fc177125e56 to 323bdfd4daabe0eff12726aff65ed5cb487ee75b

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

323bdfdtrac 20041 detail
Note: See TracTickets for help on using tickets.