33
submitted 2 months ago by swordgeek@lemmy.ca to c/askscience@lemmy.world

OK, I had a hard time coming up with a single sentence title, so please bear with me.

Let's assume I have a computer with a perfect random number generator. I want to draw from a (electronic) deck of cards that have been shuffled. I can see two distinct algorithms to accomplish this:

  1. Fill a list with the 52 cards in random order, and then pull cards from the list in sequence. That is, defining the (random) sequence of cards before getting them. This is analogous to flipping over cards from a the top of a well-shuffled deck.

  2. Generate a random card from the set that hasn't been selected yet. In other words, you don't keep track of what card is going to come up next, you do a random select each time.

Programattically I can see advantages to both systems, but I'm wondering if there's any mathematical or statistical difference between them.

you are viewing a single comment's thread
view the rest of the comments
[-] TootSweet@lemmy.world 1 points 2 months ago* (last edited 2 months ago)

Yeah, #2 is both more space efficient and more time efficient.

How I'd generally do something like that:

  1. Create an empty linked list.
  2. Generate a random integer between 0 and 51 inclusive.
  3. Iterate over the linked list and increment the random integer by one for each integer in the linked list less than or equal to your newly-generated random integer. You can break out of that loop as soon as you hit the first integer in the linked list greater than the newly-generated integer.
  4. Binary insert that integer into the sorted linked list.
  5. For the denomination, output the newly-generated integer modulus 13 plus one. Translate 1 to ace, 11 to jack, etc.
  6. For the suit, output floor of the newly-generated integer divided by 4 plus one. (Translate zero to "hearts", one to "diamonds", etc.)
  7. Loop back to step 2 51 more times.

Step 3 can definitely be optimized much more with a B-tree and a little thought. If you want jokers included, it's pretty straightforward. (Just change step 2 to generate a random integer between 0 and 53 and tweak steps 5, 6, and 7.)

[-] Brokkr@lemmy.world 5 points 2 months ago

I think you're approach is generally correct, but you've made a few errors which make it hard to follow (e.g. mixing up suit and denomination).

However, method two is only more efficient if onky a few cards will be drawn. If nearly the entire deck is drawn or dealt, then 1 is superior. Method 1 can be done with two lists and a random number generator. The length of the 2 lists will always sum to 52 and the RNG is used to decide the order that cards are removed from the first list and added to the 2nd. It requires generating at most 51 random numbers.

[-] TootSweet@lemmy.world 2 points 2 months ago

Good call on both counts!

I went ahead and fixed the suit/denomination mixup. I'll leave the reast as-is so folks can learn from my mistakes and your post continues to make sense.

Cheers!

this post was submitted on 23 Sep 2024
33 points (94.6% liked)

Ask Science

8676 readers
2 users here now

Ask a science question, get a science answer.


Community Rules


Rule 1: Be respectful and inclusive.Treat others with respect, and maintain a positive atmosphere.


Rule 2: No harassment, hate speech, bigotry, or trolling.Avoid any form of harassment, hate speech, bigotry, or offensive behavior.


Rule 3: Engage in constructive discussions.Contribute to meaningful and constructive discussions that enhance scientific understanding.


Rule 4: No AI-generated answers.Strictly prohibit the use of AI-generated answers. Providing answers generated by AI systems is not allowed and may result in a ban.


Rule 5: Follow guidelines and moderators' instructions.Adhere to community guidelines and comply with instructions given by moderators.


Rule 6: Use appropriate language and tone.Communicate using suitable language and maintain a professional and respectful tone.


Rule 7: Report violations.Report any violations of the community rules to the moderators for appropriate action.


Rule 8: Foster a continuous learning environment.Encourage a continuous learning environment where members can share knowledge and engage in scientific discussions.


Rule 9: Source required for answers.Provide credible sources for answers. Failure to include a source may result in the removal of the answer to ensure information reliability.


By adhering to these rules, we create a welcoming and informative environment where science-related questions receive accurate and credible answers. Thank you for your cooperation in making the Ask Science community a valuable resource for scientific knowledge.

We retain the discretion to modify the rules as we deem necessary.


founded 1 year ago
MODERATORS