Opened 9 years ago

Closed 9 years ago

# Rowmotion and Panyushev orbits: iterators for orbits and better doc

Reported by: Owned by: Darij Grinberg major sage-5.13 combinatorics posets, rowmotion, sage-combinat, panyushev, order-ideals, categories Jessica Striker, Sage Combinat CC user, Travis Scrimshaw, Anne Schilling sage-5.13.beta2 Darij Grinberg Nathann Cohen N/A

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:

### comment:1 Changed 9 years ago by Darij Grinberg

Status: new → needs_review

### comment:2 follow-up:  3 Changed 9 years ago by Nathann Cohen

Status: needs_review → 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:  5 Changed 9 years ago by Darij Grinberg

Hi Nathannnnn and thanks for the comments!

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

revised version

### Changed 9 years ago by Darij Grinberg

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

### comment:4 Changed 9 years ago by Darij Grinberg

Status: needs_work → needs_review

### comment:5 in reply to:  3 Changed 9 years ago by Nathann Cohen

Reviewers: → Nathann Cohen needs_review → 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 9 years ago by Darij Grinberg

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 9 years ago by Nathann Cohen

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

### comment:8 Changed 9 years ago by Darij Grinberg

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 9 years ago by Nathann Cohen

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 9 years ago by Darij Grinberg

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 9 years ago by Darij Grinberg (previous) (diff)

### comment:11 Changed 9 years ago by Jeroen Demeyer

Status: positive_review → needs_info

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

### comment:12 Changed 9 years ago by Nathann Cohen

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 9 years ago by Nathann Cohen

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 9 years ago by Darij Grinberg

Description: modified (diff) needs_info → 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:

for the patchbot:

for the patchbots

for the patchbot

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

Last edited 9 years ago by Darij Grinberg (previous) (diff)

### comment:15 Changed 9 years ago by Darij Grinberg

Description: modified (diff) needs_review → 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 9 years ago by Nils Bruin

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 9 years ago by Darij Grinberg

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 9 years ago by Darij Grinberg (previous) (diff)

### comment:18 Changed 9 years ago by Jeroen Demeyer

Merged in: → sage-5.13.beta2 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.