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

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/15313
  • Status changed from new to needs_review

I think that's enough... And not too bad from the complexity point of view :-)

Nathann

comment:2 Changed 6 months ago by git

  • Commit set to 9e4cef1925c5294c33601227bf65a6486b03b50d

Branch pushed to git repo; I updated commit sha1. New commits:

9e4cef1is_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:

b71faadis_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
Note: See TracTickets for help on using tickets.