Xref: utzoo comp.sources.wanted:7434 alt.msdos.programmer:50
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!daitc!jmorton
From: jmorton@daitc.daitc.mil (Joe Morton)
Newsgroups: comp.sources.wanted,alt.msdos.programmer
Subject: Re: Need algorithm to scramble order of array
Message-ID: <524@daitc.daitc.mil>
Date: 18 May 89 03:56:59 GMT
References: <3008@cps3xx.UUCP>
Reply-To: jmorton@daitc.daitc.mil (Joe Morton)
Followup-To: comp.sources.wanted
Organization: DTIC Special Projects Office (DTIC-SPO), Alexandria VA
Lines: 57

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
>		}

I read this one in Byte quite a few years ago - I _may_ have used it
once, and I unfortunately don't remember how well it worked.  Now that
the disclaimers have been dispensed with, here's the code:

	n = size of array

	for i = 1 to n {
	    list[ i ] = i ;
	}

	for i = 1 to n {
	    swap( list[ i ] , list[ random( n ) ] ) ; /* CALL BY REFERENCE */
	}

/* random( n ) returns random number between 1 and n */

If I'm guessing correctly, the original code is O(n^2) (or at least
degenerates to worse) and the code above is O(n).  The math for (1) is
ugly, and I don't understand it very well, but I'll answer e-mail
requests for how I arrived at that estimate.

To complete the code, here's a really neat swap routine, in C:

swap( a , b )
unsigned *a, *b;
{
    *a ^= *b ;
    *b ^= *a ;
    *a ^= *b ;
}

Try it - it works!  (for the non-C programmers, the Pascal equivalent to
*a ^= *b is a := a xor b, and a and b are "var" parameters).

Hope this helps.

DISCLAIMER:  Any code presented here is guaranteed to be as correct as
	     anything you'd pay for.

	     The opinions expressed here are not those of CDC or the
	     DTIC-SPO.