Opened 6 years ago

Closed 6 years ago

#15283 closed enhancement (fixed)

Rowmotion and Panyushev orbits: iterators for orbits and better doc

Reported by: darij Owned by:
Priority: major Milestone: sage-5.13
Component: combinatorics Keywords: posets, rowmotion, sage-combinat, panyushev, order-ideals, categories
Cc: jessicapalencia, sage-combinat, tscrim, aschilling Merged in: sage-5.13.beta2
Authors: Darij Grinberg Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by darij)

This patch adds documentation to some rowmotion-related methods in sage/categories/posets.py and sage/categories/finite_posets.py and introduces new methods which return iterators over single rowmotion / Panyushev complementation / toggle orbits instead of computing *all* orbits at once and returning them as lists. This allows experimenting with big posets (at least if one can find a way to more or less randomly sample order ideals or antichains).

Apply:

Attachments (3)

trac_15283-rowmotion-dg.patch (27.3 KB) - added by darij 6 years ago.
revised version
newdiff.txt (2.5 KB) - added by darij 6 years ago.
differences to the old file. don't apply, just read
trac_15283-additions-dg.patch (6.6 KB) - added by darij 6 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 6 years ago by darij

  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooooooooooooooooo !!

I read this patch and even though I am not from the field I feel that it could get in. I only have some small remarks to make :

  • Could the Poset class need a .is_antichain(vertices=[...]) method to check if this set of vertices induces an antichain ? You have a .is_chain() method, but it does not take any argument.
  • ``panyushev_complement`` should be :meth:`panyushev_complement`
  • isn't "generated by the antichain antichain, represented by its generating antichain" slightly redundant ? :-P
  • With my first reading, I understood toggling_orbit_iter would take a set and a list of points, and return the toggle of the set with the first point, then this new set toggled with the second point, then this new set with the third point, ... I does not make much sense it is true, especially with stop=True, but if you think somebody from the field could make the same mistake perhaps it could be made clearer :-)

Nathann

comment:3 in reply to: ↑ 2 ; follow-up: Changed 6 years ago by darij

Hi Nathannnnn and thanks for the comments!

Replying to ncohen:

  • Could the Poset class need a .is_antichain(vertices=[...]) method to check if this set of vertices induces an antichain ? You have a .is_chain() method, but it does not take any argument.

Probably, but I am not sure about adding such methods. .is_chain would have to then be given two meanings, which people might not be happy about.

  • ``panyushev_complement`` should be :meth:`panyushev_complement`

Done.

  • isn't "generated by the antichain antichain, represented by its generating antichain" slightly redundant ? :-P

I think I've improved this sentence now.

  • With my first reading, I understood toggling_orbit_iter would take a set and a list of points, and return the toggle of the set with the first point, then this new set toggled with the second point, then this new set with the third point, ... I does not make much sense it is true, especially with stop=True, but if you think somebody from the field could make the same mistake perhaps it could be made clearer :-)

Good point -- added a warning!

Since I forgot to qnew, I've made the changes in my old patch rather than adding a new patch. I hope this is fine, and I'll just update the old patch and upload the new changes as a txt file.

Changed 6 years ago by darij

revised version

Changed 6 years ago by darij

differences to the old file. don't apply, just read

comment:4 Changed 6 years ago by darij

  • Status changed from needs_work to needs_review

comment:5 in reply to: ↑ 3 Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

Yoooooooooo !

Probably, but I am not sure about adding such methods. .is_chain would have to then be given two meanings, which people might not be happy about.

Well, the meaning of is_chain stays the same when used without argument, and a feature is added. Better than creating a is_chain_subset method to do the very same, and if people often check whether a set is a chain or an antichain, it can be useful.

Since I forgot to qnew, I've made the changes in my old patch rather than adding a new patch. I hope this is fine, and I'll just update the old patch and upload the new changes as a txt file.

No prob ! Good to go ;-)

Nathann

comment:6 Changed 6 years ago by darij

The other problem is that it's not clear whether [6, 3] should be a chain of the poset divisors(6) with divisibility order. Sometimes chains defined as comparable subsets (hence yes), sometimes as actual ordered lists (then no). I fear this method will be harder to use than to rewrite for most users...

comment:7 Changed 6 years ago by ncohen

Right. Now that I think of it, though, it can be implemented better :

  • Check that an ordered list is indeed a chain : only n-1 comparisons
  • Check that a set is indeed a chain : quicksort using n log(n) comparisons, then check if the (ordered) result makes sense with n-1 comparisons.

Anyway, if this function is useful at some point it can still be implemented in a .is_chain method with a vertices=[...] argument (possibly equal to None to mean "self") and a ordered=True parameter for this second problem :-D

Nathann

Changed 6 years ago by darij

comment:8 Changed 6 years ago by darij

Hi Nathann,

I've uploaded an additional patch for this. It disappointingly required some __cmp__ hackery, so please check it and tell me if that could have been done in a nicer way.

Best regards,
Darij

comment:9 Changed 6 years ago by ncohen

Hellooooo again !

Hmmmm... I don't get why you needed this hack, actually. What's wrong with the following ?

sorted_o = sorted(o, cmp=self.lt)

If the set is a chain then it behaves exactly as a quicksort, and otherwise .lt will answer "no" from time to time -- but who cares, you will find this out in the terminal check :

all(self.lt(x[i],x[i+1]) for i in range(len(o))-1)

And I still believe that this would be better in side of Poset.is_chain() :-P

Aaaaaaand Nicolas did not think that it would be a problem but well... That's up to you :-P

Have fuuuuuuuuuuuuuuuuuuuuuun !

Nathann

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

I don't think self.lt returns the right format for sorted. It seems that the cmp keyword of sorted wants a total -1,0,1-valued function, not a boolean one. See how this prints the same list twice:

P = Poset({i: divisors(i) for i in divisors(24)})
print sorted(list(P), cmp=P.lt)
print sorted(list(P), cmp=P.gt)

And either way, I don't know how sorted would react if cmp fails to be antisymmetric, i. e., if there are two distinct elements which compare as equal or each smaller than the other. I'd hope the result would still be sorted, but who knows? Why is there no good doc for sorted??

I originally wanted to implement these functions as semantics for is_chain and is_antichain, but found that this would make the docstring rather confusing.

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

comment:11 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_info

Which patch(es) should be applied? Please check that the patches apply to sage-5.13.beta1.

comment:12 Changed 6 years ago by ncohen

I don't think self.lt returns the right format for sorted. It seems that the cmp keyword of sorted wants a total -1,0,1-valued function, not a boolean one.

Well. If you insist on that, I can make it lambda x,y : 2*self.lt(x,y)-1 :-P

I originally wanted to implement these functions as semantics for is_chain and is_antichain, but found that this would make the docstring rather confusing.

Really ? What do you think of this ?

def is_chain(verts=None):
    Checks whether the Poset (or a specific subset of it) is a chain

    INPUT:

    - ``verts`` (list of vertices) -- If ``verts`` is ``None`` (default),
      the function returns ``True`` if and only if the poset is a chain.
      If ``verts`` is a list of points, the function returns ``True`` if 
      and only if ``verts`` is a chain of the poset.

    - ``ordered`` (boolean) -- Whether to consider ``verts`` as a list, 
      or as a set. If ``ordered`` is set to ``True`` (default), only 
      checks whether the vertices of ``verts`` are totally ordered in 
      the poset. If ``ordered`` is set to ``False`` (default), checks 
      whether these vertices are totally ordered with the ordering 
      given by the list ``verts``

Nathann

comment:13 Changed 6 years ago by ncohen

Jeroen : the only patch that should be applied is trac_15283-rowmotion-dg.patch. The other one is about additional modifications that could be made on another ticket.

Nathann

comment:14 Changed 6 years ago by darij

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

Oops, I didn't notice that this was positive_review. Thanks, Nathann! In view of the changes, needs_review is probably more appropriate now.

@Jeroen: sorry, I can't tell about beta1, but they do apply on 5.13beta0.

for the patchbots:

apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch​

for the patchbot:

apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch​

for the patchbots

apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch​

for the patchbot

apply trac_15283-rowmotion-dg.patch trac_15283-additions-dg.patch​

(because I can't remember which syntax is correct).

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

comment:15 Changed 6 years ago by darij

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

OK, Nathann is right, this ticket should be split:

for the patchbots:

apply trac_15283-rowmotion-dg.patch

for the patchbot:

apply trac_15283-rowmotion-dg.patch

for the patchbots

apply trac_15283-rowmotion-dg.patch

for the patchbot

apply trac_15283-rowmotion-dg.patch

This can then be set to positive_review since Nathann did review the rowmotion patch.

comment:16 in reply to: ↑ 10 Changed 6 years ago by nbruin

Replying to darij:

I don't think self.lt returns the right format for sorted. It seems that the cmp keyword of sorted wants a total -1,0,1-valued function, not a boolean one. See how this prints the same list twice:

P = Poset({i: divisors(i) for i in divisors(24)})
print sorted(list(P), cmp=P.lt)
print sorted(list(P), cmp=P.gt)

The recommended way is to use sorted(...,key=...) where key should map the sequence elements into a totally ordered set (for instance, the integers). This provides a concise way of the decorate-sort-undecorate pattern, or Schwartzian transform, which is generally more efficient than sorting with a likely expensive custom sort function.

The cmp keyword is actually removed in Python 3. See functools.cmp_to_key to convert a legitimate cmp function into a value suitable for key.

comment:17 Changed 6 years ago by darij

Thanks, Nathann and Nils, for your comments. I've decided to provide two implementations for is_chain, one using sorting when the poset is finite (in which case, as Nils suggests, I'll use a key attribute), one by checking all pairs of possible relations when the poset is not assumed finite.

I'm still reluctant to make this part of the existing is_chain method. One reason is that the existing is_chain exists only for finite posets, so I'd have to move it from sage/combinat/posets.py to sage/categories/posets.py and give it some stupid error behavior when the poset is not finite.

I'm carrying this over into a new ticket: #15322. Please disregard the additions-dg.patch I posted here, as it is buggy.

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

comment:18 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.13.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.