Subject: Re: small hack
To: Perry E. Metzger <perry@piermont.com>
From: Bill Studenmund <skippy@macro.stanford.edu>
List: tech-userlevel
Date: 09/22/1998 17:28:15
On 22 Sep 1998, Perry E. Metzger wrote:

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

Take care,

Bill