Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
Jim Gillogly (jim@acm.org)
Thu, 29 Oct 1998 10:00:57 -0800
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 CodherPlunks 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
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23