Check to see if the collection set is pairwise disjoint

Question

What is the most efficient way to determine if a collection of sets is pairwise disjoint? those. verify that the intersection of all pairs of sets is empty. How effective can this be done?

Answer 1

Estimated linear time O (total number of elements):

def all_disjoint(sets): union = set() for s in sets: for x in s: if x in union: return False union.add(x) return True 

This is optimal under the assumption that your input is a collection of sets represented as some sort of disordered data structure (hash table?), Because you need to look at each element at least once.

You can do much better by using a different view for your sets. For example, keeping a global hash table that stores for each element the number of sets in which it is stored, you can perform all the specified operations optimally, as well as check disjointness in O (1).

Answer 2

Sets from a set do not intersect in pairs if and only if the size of their union is equal to the sum of their sizes (this statement applies to finite sets):

 def pairwise_disjoint(sets): union = set().union(*sets) n = sum(len(u) for u in sets) return n == len(union) 

It may be a one-line, but an indicator of readability .

Answer 3

Using Python as psudo code. The following tests to intersect each pair of sets only once.

 def all_disjoint(sets): S = list(sets) while S: s = S.pop() # remove an element # loop over the remaining ones for t in S: # test for intersection if not s.isdisjoint(t): return False return True 

The number of intersection tests coincides with the number of edges in a fully connected graph with the same number of vertices as the set. It also leaves earlier if any pair is disjoint.