# Computing unique subset intersections

Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S?

As per @JeffE's comment below, there are edge cases of exponential output complexity, so the time-efficient measure of complexity should probably be a function of the output length as opposed to |S|. In that case the goal is low order polynomial complexity as a function of the output length and max(|si|), the latter of which affects the complexity of intersection operations.

For background, I am dealing with several versions of this problem, some larger than others. In the smallest one |S| ≈ 1,000, |si| ≈ 10,000 and the values are zip codes.

Tiny example for clarity:

Input: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}}
Output: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}


|S| = 4 and there are 24 = 16 subsets of S. However, there are only five unique sets of subset intersections. The first four are the members of S themselves. The fifth is {3}. The empty set is already a member of S. All other 10 subset intersections produce empty sets also.

• What do you mean by "time efficient"? The output size could be exponentially large. Suppose the input consists of the $n$ possible sets of $n-1$ integers between $1$ and $n$. – Jeffε Apr 4 '13 at 9:06
• @jeffE Very good question. I am not looking for a low theoretical complexity. There are edge cases for sure. In practice, the data is far from "adversary." Perhaps the best way to define time-efficient is as a function of the output length. Assuming this is a correct approach, I'd say I'm looking for low order polynomial complexity in the output. – Sim Apr 4 '13 at 15:50

Let $u$ denote the size of the union of the sets in $S$, $n\leq 2^u$ denote the size of $S$, $h\geq n$ denote the size of the output, and $S_i$ the set of sets resulting of the intersection of $i$ sets from $S$ (in this sense, $S=S_1$), maintained in lexicographical order. For all $i\in[1..n]$, $|S_i|\leq h$.
$S_2$ can be computed in time $un(n-1)/2\leq uh(h-1)/2$: each binary intersection takes at most time $u$, and there are at most $n(n-1)/2$ of them. $S_4, S_8, \ldots$ can be computed in time $uh(h-1)/2$ each in a similar way. Other $S_j$ which are not power of two can be obtained by combining those results, up to $S_n$.
The total running time would be within $O(unh^2)$?