Opened 4 years ago

Closed 4 years ago

#24639 closed enhancement (fixed)

Enumerating greedy linear extensions

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-8.2
Component: combinatorics Keywords:
Cc: kdilks, chapoton, tscrim Merged in:
Authors: Jori Mäntysalo Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 6db34e4 (Commits, GitHub, GitLab) Commit: 6db34e48fca477d03b80bb820987f5542359eee6
Dependencies: Stopgaps:

Status badges

Description

Add function to iterate over all greedy and supergreedy (also called depth-first-search) linear extensions of a poset.

Change History (18)

comment:1 Changed 4 years ago by jmantysalo

  • Authors set to kdilks, chapoton, tscrim
  • Status changed from new to needs_info

I would like to add function(s) to iterate over all greedy and super-greedy linear extensions of a poset. What is a reasonable interface? Currently linear_extensions() returns an object of a specific type, but for example tau() of a greedy linear extension is not necessarily greedy.

comment:2 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/enumerating_greedy_linear_extensions

comment:3 Changed 4 years ago by jmantysalo

  • Commit set to b93ba19f800d2328088733dc9ec5d16ea07dfc07

Code added, interface missing.


New commits:

b93ba19Add iterator over greedy linear extensions.

comment:4 Changed 4 years ago by git

  • Commit changed from b93ba19f800d2328088733dc9ec5d16ea07dfc07 to f7e27b888a4e3bc6cfe9f879e52f4ed23db9da9a

Branch pushed to git repo; I updated commit sha1. New commits:

f7e27b8A correction.

comment:5 follow-up: Changed 4 years ago by tscrim

  • Authors kdilks, chapoton, tscrim deleted
  • Cc kdilks chapoton tscrim added

I would probably subclass the linear extension classes and have P.linear_extensions() take a (super)greedy argument.

comment:6 Changed 4 years ago by git

  • Commit changed from f7e27b888a4e3bc6cfe9f879e52f4ed23db9da9a to 67c987924cffff9b416cf5ced05a8b682b0037bc

Branch pushed to git repo; I updated commit sha1. New commits:

67c9879Add supergreedy extensions.

comment:7 in reply to: ↑ 5 ; follow-up: Changed 4 years ago by jmantysalo

Replying to tscrim:

I would probably subclass the linear extension classes and have P.linear_extensions() take a (super)greedy argument.

But what to do for .tau() then?

comment:8 follow-up: Changed 4 years ago by jmantysalo

  • Authors set to Jori Mäntysalo
  • Status changed from needs_info to needs_review

Meanwhile I mark this as needs_review: this does not affect "interface", i.e. posets.py at all. Interface can be thinked independently.

comment:9 in reply to: ↑ 7 Changed 4 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

I would probably subclass the linear extension classes and have P.linear_extensions() take a (super)greedy argument.

But what to do for .tau() then?

Have it return something in the general linear extension class (a lá Tableau and its subclasses).

comment:10 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by tscrim

Replying to jmantysalo:

Meanwhile I mark this as needs_review: this does not affect "interface", i.e. posets.py at all. Interface can be thinked independently.

It is simple enough to change this later on too. While it made me laugh, we should be a bit more professional than i_want_python_3 as a variable name.

comment:11 Changed 4 years ago by git

  • Commit changed from 67c987924cffff9b416cf5ced05a8b682b0037bc to 6db34e48fca477d03b80bb820987f5542359eee6

Branch pushed to git repo; I updated commit sha1. New commits:

6db34e4Unfunnying variable name.

comment:12 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by jmantysalo

  • Milestone changed from sage-wishlist to sage-8.2

Replying to tscrim:

While it made me laugh, we should be a bit more professional than i_want_python_3 as a variable name.

Changed that. (But for example orthocomplementations_iterator has same kind of variable name.)

comment:13 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by tscrim

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

Replying to jmantysalo:

Replying to tscrim:

While it made me laugh, we should be a bit more professional than i_want_python_3 as a variable name.

Changed that. (But for example orthocomplementations_iterator has same kind of variable name.)

I don't think I reviewed that. Although that has something worse: raising a StopIteration (at least, IIRC this to be a bad thing and instead you should just return).

Anyways, thank you. Positive review.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 4 years ago by jmantysalo

Replying to tscrim:

Thanks for review.

Although that has something worse: raising a StopIteration (at least, IIRC this to be a bad thing and instead you should just return).

Can be no yield and return in the same function.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 4 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

Thanks for review.

No problem.

Although that has something worse: raising a StopIteration (at least, IIRC this to be a bad thing and instead you should just return).

Can be no yield and return in the same function.

Void returns are okay, you just cannot return any object. Addendum: For example, see sage.combinat.partitions.RegularPartitions_all.__iter__.

Last edited 4 years ago by tscrim (previous) (diff)

comment:16 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by jmantysalo

Replying to tscrim:

Can be no yield and return in the same function.

Void returns are okay, you just cannot return any object.

OK, I did not know that. It is at least shorter to write just return, althought I did not find a reference to prefer it instead of raise StopIteration.

comment:17 in reply to: ↑ 16 Changed 4 years ago by tscrim

Replying to jmantysalo:

Replying to tscrim:

Can be no yield and return in the same function.

Void returns are okay, you just cannot return any object.

OK, I did not know that. It is at least shorter to write just return, althought I did not find a reference to prefer it instead of raise StopIteration.

It is gone after Python 3.5.2: https://www.python.org/dev/peps/pep-0479/

See also: https://stackoverflow.com/questions/14183803/what-is-the-difference-between-raise-stopiteration-and-a-return-statement-in-gen

Last edited 4 years ago by tscrim (previous) (diff)

comment:18 Changed 4 years ago by vbraun

  • Branch changed from u/jmantysalo/enumerating_greedy_linear_extensions to 6db34e48fca477d03b80bb820987f5542359eee6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.