is_linear_extension on posets is rather liberal

[darij]

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).

[ncohen]

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

Nathann

[git]

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

[changeset:9e4cef1]

is_linear_extension on posets is rather liberal

[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.

[ncohen]

Love those guys who fix a bug somewhere knowing the other function stays wrong....

Nathann

[git]

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

[darij]

Supposing that you have run the doctests, setting this to positive review. Thanks for fixing!