3 ms·
”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-nega
by Someone 7y ago
”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)
- saagarjha 7y agoI don't see why you'd need to generate a permutation?
- Someone 7y agoIf 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)
- tripzilch 7y agoThe author fails to emphasize this, but the key property here is that the output must be returned in order.