Partitions to posets

[darijgr]

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

Depends on #15350

CC: @sagetrac-sage-combinat @tscrim @anneschilling @nathanncohen

Component: combinatorics

Keywords: sage-combinat, partition, poset

Author: Darij Grinberg

Branch/Commit: public/combinat/partitions_posets @ b36286f

Reviewer: Travis Scrimshaw

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

[darijgr]

Author: Darij Grinberg

[darijgr]

comment:2

Wrong formatting in docstrings fixed; thanks Nathan!

[tscrim]

comment:3

Looks good to me. Thanks.

[tscrim]

Reviewer: Travis Scrimshaw

[jdemeyer]

comment:4

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.

[darijgr]

comment:5

Thanks for spotting this one! It's weird: apparently sphinx doesn't like
the `5`th element
(but
the `5`-th element
works fine).

[nthiery]

comment:6

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

[darijgr]

comment:7

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

[darijgr]

comment:8

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

[anneschilling]

comment:9

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.

[darijgr]

comment:10

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

[nthiery]

comment:11

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,

[darijgr]

comment:12

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

[nthiery]

comment:13

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

[nthiery]

comment:14

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!

[darijgr]

comment:15

OK, tomorrow. Setting to needs_work for now. Thanks for the careful look at the code!

[darijgr]

comment:16

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

[nthiery]

comment:17

Replying to @darijgr:

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

[darijgr]

comment:18

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

[nthiery]

comment:19

Hi Darij,

Replying to @darijgr:

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

[darijgr]

updated version

[darijgr]

comment:20

Attachment: trac_15428-partition-posets-dg.patch.gz

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

[nthiery]

comment:21

Replying to @darijgr:

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

[darijgr]

comment:22

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

[tscrim]

comment:23

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

[darijgr]

comment:24

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.

[darijgr]

Commit: b36286f

[darijgr]

New commits:

b36286f	mostly trivial doc fixes on partition.py
6812b87	trac #15428: cell_poset methods on partitions and skew partitions

[darijgr]

Branch: public/combinat/partitions_posets

[tscrim]

comment:26

Looks good to me.

[darijgr]

comment:27

Thank you once again!

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