<p>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$.</p>

<p>$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$.</p>

<p>The total running time would be  within $O(unh^2)$?</p>

CC BY-SA 3.0
2013-04-05T09:09:57.317Z
2013-04-05T09:09:57.317Z
J.y B.y
<p>Given a set <em>S</em> = {s<sub>i</sub> : {z<sub>j</sub> : z &isin; <em>N</em>} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of <em>S</em>?</p>

<p>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 |<em>S</em>|. In that case the goal is low order polynomial complexity as a function of the output length and max(|s<sub>i</sub>|), the latter of which affects the complexity of intersection operations.</p>

<p>For background, I am dealing with several versions of this problem, some larger than others. In the smallest one |<em>S</em>| &asymp; 1,000, |s<sub>i</sub>| &asymp; 10,000 and the values are zip codes.</p>

<p>Tiny example for clarity:</p>

<pre>
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}}
</pre>

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

CC BY-SA 3.0
2013-04-04T09:06:50.147Z
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ε
CC BY-SA 3.0
2013-04-04T15:50:55.100Z
@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
<ds.algorithms><permutations><dynamic-programming>
Computing unique subset intersections
Sim
# Computing unique subset intersections

(Asked by: username_0 on 2013-04-04)

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.

**Tags:** ds.algorithms, permutations, dynamic-programming
> **Comments:**
> **username_1**: 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$.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2013-04-05. Score: 0 | Accepted answer

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)$?


---

