Unsorting(randomizing) a sequence

[Chad Netzer]

Christopher Browne wrote:

> Is it so much work to come up with a half-reasonable card shuffling
> algorithm?

Well, let's see...

> The one I've always seen cited as providing decent behaviour looks
> thus:
>
> for (i = 0; i > n; i++) {
>    swap (item[i], item[random(n)]);
> }

A list of n items has n! permutations.  The algorithm you propose will
generate  n**n possible execution paths (for lack of a better term), which
is not evenly divisible by n! .  So your variation does not produce all
possible
permutations with equal probability.

The solution posted previously by Dan Schmidt, should work (I'll translate
to C pseudocode to match the above form):

for (i = n; i > 0; i--)
{
  j = i -1;
  swap(item[j], item[random(j)]); /* choose from remaining items in list */
}

The basic difference is that the second approach, after placing
a random item in a slot, only allows the remaining items to
be eligible for the remaining slots.  Think of it as randomly
picking cards from a deck to create a new shuffled deck.

Chad Netzer

PS.  if I f*cked up, be gentle. :-)