Re: Proposal: s1.intersects(s2)

On Wed, 04 Jul 2007 14:37:34 +0000, Marc 'BlackJack' Rintsch wrote:

On Wed, 04 Jul 2007 09:59:24 -0400, David Abrahams wrote:

Here's an implementation of the functionality I propose, as a
free-standing function:

def intersects(s1,s2):
if len(s1) < len(s2):
for x in s1:
if x in s2: return True
else:
for x in s2:
if x in s1 return True
return False

In Python 2.5 this can be written a bit more concise:

def intersects(set_a, set_b):
if len(set_a) < len(set_b):
set_a, set_b = set_b, set_a
return any(item in set_a for item in set_b)


I'd rather see sets gain an method "isintersect()" with the functionality
than the language to gain a built-in function.

However, there's a very subtle flaw in the idea. While "the intersection"
of two sets is well-defined, "these two sets intersect" is (surprisingly!)
_not_ well-defined. If you only consider non-empty sets, you won't have a
problem: two non-empty sets intersect if their intersection is not empty,
and both implementations of intersects() given will do the right thing.

The problem comes if we (perhaps naively) try to say that if a set A is a
subset of set B, set A must intersect with B. (Not all intersecting sets
are subsets, but all subsets are intersecting sets.) Unfortunately that is
not the same as asking if the intersection between two sets is not empty:

A = set()
B = set([12, 21])
A.issubset(B)
True
B.issuperset(A)
True
intersects(A, B) # both implementations do the same
False
intersects(A, A) # does A intersect with itself?
False


PLEASE don't anybody try to argue that Python's behaviour here is "a bug"
-- the meaning of subset and superset with the empty set is
well-established and completely uncontroversial amongst mathematicians.
(It is what they call a vacuous truth.)

Rather than discuss the issues in detail, I'll just point those who care
to Wikipedia:

http://en.wikipedia.org/wiki/Empty_set#Common_problems

and point out that the behaviour of any() and all() can sometimes be
unintuitive or contradictory for the same reason.

As a result, any proposed function or method that returns a True/False
value for whether set A intersects with set B needs to define (and
justify) what it means to say that two sets intersect when one or both are
the empty set.



--
Steven.

.

Relevant Pages

  • Re: Proposal: s1.intersects(s2)
    ... "these two sets intersect" is ... But you can't avoid treating the empty set as special, ... Of course if you exclude the empty set by definition, ... There's one, obvious, correct definition, as given above. ...
    (comp.lang.python)
  • Re: infinite sequence ring theory problem
    ... certainly false in some rings, so you must have some specific ring to ... >equal to J intersect S, show that IJ intersect S is not the empty set. ... --- Calvin ...
    (sci.math)
  • Re: Minimum distance from a point to a surface defined by constraints
    ... If the half-planes do not intersect, then there is no region (in more ... than 2 dimensions no hypersurface) defined, and so you need to rephrase ... empty set. ... constraint equations, the ...
    (sci.math)
  • Re: Minimum distance from a point to a surface defined by constraints
    ... If the half-planes do not intersect, then there is no region (in more ... than 2 dimensions no hypersurface) defined, and so you need to rephrase ... empty set. ... constraint equations, the ...
    (sci.math.num-analysis)
  • Re: Proposal: s1.intersects(s2)
    ... def intersects: ... "these two sets intersect" is ... Those are exactly the semantics I want, ...
    (comp.lang.python)
Loading