”Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication.
[…]
Stated more formally: given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n.“
I think that knowing k beforehand makes it a different, easier problem. I don’t see how, if you don’t know k beforehand, you can do without enough memory to store a number of magnitude n!, and even that would be extremely slow, the more items you have to produce (uniformly pick a permutation of n items, and produce as many of them as requested)
If you don’t know k beforehand, you have to (eventually) handle the case where k is large, possibly even equal to n.
If it turns out to be equal to n, you have to generate a permutation.
If it isn’t, you don’t need to, but you need to keep enough information around, in case it turns out that you need.
For example, by the time you’ve generated 2⁶³ integers in the range 1…2⁶⁴, you need to know which 2⁶³ integers still are ‘available’.
I think you can’t do that more compactly than by just picking the permutation to generate at start (whether you can efficiently determine the k-th number in that permutation is a separate problem)
[…]
Stated more formally: given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n.“
I think that knowing k beforehand makes it a different, easier problem. I don’t see how, if you don’t know k beforehand, you can do without enough memory to store a number of magnitude n!, and even that would be extremely slow, the more items you have to produce (uniformly pick a permutation of n items, and produce as many of them as requested)