Opened 7 years ago
Closed 7 years ago
#15428 closed enhancement (fixed)
Partitions to posets
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.2 |
Component: | combinatorics | Keywords: | sage-combinat, partition, poset |
Cc: | sage-combinat, tscrim, aschilling, ncohen | Merged in: | |
Authors: | Darij Grinberg | Reviewers: | Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | public/combinat/partitions_posets (Commits, GitHub, GitLab) | Commit: | b36286fef9ed6cc9f0b01dce6208add4b3acac0d |
Dependencies: | #15350 | Stopgaps: |
Description (last modified by )
This adds methods to partition.py
and skew_partition.py
that take a partition to its corresponding poset. The user can choose the orientation of the poset from currently 4 geographical ones (if anyone knows some more -- let me know).
Attachments (1)
Change History (30)
comment:1 Changed 7 years ago by
- Cc sage-combinat tscrim aschilling ncohen added
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
comment:3 Changed 7 years ago by
- Reviewers set to Travis Scrimshaw
- Status changed from needs_review to positive_review
Looks good to me. Thanks.
comment:4 Changed 7 years ago by
- Status changed from positive_review to needs_work
The documentation doesn't build properly:
dochtml.log:[combinat ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/combinat/partition.py:docstring of sage.combinat.partition.Partition.poset:21: WARNING: Inline interpreted text or phrase reference start-string without end-string. dochtml.log:[combinat ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/combinat/partition.py:docstring of sage.combinat.partition.Partition.poset:21: WARNING: Inline interpreted text or phrase reference start-string without end-string. dochtml.log:[combinat ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/combinat/skew_partition.py:docstring of sage.combinat.skew_partition.SkewPartition.poset:21: WARNING: Inline interpreted text or phrase reference start-string without end-string. dochtml.log:[combinat ] /scratch/release/merger/sage-5.13.rc0/local/lib/python2.7/site-packages/sage/combinat/skew_partition.py:docstring of sage.combinat.skew_partition.SkewPartition.poset:21: WARNING: Inline interpreted text or phrase reference start-string without end-string.
comment:5 Changed 7 years ago by
- Status changed from needs_work to positive_review
Thanks for spotting this one! It's weird: apparently sphinx doesn't like
the `5`th element
(but
the `5`-th element
works fine).
comment:6 Changed 7 years ago by
I agree that there is a natural correspondance between a tableau (or more generally filling) and a poset. So having a poset method in tableaux definitely makes sense.
Here the process is more about getting from a partition to a tableaux (or filling) using some filling scheme, and then asking for the poset. It would be natural for the invokation to reflect that:
sage: P = Partition(...) sage: P.tableau(orientation).poset() # or P.filling(orientation)
If you believe a shorthand for the above really brings something to the user, please find something more explicit than just poset
.
In general: I am super glad of all the work you are both puting into Sage, and all the progress that comes from the pair of you crossreviewing. But please keep in mind that we will have to maintain the code in the long run; so think *really, really* hard about good user interface and conciseness.
Thanks guys! Keep it up!
Nicolas
comment:7 Changed 7 years ago by
Hi Nicholas,
what exactly should the poset()
method on tableaux do? The way I understand the situation, the poset really comes from the *diagram*. I could imagine relabelling it according to the entries in a permutation tableau, but that's not the way I was thinking about it. If I correctly understand your proposal, my P.poset(orientation="SE")
would be something like P.superstandard_tableau().poset()
in your syntax, which is quite roundabout in my opinion since the superstandard tableau (the tableau in which you put 1, 2, ..., |P| just row by row) is a red herring to my construction (it could just as well be the co-superstandard one, where you proceed column by column; it is certainly not canonical). But TBH the main reason why I don't want to change things right now is that I want tableaux.py
to be redone by myself or someone else (IIRC we have discussed this long ago, and I'd be happy to discuss this again, though I probably can't meet your demands on speed and MuPAD-combinat code reuse -- my goals are more about getting skew_tableau
closer to tableaux
's feature completeness, and about implementing plane partitions and some variations of my own) and I'm not very keen on using the current implementation where it isn't absolutely necessary.
Best regards,
Darij
comment:8 follow-up: ↓ 9 Changed 7 years ago by
OOPS, I was stupid: With your convention, P.poset()
would not be P.superstandard_tableau().poset()
but rather something like P.tautological_tableau().poset()
, where tautological_tableau()
puts the pair of the coordinates of each cell into that cell (another function that probably needs to be made). For this method to generalize to arbitrary tableaux, though, one would have to check that all entries are pairwise distinct, which is a waste of time (OK, so a check
variable?). But to be honest, I'd very much prefer to have this method defined on partitions first and later maybe add it to tableaux as well. If I were to search for it, I would definitely not have started by constructing a tableau out of p
...
comment:9 in reply to: ↑ 8 Changed 7 years ago by
Hi Darij,
I think Nicolas' point is that it is more natural to define posets associated to tableaux than partitions. The partition poset that you implemented could then be easily obtained from that. You could use
sage: t = Tableau([[1,2,3],[4,5,6],[7]]) sage: t.cells_containing(1) [(0, 0)]
to label the cells by their coordinates. In Sage we should have general purpose methods rather than very specific methods. If I understand correctly, this is his point!
Anne
PS: I do not understand your comment that all entries are pairwise distinct. Cells inside a tableau/partition are always all distinct.
comment:10 Changed 7 years ago by
Hi Anne,
The way I understand Nicolas, the poset would be labelled by the *entries* of the tableau, not by the *cells* of the tableau. So the entries would have to be distinct (and hashable). I still think that refactoring the method through a poset
method in Tableaux
would be unnatural. On the other hand, I'm not against *adding* an (independent) poset
method in Tableaux
, once the latter class has been revamped.
Greets,\ Darij
comment:11 Changed 7 years ago by
Ok, I had missed the fact that the poset you created was indexed by the cells (i,j). That's a reasonable reason to put at least a shorthand in partition.
I let you chose the final design and timeline (for this ticket or later) for the best, knowing that:
- Having a method on standard fillings that build the poset would be generally useful
- Having a method on partitions building a standard filling containing the coordinates of the cells could be useful elsewhere.
- The cost of checking that all entries of a filling are distinct and hashable is really negligible compared to that of building a poset.
- I for myself would not have looked for such a method in Partition in the first place :-)
- The name "poset", for a partition, is not explicit enough. I would need to read the documentation to know which poset this is about.
Cheers,
comment:12 Changed 7 years ago by
I guess my takeaway is then to add similar methods to Tableaux
once the class is in less of a disarray.
About the name: What do you think about cell_poset
? I fear there is no standard name in literature...
comment:13 Changed 7 years ago by
The same name just came out independently in my head. So it's probably not too bad :-)
comment:14 Changed 7 years ago by
Btw:
- The code to build the covers in the poset is not DRY. The duplication could be removed by having two little helper functions to index the rows and columns
- Instead one option with four values for the input, there could possibly be two options, one for the vertical orientation, one for the horizontal orientation. I have no great idea for the name of those options though.
- Please put as first example the default value which shows that this is using the usual indexing of the rows and columns of a tableau.
Thanks!
comment:15 Changed 7 years ago by
- Status changed from positive_review to needs_work
OK, tomorrow. Setting to needs_work for now. Thanks for the careful look at the code!
comment:16 follow-up: ↓ 17 Changed 7 years ago by
I've renamed the methods and made the standard orientation the first example.
About the DRYness, what exactly would you factor out? What do you mean by "indexing" rows and columns?
About the orientation
keyword, I can replace it by two booleans left_is_bigger
and top_is_bigger
. What do you think about it? (Haven't done this change so far.)
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 7 years ago by
Replying to darij:
I've renamed the methods and made the standard orientation the first example.
Thanks. Maybe you could use SE rather than NW as well in the documentation when you explain what the poset is about.
About the DRYness, what exactly would you factor out? What do you mean by "indexing" rows and columns?
Oh, now I see the misunderstanding; I thought the option was about the indexing of the cells, ... Which indeed was stupid (same poset). Never mind.
To make your code DRY, you could build two lists horizontal_covers and vertical_covers, then, depending on the options, map a reverse on them:
if ...: horizontal_covers = [ (j,i) for (i,j) in horizontal_covers ] if ...: vertical_covers = [ (j,i) for (i,j) in vertical_covers ]
About the
orientation
keyword, I can replace it by two booleansleft_is_bigger
andtop_is_bigger
. What do you think about it? (Haven't done this change so far.)
For consistency, I would tend to favor non boolean options like horiz="left" / "right" (we have a bunch of them e.g. in the Coxeter code). But I don't have great suggestions for the option names themselves.
Cheers,
Nicolas
comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 7 years ago by
Replying to nthiery:
Thanks. Maybe you could use SE rather than NW as well in the documentation when you explain what the poset is about.
Will do next time I'm editing the file; good point!
About the DRYness, what exactly would you factor out? What do you mean by "indexing" rows and columns?
Oh, now I see the misunderstanding; I thought the option was about the indexing of the cells, ... Which indeed was stupid (same poset). Never mind.
To make your code DRY, you could build two lists horizontal_covers and vertical_covers, then, depending on the options, map a reverse on them:
if ...: horizontal_covers = [ (j,i) for (i,j) in horizontal_covers ] if ...: vertical_covers = [ (j,i) for (i,j) in vertical_covers ]
Hmm. TBH I still don't understand you. How do you get anything from reversal? I'm building up a dictionary, not a list of cover relations. The (arguably toy) timing I have done shows the dictionary to be faster:
sage: %timeit Poset({1: [2,3], 2: [4,5], 5: [6,7,8]}) 1000 loops, best of 3: 1.31 ms per loop sage: %timeit Poset([[1,2],[1,3],[2,4],[2,5],[5,6],[5,7],[5,8]]) 100 loops, best of 3: 1.9 ms per loop
For consistency, I would tend to favor non boolean options like horiz="left" / "right" (we have a bunch of them e.g. in the Coxeter code). But I don't have great suggestions for the option names themselves.
Hmm. I thought you wanted to get rid of strings as arguments. I'm not really convinced of replacing a 2-letter string by 2 multiletter strings :/
comment:19 in reply to: ↑ 18 Changed 7 years ago by
Hi Darij,
Replying to darij:
Hmm. TBH I still don't understand you. How do you get anything from reversal? I'm building up a dictionary, not a list of cover relations. The (arguably toy) timing I have done shows the dictionary to be faster:
sage: %timeit Poset({1: [2,3], 2: [4,5], 5: [6,7,8]}) 1000 loops, best of 3: 1.31 ms per loop sage: %timeit Poset([[1,2],[1,3],[2,4],[2,5],[5,6],[5,7],[5,8]]) 100 loops, best of 3: 1.9 ms per loop
I'd say: too early of an optimization. Especially since the above timing is actually pretty ridiculous: wtf, 1 ms to build a trivial poset? I very much hope this will be improved a lot in the future; but that's a different story. Btw: %timeit is does not measure things well for objects with unique representation, or in general whenever there is a cache involved.
At this point, just focus on expressive and duplication free code. Use covers if it's easier. I know you can find a solution :-)
For consistency, I would tend to favor non boolean options like horiz="left" / "right" (we have a bunch of them e.g. in the Coxeter code). But I don't have great suggestions for the option names themselves.
Hmm. I thought you wanted to get rid of strings as arguments. I'm not really convinced of replacing a 2-letter string by 2 multiletter strings :/
I agree. My point was more about separation of concerns (up/down, left/right). In any cases, there is no clear cut solution and I just meant to hint at possible directions. I let you take the final judgment call!
Cheers,
Nicolas
comment:20 follow-up: ↓ 21 Changed 7 years ago by
I've replaced NW by SE in the doc.
About %timeit not seeing the advantages of UniqueRepresentation?: I kind of expected it, but I don't really know how to measure the timing right (I asked something similar on sage-devel a week ago). Maybe this:
sage: %timeit [Poset({1: [2,3], 2: [4,5], 5: [6,7,8]}) for i in range(12)] 1 loops, best of 3: 15.5 ms per loop sage: %timeit [Poset([[1,2],[1,3],[2,4],[2,5],[5,6],[5,7],[5,8]]) for i in range(12)] 10 loops, best of 3: 21.2 ms per loop
I think that even when we speed up Poset.__init__
-- *particularly* when we speed it up -- the difference between a dictionary and a list input will become more noticeable. I'm pretty sure that the dictionary is the form that makes it easier to compute the poset because lookup is faster. Or not?
I don't think that separating the orientation
variable is really separation of concerns -- there is much more similarities between SE and NW than between SE and NE (for example).
comment:21 in reply to: ↑ 20 Changed 7 years ago by
Replying to darij:
I've replaced NW by SE in the doc.
Thanks!
About %timeit not seeing the advantages of UniqueRepresentation?: I kind of expected it, but I don't really know how to measure the timing right (I asked something similar on sage-devel a week ago). Maybe this:
sage: %timeit [Poset({1: [2,3], 2: [4,5], 5: [6,7,8]}) for i in range(12)] 1 loops, best of 3: 15.5 ms per loop sage: %timeit [Poset([[1,2],[1,3],[2,4],[2,5],[5,6],[5,7],[5,8]]) for i in range(12)] 10 loops, best of 3: 21.2 ms per loopI think that even when we speed up
Poset.__init__
-- *particularly* when we speed it up -- the difference between a dictionary and a list input will become more noticeable. I'm pretty sure that the dictionary is the form that makes it easier to compute the poset because lookup is faster. Or not?q
The conversion from a list to a dictionary is orders of magnitude faster than the creation of a poset:
sage: l = [[1,2],[1,3],[2,4],[2,5],[5,6],[5,7],[5,8]] sage: %timeit dict(l) 100000 loops, best of 3: 3.76 us per loop
So, don't worry about this at this point.
I don't think that separating the
orientation
variable is really separation of concerns -- there is much more similarities between SE and NW than between SE and NE (for example).
Fair enough :-)
Cheers,
Nicolas
comment:22 Changed 7 years ago by
Can anyone remind me what needs to be done here after all the discussion? Sorry, time flies...
comment:23 Changed 7 years ago by
I think all that's left is to convert this to a branch and do a final review...
comment:24 Changed 7 years ago by
OK -- since this needs review, I've thrown in one more minor commit. (The old one is unchanged apart from the commit message.) Nicolas' tableaux suggestion is now #15598. I haven't simplifies the implementation of the cell_poset
method since I still feel that Poset.__call__
is going to be optimized one day and the situation will noticeably change then, but I'm open to argument on this.
comment:25 Changed 7 years ago by
- Branch set to public/combinat/partitions_posets
- Commit set to b36286fef9ed6cc9f0b01dce6208add4b3acac0d
- Status changed from needs_work to needs_review
comment:26 Changed 7 years ago by
- Status changed from needs_review to positive_review
Looks good to me.
comment:27 Changed 7 years ago by
Thank you once again!
(And sorry for my reviewing inactivity lately...)
comment:28 Changed 7 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:29 Changed 7 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
Wrong formatting in docstrings fixed; thanks Nathan!