7
$\begingroup$

Do you know of any data structure $S[A]$, that maintains a (finite) set $A \subset \mathbb{Z}_{\geq0}$ of non-negative integers, subject to the following operations:

  1. Given $S[A],$ calculate minimal excludant $\mbox{mex} A = \min \ \mathbb{Z_{\geq 0}} \setminus A.$
  2. Given two data structures for sets $A$ and $B$, construct a data structure, maintaining the union of the two $S[A \cup B]$.

Disjoint set union comes into mind, but I can't think of a way to make it support mex-es. Intuitively, the problem I see is that we can have a situation in which both $A$ and $B$ contain many small intervals, and then their union is hard to obtain.

Ideally, both of these should be polylog (on the size of the represented sets).

How about if the sets are from a bounded universe?

Improve this question
$\endgroup$
13
  • $\begingroup$ What other operations are available? Can I create a structure from any finite set $A$? $\endgroup$
    – jbapple
    Oct 22, 2013 at 15:18
  • 2
    $\begingroup$ This might be relevant for the bounded universe case: arxiv.org/abs/1002.4248 $\endgroup$
    – Chao Xu
    Oct 22, 2013 at 18:48
  • 1
    $\begingroup$ Can you modify the set $A$ after you've created $S[A]$? If you created $S[A]$, $S[B]$, and $S[A \cup B]$, can you then modify $A$? If you can, what do you want to have happen in this case? Do you want both $S[A]$ and $S[A \cup B]$ (and $\operatorname{mex} A$ and $\operatorname{mex} B$) to be updated rapidly? $\endgroup$
    – D.W.
    Oct 23, 2013 at 0:33
  • $\begingroup$ @jbapple - We can assume that we could do that. It just boils down to creating $S[\{a\}]$ for each element in $A$, and then taking the union of all these. $\endgroup$
    – comco
    Oct 23, 2013 at 7:15
  • 1
    $\begingroup$ By thinking about this problem a little bit more, it can be restated as follows: maintain a dynamic collection $\{A_1, A_2, ...\}$ of subsets of ordered universe $U,$ with respect to finding the minimal element of $A_i,$ and finding the intersection of two existing sets (then maybe removing them from collection, and of course, after this operation, C becomes part of the collection and it becomes possible to intersect it with other sets from the collection): $C = A_i \cap A_j.$ $\endgroup$
    – comco
    Oct 23, 2013 at 17:27

1 Answer 1

Reset to default
4
$\begingroup$

Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).

Amortized constant time

We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).

There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.

To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.

Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.

Worst-case logarithmic time

For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:

  • union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)
  • a binary search tree of the elements in the union of all the sets
  • for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)
  • for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)
  • the smallest element of each set
  • a priority queue of the smallest elements of sets that are not Z.

Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.

Improve this answer
$\endgroup$

Your Answer

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

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