Unsorting(randomizing) a sequence
Chad Netzer
chad at vision.arc.nasa.gov
Thu Aug 19 21:42:32 EDT 1999
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. :-)
More information about the Python-list
mailing list