In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are 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.

  • $\begingroup$ I can see a statistics angle here. What is the computer science angle? What are the requirements on the output? I see in-/valid, most likely (which you gave) suspect (like [3E9, 0, 0, 1E9-1, 2], [0, 3E9, 0, 1E9+1, 0], [0, 0, 3E9, 1E9, 0]). $\endgroup$ – greybeard Aug 1 '19 at 5:29
  • $\begingroup$ The computer science angle would be determining the best possible time and space complexity of sampling the statistical distribution. $\endgroup$ – Victor Aug 1 '19 at 14:38
  • $\begingroup$ $O(1)$, I dare say. I'd stare hard at int org.apache.commons.math3.distribution.HypergeometricDistribution.sample(). $\endgroup$ – greybeard Aug 2 '19 at 3:45
  • $\begingroup$ @greybeard, that implementation uses binary search, which isn't constant time. $\endgroup$ – Victor Aug 2 '19 at 14:45

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.

  • $\begingroup$ What is the typical time and space complexity of sampling hypergeometric distributions? $\endgroup$ – Victor Aug 1 '19 at 14:38
  • $\begingroup$ I have no clue, but I’m sure you can find out. $\endgroup$ – Yuval Filmus Aug 1 '19 at 15:01
  • $\begingroup$ Many libraries that sample from a hypergeometric distribution have a time complexity of O(r), where r is the result, so the time complexity would be the same as the naive algorithm. $\endgroup$ – Victor Aug 5 '19 at 20:34

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.