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.
Computing unique subset intersections
ds.algorithms;permutations;dynamic programming
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)$?