# Number of pairs that do not share an interest

Consider the following problem.

Let $$P$$ be a set where each element represents a person (i.e. $$P = \{p_1, p_2, ..., p_n\})$$. Let $$I$$ be the set of interests (i.e. $$I = \{i_1, i_2, ..., i_m\}$$). We are given a function $$f$$ s.t. $$\forall p_i \in P$$, $$f(p_i)$$ is a subset of $$I$$ (in other words, the function allows us to recover a given person's interests from the set of interests). Also, consider that $$m << n$$ (let's assume that, in our case that $$m = n/10$$).

Question: How many pairs of people share at least one interest?

I assume I would have to proceed the following way:

1. Compute the number of possible pairs of people : $$C{n \choose 2}$$
2. Compute the number of pairs that do not share any interest : $$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \text{is_empty}(f(p_i) \phantom{a} \cap \phantom{a} f(p_j))$$ where the is_empty function simply checks if the intersection of both sets is empty and if it is the case, returns $$1$$ (it returns $$0$$ otherwise)
3. The number of pairs that share at least one interest is $$C{n \choose 2}-\sum_{i=1}^{n-1}\sum_{j=i+1 }^{n} \text{is_empty}(f(p_i) \phantom{a} \cap \phantom{a} f(p_j))$$

Is there a better way for me to compute this ? (Typically, here I did not exploit the fact that $$m << n$$). I have large sets and I don't want to compute the double sum by hand (and I would have to enter the sets in a computer to let it run). I am looking for a lazy way out of this :p

The construction goes as such : we construct an (undirected, simple) graph $$G = (V,E)$$, where $$V = P$$ and $$uv \in E$$ iff $$f(u) \cap f(v) = \emptyset$$. The number of edges in this graph represent your your desired answer, which could be computed by summing all the elements in your adjacency matrix.