-1

Is there a difference between the 2 below methods for choosing a random card from a deck of cards? Is one approach more accepted than the other?

Method 1: Generate a random number from 1-52 for the first card them remove that card from the array and choose a number from 1-51, then 1-50, then 1-49, etc... to get subsequent cards from the deck.

Method 2: Generate a number from 1-52 and add that number to a “used numbers array”. For each additional card, continue to choose a number from 1-52 each time, then check the used numbers array to see if it’s already been used. Repeat generating a number between 1-52 until you get a result that hasn’t been used, then add it to the used number array.

Obviously, method 1 is more efficient in terms of compute cycles - but is there any other difference between the 2 approaches? Is one approach “more random” than the other? Or “better” for any other reason related to the quality of the randomization?

  • "is there any other difference between the 2 approaches?" - no, there is not. "Is one approach “more random” than the other?" - no. To prove this, think about the probabilities of choosing the next number to pick from the deck. – Doc Brown Mar 24 at 21:53
  • 3
    Better: use Fisher-Yates to shuffle the deck in place, then just draw cards. Requires only one random number per card and no extra storage. Linear time. – Alex Reinking Mar 24 at 22:15
  • Also Method 2 takes expected n log n time (for n the size of the deck) and Method 1 takes quadratic time if you actually remove. – Alex Reinking Mar 24 at 22:23
  • Thank you for the responses. I’m curious though as to what I did wrong here to receive so many negative notes...did I break some sort of rule? – Jim Mar 25 at 2:46
  • @Jim, I would guess that the down-votes and close-votes are because this isn't exactly on topic; this seems to be a better fit for either mathematics or for computer science. IIRC your two processes are, in fact, equivalent as far as the randomness is concerned. There isn't a 'more random' but you can be less than random, i.e. your process could leak information or be predictable to some extent that someone could have a better than random chance at guessing the order, next card, etc. – esoterik Mar 25 at 3:10
1

Completely depends on the pseudo-random number sequence.

Lets assume a good RNG that generates K bits per call with each bit being statistically random, an independent probability of 50%.

Picking from the remaining cards

In the first example you are using every number generated from the RNG sequence. You are calling the RNG 51 times, given that the last card picks itself.

However most numbers between 2 and 52 are not even powers of 2. As such you cannot in a statically unbiased way generate numbers in the ranges from 1 to 52 (or 0 to 51 same issues). There will always be a slightly higher chance that some index will be chosen first.

Dead Numbers

In the second example you are introducing dead numbers. By discarding any number that is not 1-52 or has already been drawn each card will have a statistically equal chance of being anywhere in the sort.

The problem with the second solution is that:

  1. the RNGs are not guaranteed to generate every number atleast once - hence it may never terminate.
  2. the algorithm has an unknown runtime - because the last required number may be at position 2^64 of the RNG and each intermediate position must be generated first.

Swapping places

A better algorithm would be to shuffle the cards, by swapping two random locations in the deck some high number of times. see Fisher-Yates Shuffling

The benefit here is that shuffling has a bounded time, and the quality of the shuffle is less dependent on the quality of the RNG then the two previous methods.

  • Thanks for your detailed answer and advice. My use case is actually for Bingo Balls in a drum and not a deck of cards. I thought the scenarios were similar enough that any answer I received would apply to both scenarios - but I see the difference now would be that with a deck of cards, you set the order at the beginning (by shuffling) but for Bingo balls, the uncalled numbers would continue to bounce around until called. I’m not sure I understand what you mean by dead numbers. How is it possible for a number to never be selected? – Jim Mar 25 at 2:44
  • 1
    A Dead Number in this case is a number that when drawn, does nothing. Either because it was never drawable (52<x like 53) or it has already been drawn ie: 1, 51, 3, 51. That last 51 had already been drawn hence is dead. As for the similarity from the perspective of probability there is no difference. The cage is simply a device that emits a sequence of balls. A deck of cards emits a sequence of cards. Each ball/card occurs once in the entire sequence and both sequences are finite. Your goal is presumably to randomly select one of these permuted sequences and reveal it element by element. – Kain0_0 Mar 25 at 3:45

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.