Xref: utzoo comp.sources.wanted:7424 alt.msdos.programmer:46
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!decwrl!sun-barr!apple!rutgers!njin!princeton!notecnirp!ahw
From: ahw@notecnirp.Princeton.EDU (Arthur Watson)
Newsgroups: comp.sources.wanted,alt.msdos.programmer
Subject: Re: Need algorithm to scramble order of array
Message-ID: <17132@princeton.Princeton.EDU>
Date: 17 May 89 20:31:32 GMT
References: <3008@cps3xx.UUCP> <11998@grebyn.COM>
Sender: news@princeton.Princeton.EDU
Reply-To: ahw@notecnirp.UUCP (Arthur Watson)
Organization: Dept. of Computer Science, Princeton University
Lines: 25

In article <3008@cps3xx.UUCP> reedp@frith.egr.msu.edu () writes:
>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!


Assume you have the array arr[0..MAX-1] filled with your unscrambled numbers.

Now just do the following (with integer variables j and k):

	for j := 0 to MAX-1 do begin
		k := a random number between j and MAX-1 inclusive;
		swap arr[j] and arr[k];
	end;

This makes all scramblings equally likely, which you presumably want,
(since for each array location you are selecting randomly among those
elements not yet selected)
and is the most efficient way to do so
(since you only move each array element once [well, twice] :-)).

--
Arthur Watson