Opened 7 years ago

Closed 6 years ago

#14131 closed enhancement (fixed)

Greene-Kleitman partition of a poset

Reported by: darij Owned by: sage-combinat
Priority: minor Milestone: sage-5.10
Component: combinatorics Keywords: RSK, permutations, days45
Cc: nthiery, chapoton Merged in: sage-5.10.beta5
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by tscrim)

The theory behind it is explained in Britz-Fomin, arXiv:9912126 (and briefly discussed in EC1, exercise 77 in chapter 3). It is a map associating to any poset P a partition \lambda(P) of |P|. For P being a permutation poset, this partition is the shape of the RSK tableaux of the permutation; the tableaux themselves can also be reconstructed by taking the sequences of \lambda(P_i) where P_i are the initial resp. final intervals of P.

This functionality appears in Macaulay ( http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/doc/Macaulay2/Posets/html/_greene__Kleitman__Partition.html ) but is apparently not exposed in Sage. I also don't like the Macaulay implementation, since (as far as I understand the sourcecode at http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.5/share/Macaulay2/Posets.m2 ) it goes by brute force despite the existence of a polynomial-time algorithm.

So I've implemented the algorithm given in Britz-Fomin.

Apply:

Attachments (7)

greene.py (19.2 KB) - added by darij 7 years ago.
greene_shape is the most important method here. The stuff after it is what I needed for checks; maybe it has its use too, but I wouldn't expect too much.
posets.py (132.1 KB) - added by darij 6 years ago.
posets.py. Should be diffed against devel/sage-main/sage/combinat/posets/posets.py as of 5.9.rc1
trac_14131_greene_shape_v1.patch (13.5 KB) - added by darij 6 years ago.
trac_14131-greene_shape_v2.patch (20.0 KB) - added by darij 6 years ago.
Updated file, replaces both mine and Travis's files so far
trac_14131-greene_shape_v2_conservative.patch (18.6 KB) - added by darij 6 years ago.
Alternative version of v2, which should no longer conflict with Travis' RSK changes; UPDATE: BUG FIXED
trac_14131-greene_shape_v2_conservative.2.patch (18.6 KB) - added by darij 6 years ago.
Alternative version of v2, which should no longer conflict with Travis' RSK changes; SECOND BUGFIX UPDATE!
trac_14131-greene_shape-review-ts.patch (8.9 KB) - added by tscrim 6 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 7 years ago by darij

  • Description modified (diff)

Changed 7 years ago by darij

greene_shape is the most important method here. The stuff after it is what I needed for checks; maybe it has its use too, but I wouldn't expect too much.

comment:2 Changed 7 years ago by darij

Reuploaded fixed version, with docstrings and doctests.

I assume it should eventually be merged into Posets, with the functions becoming methods (umm, the ones that aren't useless to begin with). The ford_fulkerson_chronicle method should get an underscore in front of it (right now this would break the doctests).

Changed 6 years ago by darij

posets.py. Should be diffed against devel/sage-main/sage/combinat/posets/posets.py as of 5.9.rc1

comment:3 Changed 6 years ago by darij

I have tried to make this into an actual patch but I need some help now. I somehow fucked up with hg mq, and the patch ended up empty. I don't have the old version of the file anymore, but I'm just using sage-main 5.9.rc1 (no other patches installed right now), so can anyone just diff the sage/combinat/posets/posets.py of that release against the posets.py I've uploaded and make the changes into a .patch?

Note that this will likely need manual merging with #14136 since both patches insert stuff at the same position; but there's no actual conflict.

As far as content is concerned, this contains the most important parts of greene.py with a couple bugfixes. The Greene-Kleitman partition of a poset is computed (in polynomial time). The doctests succeed, but I haven't tried compiling the doc (how does that work again?), so there might be formatting issues.

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

comment:4 Changed 6 years ago by darij

  • Cc nthiery chapoton added
  • Status changed from new to needs_review

Changed 6 years ago by darij

comment:5 Changed 6 years ago by darij

I've made this stuff into a patch [trac_14131_greene_shape_v1.patch] . Can anyone check if it applies correctly? (I am working from sage-main 5.9 rc1.) It might have a few stupid newline issues.

comment:6 Changed 6 years ago by tscrim

  • Status changed from needs_review to needs_work

Hey I've uploaded a review patch which fixes up some of the documenation. The doc of _ford_fulkerson_chronicle will still need to be standardized following the conventions page.

As for the potential conflect with #14136, I was able to apply this after but has some fuzz. All that means is it will need a qrefresh to be run.

Also the first patch is missing a commit message. Let me know when these are done and I can give it another code review. I'd prefer if someone else (Frederic) can give this a math review.

Best,
Travis

Last edited 6 years ago by tscrim (previous) (diff)

Changed 6 years ago by darij

Updated file, replaces both mine and Travis's files so far

comment:7 Changed 6 years ago by darij

Thanks a lot for the comments, Travis!

I've uploaded a new patch [trac_14131-greene_shape_v2.patch], which contains both of our changes and a few more. I've standardized the docstring of the Ford-Fulkerson chronicle, though it wouldn't harm to check whether standardized really means standardized. I've also added a (very simple) method to permutations.py to compute the permutation poset of a permutation, and while being there fixed a couple typos in the RSK docs (the changeset isn't very informative, but what I've done is replacing some "right" by "left" in the doc).

I'm not sure what "fuzz" exactly means; is it something like "the line numbers have shifted, but it's kinda clear where the changes belong"?

I don't know how to add a commit message...

comment:8 Changed 6 years ago by chapoton

to add a commit message, you can use

hg qrefresh - m "trac #14131 patch for doing really serious things"

or just

hg qrefresh -e

which will open a text editor

comment:9 Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

Then you'll also run

hg export trac_14131-greene_shape_v2.patch > /path/to/patch/trac_14131-greene_shape_v2.patch

Note that the export does not have to override the patch file, but you only would have to do it once if changes are subsequently made to the patch.

If you try to apply the one patch after the other, you should get something like "patch applied with fuzz 2 (offset 1 line)" or something like that. The fuzz is telling you somethings have moved, but it still applied.

Anyways, the doc looks much better but the inputs should be formatted in code with 2 backticks (see frank_network() for example).

I would prefer for this not to change the RSK docs since this will create a conflict with #8392 and is outside of the scope of this patch (same could be said of my changes to evacuation() and is_slender() [I believe that is what that function is called], but here the doc was more misformed). Also you'll need your real name in the Author section of the ticket, and we should make #14136 depend on this ticket because we need to sort out the doctest issue. Thanks.

comment:10 Changed 6 years ago by chapoton

  • Description modified (diff)

comment:11 Changed 6 years ago by chapoton

for the bot : apply trac_14131-greene_shape_v2.patch

comment:12 Changed 6 years ago by darij

Thank you @Travis and Frédéric for the help with hg! Now I guess I've got the whole mq picture. A shame it's soon to be obsoleted...

There is one thing I don't understand: [Travis] "Note that the export does not have to override the patch file, but you only would have to do it once if changes are subsequently made to the patch." Do what once?

I deliberately used 1 backtick for the variables since their font should match the font in which they appear in later LaTeX formulae. Is this against some convention?

Changed 6 years ago by darij

Alternative version of v2, which should no longer conflict with Travis' RSK changes; UPDATE: BUG FIXED

Changed 6 years ago by darij

Alternative version of v2, which should no longer conflict with Travis' RSK changes; SECOND BUGFIX UPDATE!

comment:13 Changed 6 years ago by darij

New version uploaded: trac_14131-greene_shape_v2_conservative.2.patch. This differs from the one from 2 days ago in that RSK methods are no longer being edited, and I have even changed the insertion point so it shouldn't even be close to RSK. I have tested on 5.10beta2 that this doesn't conflict with #8392 in either order of patching. Oh and I also fixed a documentation bug (the :meth: declaration used a wrong method name), put inputs in double backticks the first time they appear, and added a commit message.

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

comment:14 Changed 6 years ago by darij

  • Status changed from needs_work to needs_review

comment:15 Changed 6 years ago by darij

  • Description modified (diff)

comment:16 Changed 6 years ago by tscrim

  • Authors changed from darij to Darij Grinberg
  • Description modified (diff)

I've uploaded a new (version) review patch which makes some changes to the doc. If you agree with my changes, you can set this to positive review.

Also thanks for separating off the RSK changes.

Best,
Travis

comment:17 Changed 6 years ago by darij

Thank you for the review! There were some stupid doc blunders *oops*.

I agree with all of your changes except maybe two:

  • You replaced range by xrange -- wasn't xrange supposed to be deprecated? (Do let me know what you think, as my other patches have the same situation at times.)
  • I'd replace ``s`` -- the source vertex of `G` by ``s`` -- a vertex of `G`, to be used as the source vertex and similarly for t. This is to avoid the false impression that s needs to be a source in the sense of having no arrows going to s (that's not required).

comment:18 Changed 6 years ago by tscrim

I didn't know xrange was deprecated in python 3 (it might even be removed outright); I've changed it back. I've also tweaked those inputs around.

comment:19 follow-up: Changed 6 years ago by darij

TBH I'm not sure if this is a good reason; I was just saying this is the reason why I chose range. Looking at the changes in Python 3.0 ( http://docs.python.org/3.1/whatsnew/3.0.html ), I suspect that most of our code is going to break if we ever switch to 3.0 (I am using None < 0 several times in my Bender-Knuth code, for example), so I am not sure whether to expect such a switch in the nearest time...

comment:20 in reply to: ↑ 19 Changed 6 years ago by nthiery

Replying to darij:

TBH I'm not sure if this is a good reason; I was just saying this is the reason why I chose range. Looking at the changes in Python 3.0 ( http://docs.python.org/3.1/whatsnew/3.0.html ), I suspect that most of our code is going to break if we ever switch to 3.0 (I am using None < 0 several times in my Bender-Knuth code, for example), so I am not sure whether to expect such a switch in the nearest time...

I don't expect a switch in the short run. Yet I try to avoid using 2.0-only "features" without a compelling reason (but I certainly am unknowingly using some).

Cheers,

Nicolas

comment:21 Changed 6 years ago by tscrim

Hey Darij,

If you're happy with the latest review patch I've uploaded, you can set this to positive review.

Best,
Travis

comment:22 Changed 6 years ago by darij

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

comment:23 Changed 6 years ago by darij

Oops, of course! Yes, I'm happy with the review patch. But why are you suddenly making francophone typos? ("attachement")

comment:24 Changed 6 years ago by tscrim

...because I'm doing this on a keyboard I'm not used to? :P

comment:25 Changed 6 years ago by tscrim

  • Description modified (diff)

comment:26 Changed 6 years ago by darij

Touché. :D

comment:27 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

There is a problem with the documentation:

[combinat ] /mazur/release/merger/sage-5.10.beta5/local/lib/python2.7/site-packages/sage/combinat/posets/posets.py:docstring of sage.combinat.posets.posets:20: WARNING: Inline literal start-string without end-string.

Changed 6 years ago by tscrim

comment:28 Changed 6 years ago by tscrim

  • Status changed from needs_work to positive_review

Fixed, small typo. Sorry about that.

comment:29 Changed 6 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.