#15313: is_linear_extension on posets is rather liberal
-------------------------+-------------------------------------------------
Reporter: darij | Owner:
Type: | Status: needs_review
defect | Milestone: sage-5.13
Priority: minor | Resolution:
Component: | Merged in:
combinatorics | Reviewers:
Keywords: | Work issues:
posets, combinat | Commit:
Authors: | 9e4cef1925c5294c33601227bf65a6486b03b50d
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/15313 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (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.
--
Ticket URL: <http://trac.sagemath.org/ticket/15313#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
