🚀 go-pugleaf

In article <BxM16o.2n@immd4.informatik.uni-erlangen.de> hrjoist@immd4.informatik.uni-erlangen.de (Holger Joist) writes:
>I think a better way is:
>
>/* initialize */
>for (i = 0; i < DECKSIZE; i++)
>	deck[i] = i;
>
>/* choose one element randomly,       */
>/* exchange it with the last element, */
>/* repeat with the rest of the deck   */
>
>for (i = DECKSIZE - 1; i >= 0; i--)
>{
>	rnd = random(i + 1);
>	x = deck[i];
>	deck[i] = deck[rnd];
>	deck[rnd] = x;
>}
>
>
>Using that  method  you  get  a  perfect  permutation.  And  this
>alorithm  works  for  every  DECKSIZE  (Asuming  random() is good
>enough) in only DECKSIZE loops.

Another advantage of this algorithm that was pointed out to me is that
it can be run incrementally.  You can do this everytime you "deal" a
card.  This greatly decreases the amount of shuffling time when you
don't deal out the whole deck (poker, blackjack, etc.).

For instance:

static pos;

int shuffle()
{
	int x;

	if (pos < 0)
		return -1;  /* meaning we reached the end */
	rnd = random_0_to_n(pos);
	x = deck[pos];
	deck[pos] = deck[rnd];
	deck[rnd] = x;
	pos--;
}

You get the idea.

Dave Roberts
Advanced Micro Devices, Inc.
Network Products Division
david.roberts@amd.com