alt Hacker News> If you wrote a function that takes a PRNG and generates a random object, you already have a function capable of enumerating all objects.
More specifically: if you uniformly sample from a space of size N, then in O(N log N) tries you can expect to sample every point in the space. There's a logarithmic cost to this random sampling, but that's not too bad.
Replies
matklad • today at 1:06 PM
It is much better than this. You can _directly_ enumerate all the objects, without any probabilities involved. There's nothing about probabilities in the interface of a PRNG, it's just non-determinism!
You could _implement_ non-determinism via probabilistic sampling, but you could also implement the same interface as exhaustive search.
➕ show 1 reply
Just a tiny addition: Yes, N log N is the average time, but the distribution is heavily long-tailed, the variance is quite high, so in many instances it might take quite some time till every item has been visited (in contrast to merely most items).
The keyword to look up more details is "coupon collector's problem".