[104839] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Greg Rose)
Thu Oct 29 14:51:01 1998
Date: Thu, 29 Oct 1998 09:39:14 +1000
To: coderpunks@toad.com
From: Greg Rose <ggr@Qualcomm.com>
In-Reply-To: <3638AD59.D40888BD@acm.org>
Reply-To: Greg Rose <ggr@Qualcomm.com>
At 10:00 29/10/98 -0800, Jim Gillogly wrote:
>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
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
