Xref: utzoo comp.sources.wanted:7509 alt.msdos.programmer:69
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!tektronix!percival!bucket!leonard
From: leonard@bucket.UUCP (Leonard Erickson)
Newsgroups: comp.sources.wanted,alt.msdos.programmer
Subject: Re: Need algorithm to scramble order of array
Message-ID: <1405@bucket.UUCP>
Date: 22 May 89 02:04:43 GMT
References: <3008@cps3xx.UUCP>
Reply-To: leonard@bucket.UUCP (Leonard Erickson)
Organization: Rick's Home Grown Unix; Portland, OR
Lines: 36

In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes:
<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:
<
<	n = size of array
<
<	for i = 1 to n
<		{
<		do
<			x = random number between 1 and n
<		while x is not already in list[]
<
<		list[i] = x
<		}
<
<The problem is that as the list fills up with numbers, the time spent in
<the do loop getting a number not already in the list grows very large.
<
<Does anyone know of a better way to do this?  Any help would be greatly 
<appreciated!

Yes. Do this:

	n = sizeof of array
	for i = 1 to n
	   x=random number from 1 to n
           swap array[i] with array[x]
  
The idea is that what you want is _the arrray elements in a random order_
What you were doing was grabbing a random element of the array.
-- 
Leonard Erickson		...!tektronix!reed!percival!bucket!leonard
CIS: [70465,203]
"I'm all in favor of keeping dangerous weapons out of the hands of fools.
Let's start with typewriters." -- Solomon Short