Opened 8 years ago
Closed 8 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 )
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)
Change History (21)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 5 Changed 8 years ago by
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.
comment:4 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:5 in reply to: ↑ 3 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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 withn-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 8 years ago by
comment:8 Changed 8 years ago by
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 8 years ago by
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: ↓ 16 Changed 8 years ago by
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.
comment:11 Changed 8 years ago by
- 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 8 years ago by
I don't think
self.lt
returns the right format forsorted
. It seems that thecmp
keyword ofsorted
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
andis_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 8 years ago by
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 8 years ago by
- 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).
comment:15 Changed 8 years ago by
- 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 8 years ago by
Replying to darij:
I don't think
self.lt
returns the right format forsorted
. It seems that thecmp
keyword ofsorted
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 8 years ago by
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.
comment:18 Changed 8 years ago by
- Merged in set to sage-5.13.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
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 :
.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`
antichain
, represented by its generating antichain" slightly redundant ?:-P
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