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: |
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
- Status changed from new to needs_info
comment:2 Changed 4 years ago by
- Branch set to u/jmantysalo/enumerating_greedy_linear_extensions
comment:3 Changed 4 years ago by
- Commit set to b93ba19f800d2328088733dc9ec5d16ea07dfc07
comment:4 Changed 4 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 follow-up: ↓ 7 Changed 4 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 4 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 ; follow-up: ↓ 9 Changed 4 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 follow-up: ↓ 10 Changed 4 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 4 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 ; follow-up: ↓ 12 Changed 4 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 4 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 ; follow-up: ↓ 13 Changed 4 years ago by
- 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: ↓ 14 Changed 4 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 ; follow-up: ↓ 15 Changed 4 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 ; follow-up: ↓ 16 Changed 4 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 ; follow-up: ↓ 17 Changed 4 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 4 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 after Python 3.5.2: https://www.python.org/dev/peps/pep-0479/
comment:18 Changed 4 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 super-greedy 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.