# Efficient algorithm to simulate dealing cards from a large deck of cards?

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.

• 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]). – greybeard Aug 1 '19 at 5:29
• The computer science angle would be determining the best possible time and space complexity of sampling the statistical distribution. – Victor Aug 1 '19 at 14:38
• $O(1)$, I dare say. I'd stare hard at int org.apache.commons.math3.distribution.HypergeometricDistribution.sample(). – greybeard Aug 2 '19 at 3:45
• @greybeard, that implementation uses binary search, which isn't constant time. – Victor Aug 2 '19 at 14:45