Opened 5 years ago
Closed 5 years ago
#24639 closed enhancement (fixed)
Enumerating greedy linear extensions
Reported by:  jmantysalo  Owned by:  

Priority:  major  Milestone:  sage8.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: 
Description
Add function to iterate over all greedy and supergreedy (also called depthfirstsearch) linear extensions of a poset.
Change History (18)
comment:1 Changed 5 years ago by
 Status changed from new to needs_info
comment:2 Changed 5 years ago by
 Branch set to u/jmantysalo/enumerating_greedy_linear_extensions
comment:3 Changed 5 years ago by
 Commit set to b93ba19f800d2328088733dc9ec5d16ea07dfc07
comment:4 Changed 5 years ago by
 Commit changed from b93ba19f800d2328088733dc9ec5d16ea07dfc07 to f7e27b888a4e3bc6cfe9f879e52f4ed23db9da9a
Branch pushed to git repo; I updated commit sha1. New commits:
f7e27b8  A correction.

comment:5 followup: ↓ 7 Changed 5 years ago by
 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 5 years ago by
 Commit changed from f7e27b888a4e3bc6cfe9f879e52f4ed23db9da9a to 67c987924cffff9b416cf5ced05a8b682b0037bc
Branch pushed to git repo; I updated commit sha1. New commits:
67c9879  Add supergreedy extensions.

comment:7 in reply to: ↑ 5 ; followup: ↓ 9 Changed 5 years ago by
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 followup: ↓ 10 Changed 5 years ago by
 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 5 years ago by
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 ; followup: ↓ 12 Changed 5 years ago by
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 5 years ago by
 Commit changed from 67c987924cffff9b416cf5ced05a8b682b0037bc to 6db34e48fca477d03b80bb820987f5542359eee6
Branch pushed to git repo; I updated commit sha1. New commits:
6db34e4  Unfunnying variable name.

comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 5 years ago by
 Milestone changed from sagewishlist to sage8.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 ; followup: ↓ 14 Changed 5 years ago by
 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 ; followup: ↓ 15 Changed 5 years ago by
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 justreturn
).
Can be no yield
and return
in the same function.
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 5 years ago by
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 justreturn
).Can be no
yield
andreturn
in the same function.
Void returns are okay, you just cannot return any object. Addendum: For example, see sage.combinat.partitions.RegularPartitions_all.__iter__
.
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 5 years ago by
Replying to tscrim:
Can be no
yield
andreturn
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 5 years ago by
Replying to jmantysalo:
Replying to tscrim:
Can be no
yield
andreturn
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 ofraise StopIteration
.
It is gone in Python 3.5: https://www.python.org/dev/peps/pep0479/
comment:18 Changed 5 years ago by
 Branch changed from u/jmantysalo/enumerating_greedy_linear_extensions to 6db34e48fca477d03b80bb820987f5542359eee6
 Resolution set to fixed
 Status changed from positive_review to closed
I would like to add function(s) to iterate over all greedy and supergreedy linear extensions of a poset. What is a reasonable interface? Currently
linear_extensions()
returns an object of a specific type, but for exampletau()
of a greedy linear extension is not necessarily greedy.