Opened 6 years ago

Closed 6 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) Commit: b36286fef9ed6cc9f0b01dce6208add4b3acac0d
Dependencies: #15350 Stopgaps:

Description (last modified by darij)

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)

trac_15428-partition-posets-dg.patch (14.8 KB) - added by darij 6 years ago.
updated version

Download all attachments as: .zip

Change History (30)

comment:1 Changed 6 years ago by darij

  • Authors set to Darij Grinberg
  • Cc sage-combinat tscrim aschilling ncohen added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 6 years ago by darij

Wrong formatting in docstrings fixed; thanks Nathan!

comment:3 Changed 6 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Looks good to me. Thanks.

comment:4 Changed 6 years ago by jdemeyer

  • 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 6 years ago by darij

  • 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 6 years ago by nthiery

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 6 years ago by darij

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: Changed 6 years ago by darij

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 6 years ago by aschilling

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 6 years ago by darij

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 6 years ago by nthiery

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 6 years ago by darij

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 6 years ago by nthiery

The same name just came out independently in my head. So it's probably not too bad :-)

comment:14 Changed 6 years ago by nthiery

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 6 years ago by darij

  • 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: Changed 6 years ago by darij

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: Changed 6 years ago by nthiery

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 booleans left_is_bigger and top_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: Changed 6 years ago by darij

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!

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 :/

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

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

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

Changed 6 years ago by darij

updated version

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

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 6 years ago by nthiery

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 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?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 6 years ago by darij

Can anyone remind me what needs to be done here after all the discussion? Sorry, time flies...

comment:23 Changed 6 years ago by tscrim

I think all that's left is to convert this to a branch and do a final review...

comment:24 Changed 6 years ago by darij

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 6 years ago by darij

  • Branch set to public/combinat/partitions_posets
  • Commit set to b36286fef9ed6cc9f0b01dce6208add4b3acac0d
  • Status changed from needs_work to needs_review

New commits:

b36286fmostly trivial doc fixes on partition.py
6812b87trac #15428: cell_poset methods on partitions and skew partitions

comment:26 Changed 6 years ago by tscrim

  • Status changed from needs_review to positive_review

Looks good to me.

comment:27 Changed 6 years ago by darij

Thank you once again!

(And sorry for my reviewing inactivity lately...)

comment:28 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:29 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.