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=-0.9 required=5.0 tests=BAYES_00,FROM_NUMERIC_TLD autolearn=no 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-04 05:23:26 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!nntp.abs.net!lore.csc.com!baen1673807.greenlnk.net!baen1673807!not-for-mail From: Stuart Palin Newsgroups: comp.lang.ada Subject: Re: Ada2005 random Date: Fri, 04 Apr 2003 13:20:13 +0100 Organization: Computer Sciences Corporation Message-ID: <3E8D787D.A3999D46@0.0> References: NNTP-Posting-Host: 20.44.241.70 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: lore.csc.com 1049458814 9130 20.44.241.70 (4 Apr 2003 12:20:14 GMT) X-Complaints-To: abuse@news.csc.com NNTP-Posting-Date: Fri, 4 Apr 2003 12:20:14 +0000 (UTC) X-Mailer: Mozilla 4.5 [en] (WinNT; I) X-Accept-Language: en X-Original-NNTP-Posting-Host: rc2966.rochstr.gmav.gecm.com X-Original-Trace: 4 Apr 2003 13:18:27 GMT, rc2966.rochstr.gmav.gecm.com Xref: archiver1.google.com comp.lang.ada:35925 Date: 2003-04-04T13:20:13+01:00 List-Id: 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. Depending on the size of the set, and the nature in which the size changes you could create an initial set and then use one of the many 'shuffling' algorithms readily available (make sure you use one that truly preserves the randomness statistics - ISTR there is a subtle point in one of the most obvious algorithms). You can then simply draw your random selection by moving through the list. There are probably many 'themes' on this idea that you can play around with, depending on your needs. (For instance if your 'set' is a linked list, you could make it a doubly linked list, the secondary link being a random order). -- Stuart Palin