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 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,c7fc42d2c6a0eedc X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2003-04-13 14:58:39 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!logbridge.uoregon.edu!nntp-server.caltech.edu!attla2!ip.att.net!attbi_feed3!attbi.com!rwcrnsc51.ops.asp.att.net.POSTED!not-for-mail From: Mark Biggar User-Agent: Mozilla/5.0 (Windows; U; Win 9x 4.90; en-US; rv:1.2.1) Gecko/20021130 X-Accept-Language: en-us, en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: Ada2005 random References: <3E997A99.3060506@attbi.com> In-Reply-To: <3E997A99.3060506@attbi.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: NNTP-Posting-Host: 12.235.88.213 X-Complaints-To: abuse@attbi.com X-Trace: rwcrnsc51.ops.asp.att.net 1050271118 12.235.88.213 (Sun, 13 Apr 2003 21:58:38 GMT) NNTP-Posting-Date: Sun, 13 Apr 2003 21:58:38 GMT Organization: AT&T Broadband Date: Sun, 13 Apr 2003 21:58:38 GMT Xref: archiver1.google.com comp.lang.ada:36124 Date: 2003-04-13T21:58:38+00:00 List-Id: Robert I. Eachus wrote: > Dale Stanbrough wrote: > >> Randy Brukardt wrote: >> >> >>> I needed that for a 'choosing' algorithm, say drawing balls one by one >>> out of a bowl. If you have 8 balls originally, you're choosing 1 out of >>> 7, then 1 out of 6, etc. If you try to use 1 out of 8 the whole time and >>> discarding the useless ones, the second last draw can take a very long >>> time (only 2 out of 8 choices are meaningful). I'm pretty sure that this >>> is a valid technique; certainly the underlying float generator is still >>> random (at least as much as it ever was!), and the use of that result is >>> unbiased. >>> >>> While it would be nice if Ada supported this directly, it's easy enough >>> to write it yourself. > > > If you need a permutation, the best way to do it is to generate a set of > random (float) values, associate them with the data to be permuted and > the sort on this key. I have seen a lot of code that attempts to > permute a list by going through the list and exchanging elements. For > lists of length greater than two this can easily be shown to be biased. > > For example there are 3! = 6 possible permutions of a list of three > elements, the usual version of the swapping algorithm has 3^3 = 27 > possible outcomes, another (worse) variation has 2^3 = 8 different > outcomes. In either case the number of outcomes is not evenly divisible > by the number of different permutations. The way I usualy do random array shuffle has no bias for i in reverse 2..n loop j := random(1..i); swap(x(i), x(j)); end loop; that translates to "randomly select with out replacement until the unselected set is empty" and in the 3 item case results in exactly 6 outcomes (first iteration select 1 of 3, second iteration select 1 of 2 for 6 outcomes). -- Mark Biggar mark@biggar.org mark.a.biggar@attbi.com