2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Jeffε Apr 4 '13 at 9:06
  • $\begingroup$ @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. $\endgroup$ – Sim Apr 4 '13 at 15:50
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.