search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

Greene-Kleitman partition of a poset #14131

Closed darijgr closed 11 years ago

darijgr commented 11 years ago

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:

CC: @nthiery @fchapoton

Component: combinatorics

Keywords: RSK, permutations, days45

Author: Darij Grinberg

Reviewer: Travis Scrimshaw

Merged: sage-5.10.beta5

Issue created by migration from https://trac.sagemath.org/ticket/14131

darijgr commented 11 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 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 Greene-Kleitman. I'm not doing this as a patch, because I believe the Posets file is currently being worked on and this is likely to require manual merging (also, I am not currently using sage-combinat).
+So I've implemented the algorithm given in Britz-Fomin. I'm not doing this as a patch, because I believe the Posets file is currently being worked on and this is likely to require manual merging (also, I am not currently using sage-combinat).
darijgr commented 11 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.

darijgr commented 11 years ago
comment:2

Attachment: greene.py.gz

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).

darijgr commented 11 years ago

Attachment: posets.py.gz

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

darijgr commented 11 years ago
comment:3

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.

darijgr commented 11 years ago
comment:5

Attachment: trac_14131_greene_shape_v1.patch.gz

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.

tscrim commented 11 years ago
comment:6

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

darijgr commented 11 years ago

Attachment: trac_14131-greene_shape_v2.patch.gz

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

darijgr commented 11 years ago
comment:7

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...

fchapoton commented 11 years ago
comment:8

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

tscrim commented 11 years ago
comment:9

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.

tscrim commented 11 years ago

Reviewer: Travis Scrimshaw

fchapoton commented 11 years ago

Description changed:

--- 
+++ 
@@ -3,3 +3,6 @@
 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. I'm not doing this as a patch, because I believe the Posets file is currently being worked on and this is likely to require manual merging (also, I am not currently using sage-combinat).
+
+Apply:
+* [attachment: trac_14131-greene_shape_v2.patch](https://github.com/sagemath/sage-prod/files/10657149/trac_14131-greene_shape_v2.patch.gz)
fchapoton commented 11 years ago
comment:11

for the bot : apply trac_14131-greene_shape_v2.patch

darijgr commented 11 years ago
comment:12

Thank you @tscrim 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?

darijgr commented 11 years ago

Attachment: trac_14131-greene_shape_v2_conservative.patch.gz

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

darijgr commented 11 years ago

Attachment: trac_14131-greene_shape_v2_conservative.2.patch.gz

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

darijgr commented 11 years ago
comment:13

New version uploaded: attachment: 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.

darijgr commented 11 years ago

Description changed:

--- 
+++ 
@@ -5,4 +5,4 @@
 So I've implemented the algorithm given in Britz-Fomin. I'm not doing this as a patch, because I believe the Posets file is currently being worked on and this is likely to require manual merging (also, I am not currently using sage-combinat).

 Apply:
-* [attachment: trac_14131-greene_shape_v2.patch](https://github.com/sagemath/sage-prod/files/10657149/trac_14131-greene_shape_v2.patch.gz)
+* [attachment: trac_14131-greene_shape_v2_conservative.2.patch](https://github.com/sagemath/sage-prod/files/10657151/trac_14131-greene_shape_v2_conservative.2.patch.gz)
tscrim commented 11 years ago

Changed author from darij to Darij Grinberg

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,8 @@

 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. I'm not doing this as a patch, because I believe the Posets file is currently being worked on and this is likely to require manual merging (also, I am not currently using sage-combinat).
+So I've implemented the algorithm given in Britz-Fomin.

 Apply:
 * [attachment: trac_14131-greene_shape_v2_conservative.2.patch](https://github.com/sagemath/sage-prod/files/10657151/trac_14131-greene_shape_v2_conservative.2.patch.gz)
+* [attachement:trac_14131-green_shape-review-ts.patch]
tscrim commented 11 years ago
comment:16

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

darijgr commented 11 years ago
comment:17

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

I agree with all of your changes except maybe two:

tscrim commented 11 years ago
comment:18

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.

darijgr commented 11 years ago
comment:19

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...

nthiery commented 11 years ago
comment:20

Replying to @darijgr:

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

tscrim commented 11 years ago
comment:21

Hey Darij,

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

Best,

Travis

darijgr commented 11 years ago

Description changed:

--- 
+++ 
@@ -6,4 +6,4 @@

 Apply:
 * [attachment: trac_14131-greene_shape_v2_conservative.2.patch](https://github.com/sagemath/sage-prod/files/10657151/trac_14131-greene_shape_v2_conservative.2.patch.gz)
-* [attachement:trac_14131-green_shape-review-ts.patch]
+* [attachment: trac_14131-green_shape-review-ts.patch](https://github.com/sagemath/sage/files/ticket14131/trac_14131-green_shape-review-ts.patch.gz)
darijgr commented 11 years ago
comment:23

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

tscrim commented 11 years ago
comment:24

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

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -6,4 +6,4 @@

 Apply:
 * [attachment: trac_14131-greene_shape_v2_conservative.2.patch](https://github.com/sagemath/sage-prod/files/10657151/trac_14131-greene_shape_v2_conservative.2.patch.gz)
-* [attachment: trac_14131-green_shape-review-ts.patch](https://github.com/sagemath/sage/files/ticket14131/trac_14131-green_shape-review-ts.patch.gz)
+* [attachment: trac_14131-greene_shape-review-ts.patch](https://github.com/sagemath/sage-prod/files/10657152/trac_14131-greene_shape-review-ts.patch.gz)
darijgr commented 11 years ago
comment:26

Touché. :D

jdemeyer commented 11 years ago
comment:27

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.
tscrim commented 11 years ago

Attachment: trac_14131-greene_shape-review-ts.patch.gz

tscrim commented 11 years ago
comment:28

Fixed, small typo. Sorry about that.

jdemeyer commented 11 years ago

Merged: sage-5.10.beta5