Subject: Re: small hack
To: Bill Studenmund <skippy@macro.stanford.edu>
From: Andrew Brown <twofsonet@graffiti.com>
List: tech-userlevel
Date: 09/23/1998 12:20:14
>> X	/*
>> X	 * This algorithm taken from Knuth, Seminumerical Algorithms,
>> X	 * page 139.
>> X	 */
>> X	for (j = 0; j < t; j++) {
>> X		k = random()%t;
>> X		temp = shuffle[j];
>> X		shuffle[j] = shuffle[k];
>> X		shuffle[k] = temp;
>> X	}
>
>According to an algorythm book I've got (at home, can get reference), this
>shuffle routine isn't that great. As j progresses, it might unshuffle some
>swaps, giving a slight preference to the initial dataset.
>
>A better way to do it is either
>
>k=j + (random()%(t-j));
>
>or do the loop from t-1 to 0, and have k=random()%(j+1).

and if you were feeling short on storage, or just obscure, you could
always replace the three assigments with the temporary with either

	shuffle[j]^=shuffle[i]^=shuffle[j]^=shuffle[i];

which would be fine, since you're using integers, or, if you decide
you want something that's non-type specific (ie, work with floats
too), you'd have to use

	shuffle[i]=-(shuffle[i]-=shuffle[j])+(shuffle[j]+=shuffle[i]);

but that'd just be silly.  :)

-- 
|-----< "CODE WARRIOR" >-----|
codewarrior@daemon.org             * "ah!  i see you have the internet
twofsonet@graffiti.com (Andrew Brown)                that goes *ping*!"
warfare@graffiti.com      * "information is power -- share the wealth."