Re: Card game deck but with trumps suit for tarot "divination" Is there a better way than enumerating all cards?

[Robert Eachus <rieachus@comcast.net>]

On Friday, February 2, 2018 at 6:05:23 PM UTC-5, Randy Brukardt wrote:

> >Why go through sorting the Long_Float values?  If you draw without
> >replacement, you draw from 78 cards, then 77, 76, 75,...4,3,2,1.  There
> >is nothing in Ada's random number generators to guarantee that these 78
> >generators work together to produce random values.  By choosing 78
> >values from the same generator you don't have that problem.
> 
> As previously noted, Ada 2020 has added an additional Random function into 
> Discrete_Random to deal with this problem.
The reason to use Long_Float, or an even better generator if available is that there are 78! possible orders for the deck. If you use a generator with 2**24 values, there are lots of deck orders you can't generate.  Even worse if the period of the PRNG is significantly less than the number of deals.  (If you are dealing the cards into n hands of k cards, there are 78!/((k!)**n possible deals.  For bridge hands (52 card deck, four hands) this is about 5.36x10**28, the tarot deck doesn't deal evenly into four hands, but you can deal it into two, three, six, or 13 hands. ;-)
> 
> An alternative approach using current Ada would be to use a fixed 
> Discrete_Random range (0 .. 77), and simply discard any values that identify 
> cards already dealt, just retrying to get a random value. This works well 
> and is properly uniform, but only if you are going to deal part of the deck 
> (say 25%). If you need to deal the whole deck, it can get slow toward the 
> end when most of the values returned from Random have already been dealt. 
> (That's especially bad if you forget to special case the last card to the 
> dealt - you don't need a random choice to figure out which one that is after 
> all of the rest have been dealt.)
> 
> Experience shows that most users don't get this right, as did the discussion 
> on the topic (in which many knowledgeable people suggested approaches which 
> just don't work). I had to fix the Janus/Ada random number generator after 
> that discussion, as it had made one of the mistakes as well.

If your random number generator uses the Linux RNG for initialization, and has a long enough period (the GNAT generator does) the above will work, and is reasonably fast.  Throwing back duplicates, as Randy said, can take a lot of RNG calls near the end.  If you are going to special case the last card, why not special case the last few cards, generate a permutation of say six values and use that for the last six cards.  Much faster, but the one value per card, then sort takes O(n log2 n) time, and is usually dominated by the n RNG calls.