patternMinor
Efficient algorithm to simulate dealing cards from a large deck of cards?
Viewed 0 times
cardsefficientdeckdealingalgorithmlargefromsimulate
Problem
In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are
For example, if there are N=3 players, and there are 5 card types and the count of each card is
A naive algorithm is to create a large array of all of the cards, do the Fisher–Yates shuffle on it, and then go through each element and increment the count of the card for the current player and set the current player to the next player. For the example above, this creates an array of size 12000000002 and requires that many iterations, but there are only 5 card types and 3 players (output is size 15).
Is there a more efficient algorithm? It would have to generate the output with the same probability that the naive algorithm would.
N players, card i goes to player i mod N). If the number of each type of card is known, is there a way to simulate dealing the cards and get a count of each type of card each player has?For example, if there are N=3 players, and there are 5 card types and the count of each card is
[3000000000, 3000000000, 3000000000, 3000000000, 2], one possible output is [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 1], [1000000000, 1000000000, 1000000000, 1000000000, 0], which represents the number of cards of each type that each player has.A naive algorithm is to create a large array of all of the cards, do the Fisher–Yates shuffle on it, and then go through each element and increment the count of the card for the current player and set the current player to the next player. For the example above, this creates an array of size 12000000002 and requires that many iterations, but there are only 5 card types and 3 players (output is size 15).
Is there a more efficient algorithm? It would have to generate the output with the same probability that the naive algorithm would.
Solution
In the special case of two players and two card types, this is exactly the hypergeometric distribution. More accurately, the number of cards of the first type that the first player gets is distributed hypergeometrically; and the rest of the deal can be deduced from that.
Conversely, you can simulate the entire dealing process by sampling appropriate hypergeometric distributions. Indeed, the number of cards of the first type that the first player gets had hypergeometric distribution. After deciding that amount, remove these cards and reduce the number of cards that remain for the first player and repeat, until you have detail the first player their entire hand. Then repeat with the other players.
The two problems are thus equivalent. Presumably there are online resources, and probably even libraries, for sampling hypergeometric random variables efficiently.
Conversely, you can simulate the entire dealing process by sampling appropriate hypergeometric distributions. Indeed, the number of cards of the first type that the first player gets had hypergeometric distribution. After deciding that amount, remove these cards and reduce the number of cards that remain for the first player and repeat, until you have detail the first player their entire hand. Then repeat with the other players.
The two problems are thus equivalent. Presumably there are online resources, and probably even libraries, for sampling hypergeometric random variables efficiently.
Context
StackExchange Computer Science Q#112354, answer score: 2
Revisions (0)
No revisions yet.