Python set intersection question

all(any(a & b for a in s if a is not b) for b in s)

Here's a very simple solution that's very efficient for large inputs:

def g(s):
 import collections
 count = collections.defaultdict(int)
 for a in s:
 for x in a:
 count[x] += 1
 return all(any(count[x] > 1 for x in a) for a in s)

It's a little verbose but I think it's a pretty efficient solution. It takes advantage of the fact that when two sets intersect, we can mark them both as connected. It does this by keeping a list of flags as long as the list of sets. when set i and set j intersect, it sets the flag for both of them. It then loops over the list of sets and only tries to find a intersection for sets that haven't already been intersected. After reading the comments, I think this is what @Victor was talking about.

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])] # true, 16 and 14
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] # false
def connected(sets):
 L = len(sets)
 if not L: return True
 if L == 1: return False
 passed = [False] * L
 i = 0
 while True:
 while passed[i]: 
 i += 1
 if i == L: 
 return True
 for j, s in enumerate(sets):
 if j == i: continue
 if sets[i] & s: 
 passed[i] = passed[j] = True
 break
 else:
 return False
print connected(s0)
print connected(s1)

I decided that an empty list of sets is connected (If you produce an element of the list, I can produce an element that it intersects ;). A list with only one element is dis-connected trivially. It's one line to change in either case if you disagree.

Here's a more efficient (if much more complicated) solution, that performs a linear number of intersections and a number of unions of order O( n*log(n) ), where n is the length of s:

def f(s):
 import math
 j = int(math.log(len(s) - 1, 2)) + 1
 unions = [set()] * (j + 1)
 for i, a in enumerate(s):
 unions[:j] = [set.union(set(), *s[i+2**k:i+2**(k+1)]) for k in range(j)]
 if not (a & set.union(*unions)):
 return False
 j = int(math.log(i ^ (i + 1), 2))
 unions[j] = set.union(a, *unions[:j])
 return True

Note that this solution only works on Python>= 2.6.

As usual I'd like to give the inevitable itertools solution ;-)

from itertools import combinations, groupby
from operator import itemgetter
def any_intersects( sets ):
 # we are doing stuff with combinations of sets
 combined = combinations(sets,2) 
 # group these combinations by their first set
 grouped = (g for k,g in groupby( combined, key=itemgetter(0)))
 # are any intersections in each group
 intersected = (any((a&b) for a,b in group) for group in grouped)
 return all( intersected )
s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])]
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] 
print any_intersects( s0 ) # True
print any_intersects( s1 ) # False

This is really lazy and will only do the intersections that are required. It can also be a very confusing and unreadable oneliner ;-)

To answer your question, no, there isn't a built-in or simple list comprehension that does what you want. Here's another itertools based solution that is very efficient -- surprisingly about twice as fast as @THC4k's itertools answer using groupby() in timing tests using your sample input. It could probably be optimized a bit further, but is very readable as presented. Like @AaronMcSmooth, I arbitrarily decided what to return when there are no or is only one set in the input list.

from itertools import combinations
def all_intersect(sets):
 N = len(sets)
 if not N: return True
 if N == 1: return False
 intersected = [False] * N
 for i,j in combinations(xrange(N), 2):
 if not intersected[i] or not intersected[j]:
 if sets[i] & sets[j]:
 intersected[i] = intersected[j] = True
 return all(intersected)

This strategy isn't likely to be as efficient as @Victor's suggestion, but might be more efficient than jchl's answer due to increased use of set arithmetic (union).

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])]
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])]
def freeze(list_of_sets):
 """Transform a list of sets into a frozenset of frozensets."""
 return frozenset(frozenset(set_) for set_ in list_of_sets)
def all_sets_have_relatives(set_of_sets):
 """Check if all sets have another set that they intersect with.
 >>> all_sets_have_relatives(s0) # true, 16 and 14
 True
 >>> all_sets_have_relatives(s1) # false
 False
 """
 set_of_sets = freeze(set_of_sets)
 def has_relative(set_):
 return set_ & frozenset.union(*(set_of_sets - set((set_,))))
 return all(has_relative(set) for set in set_of_sets)

This may give better performance depending on the distribution of the sets.

def all_intersect(s):
 count = 0
 for x, a in enumerate(s):
 for y, b in enumerate(s):
 if a & b and x!=y:
 count += 1
 break
 return count == len(s)

• python
• set