4
$\begingroup$

If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:

U1 = {1,2}

U2 = {3,4,5}

C1 = {3,5}

C2 = {2}

The above sets are guaranteed to be subsets of S, however they may not be subsets of each other. To check if C1 is subset of U2 I need to iterate through both sets and check if all elements of C1 are in U2. In this case 3 and 5 are elements of U2 thus C1 is a subset of U2.

But this operation is O(n) at best if you keep everything sorted. I'm wondering, is it possible to select the elements of S wisely or construct a data structure in such a way to perform fast (like O(1)) subset check operations ?

If this means I need to look into parallel algorithms I am open to that as well.

$\endgroup$
2
  • $\begingroup$ I think you'll need to clarify. $O(1)$ time is not achievable unless you have a guarantee that all sets are of $O(1)$ size. In the worst case, the number of elements you'll have to examine is at least $\min(|C_i|,|U_j|)$, since you have to look at every element of the smaller set (in the worst case where it is a subset). Do you allow preprocessing of the sets? Do you need to answer many such subset queries? What's the application, and what are the requirements? $\endgroup$
    – D.W.
    Oct 25, 2013 at 5:53
  • $\begingroup$ I would allow for pre-processing. $\endgroup$ Oct 25, 2013 at 16:51

3 Answers 3

2
$\begingroup$

Represent sets as Bit Sets. Java has built-in implementation. A is subset of B if A & B = A. These operations on bit sets are fast (O(1) ).

$\endgroup$
2
  • $\begingroup$ Great suggestion. How do you know these bitset operations are O(1) ? Where is that documented? $\endgroup$ Oct 28, 2013 at 2:43
  • $\begingroup$ I was wrong, O(1) only for small sets (no more than word size, 32 or 64), O(N) for larger sets, where N is the size of universe. Anyway, I belive it is the fastest way. And it can be parallelized, but effect is greater than overhead for only extremly large sets (millions of elements). $\endgroup$ Oct 28, 2013 at 6:41
1
$\begingroup$

Here's one heuristic that might help in some practical situations:

Store the $U$ sets in sorted order, or for each $U$ set keep a hashtable of the elements of the set.

To test whether $C_i$ is a subset of $U_j$, select a few elements at random from $C_i$. For each selected element $x$, test whether $x \in U_j$. If $x \notin U_j$, you can immediately answer "No, $C_i$ is not a subset of $U_j$": you can answer the answer quickly. If $x \in U_j$ for each selected element, then there's no shortcut: you have to compare all the elements, for a running time of $O(|C_i| \lg |U_j|)$ or $O(|C_i|)$ (depending upon whether you have sorted lists or a hashtable).

This doesn't help if what you care about is worst-case performance. But if you have a practical application, depending upon how the sets you're dealing with are formed, you might find it helpful.

$\endgroup$
1
  • $\begingroup$ If I have the control over the universe S - is it possible to achieve faster running times than what you state? I'm not an expert in math - but could this perhaps involve abstract algebra / group theory? $\endgroup$ Oct 25, 2013 at 16:50
1
$\begingroup$

For an approximate solution, bloom filters could be an option. You get guaranteed negative answers, and a bound on the false positive rate. Bloom filters would have O(log(1/epsilon)) space complexity, where epsilon is the false positive rate you want. Time complexity for intersection would be the same. So compared to bit sets, you get a complexity that is, if i translate the false positive rate correctly, logarithmic in the universe's size, as compared to linear in that size for BitSets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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