2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Rahul Apr 18 '15 at 2:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Gregory J. Puleo Apr 18 '15 at 2:44
  • $\begingroup$ 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. $\endgroup$ – David Apr 18 '15 at 2:50
  • $\begingroup$ 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. $\endgroup$ – David Apr 18 '15 at 3:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Henry Swanson Apr 18 '15 at 3:52
3
$\begingroup$

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.

If the sample is large, it uses the Fisher-Yates Shuffle method. It repeatedly picks a random index and pulls that card into your sample, removing it from the deck at the same time. Technically, it removes the card and swaps the last card into the place it removed from, instead of just shifting the stuff after the gap; this reduces the amount of moving you need to do to shorten the list.

The first method works quickly for small samples, and doesn't use up much memory: it needs only enough room to store as many indexes as the size of the sample, and each card selection requires slightly more than one random number to perform. The number of required random numbers grows as you select more cards: to 1.5 at 1/3 of the deck already selected, to 2 at 1/2 the deck already selected, and it gets worse from there: see the Coupon Collector's Problem. So it's terrible for large samples.

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).

Your "unpick" method has an important restriction: the results of unpicking aren't shuffled.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.