The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.
Algorithm No One Knows About (2016)
61–70 of 200 posts
Re: Algorithm No One Knows About (2016)
#62Ok I'll take a shot at it. Pick a number between 0 and N. Let's call it p for pivot. Each draw after this initial draw is either less than p with probability p/(N-1) or greater than p with probability 1-p/(N-1). You need to make k-1 additional draws. The probability of m of those draws being less than p is given by the binomial distribution. Choose m from the binomial distribution. Then run the algorithm recursively…
[deleted]
Re: Algorithm No One Knows About (2016)
#63Earlier quoted context omitted.
If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done.
One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k.
If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties)
This also wouldn't use much extra space, and doesn't require special handling for small or large k.
Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.
Re: Algorithm No One Knows About (2016)
#64Can't you use https://en.wikipedia.org/wiki/Lehmer_random_number_generator for this? I thought that was a common method of generating a random sequence without repetition. True, the result is not very random, but in most applications it doesn't make much of a difference.
Not if you want it to be actually random.
But you might be correct if you simply want the appearance of randomness.
Re: Algorithm No One Knows About (2016)
#65Ok I'll take a shot at it. Pick a number between 0 and N. Let's call it p for pivot. Each draw after this initial draw is either less than p with probability p/(N-1) or greater than p with probability 1-p/(N-1). You need to make k-1 additional draws. The probability of m of those draws being less than p is given by the binomial distribution. Choose m from the binomial distribution. Then run the algorithm recursively…
What's the time complexity of sampling from the binomial distribution?
Re: Algorithm No One Knows About (2016)
#66If this really was such an obscure but useful algorithm, someone should change the title of this post to help people find it in the future so it doesn't remain obscure (add "card drawing"?)
It's... not that useful, as far as I can tell (unless I'm still under-caffeinated!)
@avip mentions the following comment https://news.ycombinator.com/item?id=20961320 , which means that we only have to consider k ~ cn for 0 ≤ c ≤ 1/2. Drawing in this fashion, we have an expected runtime of k * (H_n - H_{(1-c)n}) ≤ k * (H_n - H_{n/2}) ~ O(k).[1]
The latter is true since H_n ~ log n + C + O(1/n) for some[2] constant C.
Of course, depending on what the author's constraints are, there would be an additional O(k) space requirement for keeping track of indices that have already been picked. Vitter's algorithm is particularly nice, since it can report the items without this additional space requirement.
---
[1] https://en.wikipedia.org/wiki/Coupon_collector's_problem
Re: Algorithm No One Knows About (2016)
#67Earlier quoted context omitted.
...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail? You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...
You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.
I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above...
...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...
Re: Algorithm No One Knows About (2016)
#68Earlier quoted context omitted.
The python algo does not get slow when n is large. The k~n case obviously calls for inverse selection. https://github.com/python/cpython/blob/master/Lib/random.py#...
NOTE: This comment I wrote is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 Yeah, but the k ~ n/2 case (in which inverse selection and normal selection have the same runtime) is still Ω(n log n) (equiv Ω(k log k)), which is still "slower" than the presented algorithm.
Actually, this comment is correct despite making a similar argument to your incorrect one elsewhere. Using a set to accumulate intermediate results requires k inserts at O(log k) each.
Re: Algorithm No One Knows About (2016)
#69> given non-negative integers k and n with k > We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.)
Sounds like the Knuth multiplicative hash.
The Art of Computer Programming vol. 3, section 6.4, page 516.
Re: Algorithm No One Knows About (2016)
#70The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.
This is a good approach. Thanks to bijective mapping between original and encrypted spaces the result is guaranteed to be unique. And since the mapping function is a secure encryption algorithm, the output has uniform distribution. Well done.