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
Greg Rose (ggr@qualcomm.com)
Thu, 29 Oct 1998 09:39:14 +1000
At 10:00 29/10/98 -0800, Jim Gillogly wrote:
>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
Hear hear. This is an apparently simple problem, which people stuff up so
often it isn't funny. I was about to reply to the first anon when Jim's
message came in.
>This swaps 255 times and uses 255 random numbers. Your variation
>of the original algorithm uses 709 swaps and at least 1418 random
>numbers.
I believe the theoretical minimum is O(n log n) *bits* to randomise n
items. (This agrees entirely with the above, given that the random numbers
are log n bits each.) But another, theoretically interesting, way to
randomise is to take a sorting algorithm and make random binary choices
everywhere it would compare two elements and swap them if out of order.
Greg.
Greg Rose INTERNET: ggr@Qualcomm.com
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23