Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python set intersection question

Tags:

python

set

I have three sets:

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

I want a function that will return True if every set in the list intersects with at least one other set in the list. Is there a built-in for this or a simple list comprehension?

like image 775
Eric Schoonover Avatar asked Oct 01 '10 08:10

Eric Schoonover


People also ask

What is intersection of sets in Python?

Intersection() function Python The intersection of two given sets is the largest set, which contains all the elements that are common to both sets. The intersection of two given sets A and B is a set which consists of all the elements which are common to both A and B.

How do you find the intersection of a set?

For any two sets A and B, the intersection, A ∩ B (read as A intersection B) lists all the elements that are present in both sets, and are the common elements of A and B. For example, if Set A = {1,2,3,4,5} and Set B = {3,4,6,8}, A ∩ B = {3,4}.

Which operator would you use to find the intersection of 2 sets in Python?

The intersection of two sets is the set of all the common elements of both the sets. You can use the intersection() method of the & operator to find the intersection of a Python set.


2 Answers

all(any(a & b for a in s if a is not b) for b in s)
like image 182
jchl Avatar answered Nov 04 '22 16:11

jchl


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.

like image 23
aaronasterling Avatar answered Nov 04 '22 14:11

aaronasterling