# Find a non-minimal sequence of elements covering the support set

Consider a sequence $$s$$ of $$n$$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $$O(1)$$ time with arbitrary positions). Denote $$\text{supp}(s) = \left\{ x \in \mathbb{N} \;|\; x \in s \right\}$$, the support set for $$s$$.

We are interested in obtaining a supporting sequence $$s'$$ of elements such that $$\text{supp}(s) = \text{supp}(s')$$; in other words, we want a sequence of elements, in any order and possibly with repetitions, with appearances of all of elements appearing in $$s$$ (and no others).

The minimum such sequence is any ordering of the actual support set for $$s$$. But - we don't need the minimum itself. In fact, we are given a size bound $$m$$, and must produce an $$s'$$ with $$|s'| \leq m$$.

What algorithmic approach would you suggest for producing $$s'$$, which would have meaningfully better than just obtaining the exact support set - in terms of worst-case time complexity?

This question is related to this one.

Notes:

• The algorithm is not limited to just comparisons (so hashing is on the table if you like).
• Obviously, the complexity cannot be any better than $$\Theta(n)$$, since you have to actually read all the input; and it can't be worse than $$\Theta(n \log(n))$$, with which complexity you can just obtain the exact support.
• Constant-factor improvements are significant, e.g. fewer reads of each element, even if the $$O(\cdot)$$ or $$\Theta(\cdot)$$ class might be same. I'm hoping for something that depends on $$m$$ or $$m - |s'|$$ obviously.
• Better in what respect? Are you trying to minimize worst-case running time? What's your model of computation? Do you require a deterministic algorithm? Do you require an algorithm that uses only comparisons? Do you need a streaming/online algorithm? The running time of different algorithms might depend in a delicate way on these assumptions. What counts as significant? You're not going to be able to get more than a $O(\log n)$-factor speedup.
– D.W.
Nov 21 '19 at 17:39
• @D.W.: Sorry, I should have added more details before submitting the question. See edit. Nov 21 '19 at 19:25
• I still wonder if hashing might be the best solution. I see that in your previous question you rejected it because it is not deterministic, but given that you mention constant-factor improvements, I wonder whether hashing might actually be the best solution. If you use 2-universal hashing, not only is the expected running time $\Theta(n)$, but we can also prove that there is a small constant $c$ such that there is only an exponentially small probability that the running time exceeds $c\cdot n$. I don't think it makes engineering sense to worry about exponentially small probabilities; [..]
– D.W.
Nov 21 '19 at 20:34
• they are smaller than the probability that a cosmic ray hits your microprocessor and causes it to produce the wrong output or enter an infinite loop. If we're willing to accept the risk of cosmic-ray-induced faults (which most people seem to be), then it seems like we also ought to be willing to accept the risk of an exponentially small chance of getting a poor random seed that causes our algorithm to take longer (or produce the wrong output). [...]
– D.W.
Nov 21 '19 at 20:35
• From a theoretical perspective the difference between deterministic vs randomized algorithms is interesting, but if we adopt that theoretical perspective, constant factors are normally irrelevant. So I'm struggling to find a context that would lead to the stated requirements and that also makes hashing unacceptable.
– D.W.
Nov 21 '19 at 20:36