# Fast method to pick unique random numbers?

In general, computer simulation involving random numbers (lets say to simulate a fair deck of playing cards so $1$ thru $52$) runs fast if you only pick a few cards. However, as you pick more and more, the algorithm slows because of "collisions", meaning, the random number generator will very likely repeat a card and then we will have to try again to resolve it. As we get closer and closer to exhausting the deck (like we picked $45$ cards and still want more), the algorithm "crawls" (by comparison to when we pick only a few cards) since there are mostly collisions as the available cards dwindle (using the flag method of already seen cards).

So I am wondering what a good way is to alleviate this problem for simulation of games where we need a variable # of random numbers from about $25$% to $90$% of all possible. Perhaps we can just concentrate on $50$% for the sake of comparing speeds. For example, to pick $26$ of $52$ cards randomly using the flag method, we would need on average $1.38 * 26 = 36$ random numbers which is very reasonable and quite fast but can we do better as far as speed?

Also, would it be fair to say that if we choose a random number (let's say from $1$ to $52$ representing the cards in a deck), and we get a collision, that just picking the next higher not yet chosen card still maintains good randomness because each previously chosen card has an equal chance of a collision? For example, if we choose $2, 37, 51, 15, 44, 37$, we would then make the 2nd $37$ a $38$ because $38$ has not been chosen yet.

• The conceptually simplest way is to shuffle the deck and then take the first 45 cards. I like your method 1, which is basically a lazy version of that. – user856 Apr 18 '15 at 2:41
• As for the question of efficiency: if you use an array to mark which cards you've seen yet and which you haven't, you're basically trying to solve the Coupon-Collector Problem: en.wikipedia.org/wiki/Coupon_collector%27s_problem . If you wanted to shuffle the entire $n$-card deck this way, it would take about $n\log n$ random numbers. In contrast, Fisher--Yates only needs a linear number of steps, so it should be faster asymptotically. I imagine the same is true if you only need "most" of the deck instead of all of it. – Gregory J. Puleo Apr 18 '15 at 2:44
• I could implement a few methods and time them and see which one "wins". I like my 1st method because we basically force the random number to work every time by moving the chosen card out of range of the next smaller random number. In the past, I generally use an array of flags and set them to all false before I pick and cards and then just set the flag after picking which is a straighforward way to do it and it also has the advantage that the position of the card itself implies the actual card, thus we don't have to store any card information as it is implied. – David Apr 18 '15 at 2:50
• In college they were concerned about the complexity of algorithms such as $n^2$ or $n$ log $n$ or just $n$ but here I am concerned about the actual runtime because I do a fair amount of simulation of card games and such so I want it to be as fast as possible so I can get more decisions. Remember time is of the essence here so "shuffling" of a deck is "wasting" time. – David Apr 18 '15 at 3:17
• If you're drawing a large number of cards, shuffling isn't any slower than drawing randomly, because once you've shuffled, you just need to iterate through the array. You'll still need to make $n$ random picks, but now they're all at the beginning, instead of spaced out. – Henry Swanson Apr 18 '15 at 3:52

Python's random.sample method solves this problem, and chooses between two different ways depending on how large the sample is compared to the full deck.
If the sample is relatively small, it will generate a bunch of random indexes into the array, and throw out duplicates (using the set type), until it has the right number of distinct indexes.
The second method always requires exactly one random number generation per selection, and so has guaranteed time performance... but it also requires either a list of indexes the size of the original deck, or freedom to mangle the original deck (which Python's random.shuffle uses).