Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!hpfcdc!hpislx!hpmtlx!kwb
From: kwb@hpmtlx.HP.COM ($Keith_Blackwell@hpmtlkb)
Newsgroups: comp.sources.wanted
Subject: Re: Need algorithm to scramble order of array
Message-ID: <730003@hpmtlx.HP.COM>
Date: 18 May 89 19:49:34 GMT
References: <3008@cps3xx.UUCP>
Organization: HP Manufacturing Test Division - Loveland, CO
Lines: 18

| I need a fast algorithm to randomly rearrange the order of elements in
| an array.  Right now I am just using a random number generator to form 
| a list of numbers that directly determines the order of the array like this:

The easiest way is to just extract the components in random order. 
Set a "TopOfList" variable to the maximum index, then each time you
need a new element you just take a random number between the lower
index and TopOfList (inclusive) and swap that element with TopOfList,
then decrement TopOfList.  Of course, once you've run through the
whole thing, the array has been randomly rearranged.  And this is fast!
I doubt you can do it any faster.

I actually thought of this myself when in college, but then I found it
in a slightly different form in (one of?) Knuth's algorithms books.
I guess it's a pretty obvious idea.

--
Keith Blackwell