Everywhere in this article, and in all of the current comments, where the word "unique" appears, it really should be the word "distinct" instead.
Vitter's reservoir sampling algorithm D: randomly selecting unique items
81–83 of 83 posts
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#82> The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. If you draw (with replacement) over and over again, ignoring cards you’ve already picked, you can simulate a deal, but you run into problems. The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem). I don't think this…
I think it is true. We head off discussion here by referring to the naive approach, but what you're doing is past naive coupon collector's and past the technical scope of the context. There are several steps where your method could (will) fail. Since you don't introduce any machinery for the hand, you imply an O(k^2) checking algorithm. You also imply an unsorted hand. If you generate the hand in random order, then y…
In addition to not being sorted it's also not "online." You won't get the first value out of it in constant time if k is too big, and you need to access elements in a random order.
Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items
#83Here is an alternative: Use a multiplicative linear congruential generator with a period 2^n , where n is ceil(log2(m)), where m is the size of the list. Seed the generator, start generating values and drop all values that are larger than m. In the worst case you will have to drop half of the values, in the best case you will drop none. This depends on how close to a power of 2 m is. The generator is very short, one…
This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations. There are "N choose k" combinations, which in the worst case (k = N/2) grows as ~ 2^N. The number of combinations quickly outstrips the number of possible states of the LCG, and most combinations will never be found. For example, we have a list of length 16 and wish to choose 8. We have a choic…
By randomly adding skips, can definitely get to all possible combinations even with only 16 seeds (since skips can be seeded from a much larger space), although there could be a speed implication.