Opened 9 years ago
Closed 9 years 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, GitHub, GitLab) | 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 9 years ago by
- Branch set to u/ncohen/15313
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Commit set to 9e4cef1925c5294c33601227bf65a6486b03b50d
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:9e4cef1] | is_linear_extension on posets is rather liberal |
comment:3 Changed 9 years ago by
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 9 years ago by
Love those guys who fix a bug somewhere knowing the other function stays wrong....
Nathann
comment:5 Changed 9 years ago by
- Commit changed from 9e4cef1925c5294c33601227bf65a6486b03b50d to b71faad7ac78cbb883f3d5ee7e7dca7a25c45ad8
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:b71faad] | is_linear_extension on posets is rather liberal : updating linear_extensions.py |
comment:6 Changed 9 years ago by
- 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 9 years ago by
- Milestone changed from sage-5.13 to sage-6.0
comment:8 Changed 9 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:9 Changed 9 years ago by
- 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