[104835] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Jim Gillogly)
Thu Oct 29 14:13:25 1998
Date: Thu, 29 Oct 1998 10:00:57 -0800
From: Jim Gillogly <jim@acm.org>
To: coderpunks@toad.com
Reply-To: Jim Gillogly <jim@acm.org>
Another Anonymous says:
> A couple responders have said there is no SWAP_TIMES
> which would work. But I don't understand why the
> following wouldn't work:
[changes the algorithm slightly to make analysis easier]
> Now, simply calculate how many SWAP_TIMES it would take for it
> to be equally as likely that an element would not be touched as
> it would to land in its original spot.
>
> (255/256)^(t*2) = 1/256
> or
> t = ln(1/256)/(2*ln(255/256))
> or
> 708.3955
Fine. But since this is Coderpunks rather than Mathpunks, my point
is that you should simply use Knuth's Algorithm P instead (due to
R. Durstenfeld, CACM 7 (1964)) because it's both correct and much
faster:
for j from 255 down to 1
pick random number k from 0 through j
swap items j and k
This swaps 255 times and uses 255 random numbers. Your variation
of the original algorithm uses 709 swaps and at least 1418 random
numbers.
You make the call.
--
Jim Gillogly
8 Blotmath S.R. 1998, 17:49
12.19.5.11.11, 9 Chuen 4 Zac, Sixth Lord of Night
