Re: Ada2005 random

[Mark Biggar <mark.a.biggar@attbi.com>]

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