From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.107.12.227 with SMTP id 96mr22902606iom.106.1517677165079; Sat, 03 Feb 2018 08:59:25 -0800 (PST) X-Received: by 10.157.24.117 with SMTP id t50mr2355849ott.9.1517677164993; Sat, 03 Feb 2018 08:59:24 -0800 (PST) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!border1.nntp.ams1.giganews.com!nntp.giganews.com!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.am4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!w142no1037654ita.0!news-out.google.com!s63ni1772itb.0!nntp.google.com!w142no1037650ita.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 3 Feb 2018 08:59:24 -0800 (PST) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=2601:191:8303:2100:7466:f44c:da21:40b1; posting-account=fdRd8woAAADTIlxCu9FgvDrUK4wPzvy3 NNTP-Posting-Host: 2601:191:8303:2100:7466:f44c:da21:40b1 References: <87y3ki743m.fsf@jacob-sparre.dk> <40142b86-fdcf-49d3-bee7-2fdbb04c6db0@googlegroups.com> <8c806572-009d-4ba2-a20d-de1209e45ca6@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Card game deck but with trumps suit for tarot "divination" Is there a better way than enumerating all cards? From: Robert Eachus Injection-Date: Sat, 03 Feb 2018 16:59:25 +0000 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Received-Bytes: 4267 X-Received-Body-CRC: 381824725 Xref: reader02.eternal-september.org comp.lang.ada:50292 Date: 2018-02-03T08:59:24-08:00 List-Id: 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. >=20 > As previously noted, Ada 2020 has added an additional Random function int= o=20 > Discrete_Random to deal with this problem. The reason to use Long_Float, or an even better generator if available is t= hat 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 wors= e 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 a= bout 5.36x10**28, the tarot deck doesn't deal evenly into four hands, but y= ou can deal it into two, three, six, or 13 hands. ;-) >=20 > An alternative approach using current Ada would be to use a fixed=20 > Discrete_Random range (0 .. 77), and simply discard any values that ident= ify=20 > cards already dealt, just retrying to get a random value. This works well= =20 > and is properly uniform, but only if you are going to deal part of the de= ck=20 > (say 25%). If you need to deal the whole deck, it can get slow toward the= =20 > end when most of the values returned from Random have already been dealt.= =20 > (That's especially bad if you forget to special case the last card to the= =20 > dealt - you don't need a random choice to figure out which one that is af= ter=20 > all of the rest have been dealt.) >=20 > Experience shows that most users don't get this right, as did the discuss= ion=20 > on the topic (in which many knowledgeable people suggested approaches whi= ch=20 > just don't work). I had to fix the Janus/Ada random number generator afte= r=20 > 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 l= ot of RNG calls near the end. If you are going to special case the last ca= rd, 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 v= alue per card, then sort takes O(n log2 n) time, and is usually dominated b= y the n RNG calls.