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."