Madhu <enometh@meer.net> wrote:
+---------------
| * (Rob Warnock) <Tt6dnXoBBpIQcgbUnZ2dnUVZ_jmdnZ2d@speakeasy.net> :
| | Marco Antoniotti <marcoxa@gmail.com> wrote:
...
| I suspect both of these functions are likely to produce "less than
| random" results, [although I doubt it would be a concern to the OP] I
| think a small bias is introduced in sampling the uniform random process
| producing the numbers.
+---------------
Indeed. We had a long discussion about that here about three years ago,
and at that time I even observed that:
The pages <http://www.nist.gov/dads/HTML/fisherYatesShuffle.html>
and <http://www.nist.gov/dads/HTML/idealRandomShuffle.html>[1] contain
comments on & references to why you don't want to do this. Briefly;
Note: Attaching random tags then sorting (see permutation)
may not be a perfect shuffle: if tags may be duplicated, a
stable sort has a greater chance of producing permutations
with some items in the original order.
A Fisher-Yates shuffle in an array initialized to (IOTA BOUND)
would be truly random, and if the desired output sequence LENGTH
were close to BOUND it would probably be near-optimal in performance
as well [certainly much better than either Marco's or my functions].
On the other hand, if LENGTH << BOUND, then the non-randomness of
Marco's or my functions due to the chance of duplicates will be small,
and the performance will be much better than Fisher-Yates.
-Rob
[1] Actually, the page I quoted in March 2006 was the following one,
which has since been replaced by the one referenced above:
http://www.nist.gov/dads/HTML/perfectShuffle.html
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607