Opened 6 months ago
Closed 4 months ago
#15313 closed defect (fixed)
is_linear_extension on posets is rather liberal
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.1 |
Component: | combinatorics | Keywords: | posets, combinat |
Cc: | ncohen, sage-combinat | Merged in: | |
Authors: | Nathann Cohen | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/ncohen/15313 (Commits) | Commit: | b71faad7ac78cbb883f3d5ee7e7dca7a25c45ad8 |
Dependencies: | Stopgaps: |
Description
sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True) sage: list(P) [1, 2, 3, 4, 6, 12] sage: P.is_linear_extension([1,2,4,3,6,12,1337]) True sage: P.is_linear_extension([1,2,4,3,6,666,12,1337]) True
At the moment I am not planning to do anything about it, since it would probably involving seeing what other parts of the code using is_linear_extension and how they are using (my bets that this error doesn't cause any other problems in the code, and fixing it would likely incur some speed penalty so one should keep the old functionality accessible).
Change History (9)
comment:1 Changed 6 months ago by ncohen
- Branch set to u/ncohen/15313
- Status changed from new to needs_review
comment:2 Changed 6 months ago by git
- Commit set to 9e4cef1925c5294c33601227bf65a6486b03b50d
Branch pushed to git repo; I updated commit sha1. New commits:
9e4cef1 | is_linear_extension on posets is rather liberal |
comment:3 Changed 6 months ago by darij
Good fix, but sage/combinat/posets/linear_extension.py still is trying to work around this bug:
def __contains__(self, obj): """ Membership testing EXAMPLES:: sage: P = Poset((divisors(12), attrcall("divides")), facade=True, linear_extension=True) sage: P.list() [1, 2, 3, 4, 6, 12] sage: L = P.linear_extensions() sage: L([1, 2, 4, 3, 6, 12]) in L True sage: [1, 2, 4, 3, 6, 12] in L False sage: L = P.linear_extensions(facade=True) sage: [1, 2, 4, 3, 6, 12] in L True sage: [1, 3, 2, 6, 4, 12] in L True sage: [1, 3, 6, 2, 4, 12] in L False sage: [p for p in Permutations(list(P)) if list(p) in L] [[1, 2, 3, 4, 6, 12], [1, 2, 3, 6, 4, 12], [1, 2, 4, 3, 6, 12], [1, 3, 2, 4, 6, 12], [1, 3, 2, 6, 4, 12]] """ if not self._is_facade: return super(LinearExtensionsOfPoset, self).__contains__(obj) return \ isinstance(obj, (list, tuple)) and \ len(obj) == len(self.poset()) and \ set(obj) == set(self.poset()) and \ self.poset().is_linear_extension(obj)
This could be now optimized.
comment:4 Changed 6 months ago by ncohen
Love those guys who fix a bug somewhere knowing the other function stays wrong....
Nathann
comment:5 Changed 6 months ago by git
- Commit changed from 9e4cef1925c5294c33601227bf65a6486b03b50d to b71faad7ac78cbb883f3d5ee7e7dca7a25c45ad8
Branch pushed to git repo; I updated commit sha1. New commits:
b71faad | is_linear_extension on posets is rather liberal : updating linear_extensions.py |
comment:6 Changed 6 months ago by darij
- Status changed from needs_review to positive_review
Supposing that you have run the doctests, setting this to positive review. Thanks for fixing!
comment:7 Changed 6 months ago by jdemeyer
- Milestone changed from sage-5.13 to sage-6.0
comment:8 Changed 4 months ago by vbraun_spam
- Milestone changed from sage-6.0 to sage-6.1
comment:9 Changed 4 months ago by vbraun
- Resolution set to fixed
- Status changed from positive_review to closed
I think that's enough... And not too bad from the complexity point of view :-)
Nathann