Unsorting(randomizing) a sequence

[Tim Peters]

[Christopher Browne]
> Is it so much work to come up with a half-reasonable card shuffling
> algorithm?
>
> The one I've always seen cited as providing decent behaviour looks
> thus:
>
> for (i = 0; i > n; i++) {  /* surely intended "i < n" */
>    swap (item[i], item[random(n)]);
> }

[Chad Netzer]
> 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.
> ...
> PS.  if I f*cked up, be gentle. :-)

No, that was an excellent argument, Chad!  Cut straight to the heart of it
with no need to think <wink>.  For n=1 and n=2, Christopher's algorithm
works fine, and for all n the *last* position in the generated permutations
has the right distribution.  For all other cases, the output element at
position i is most likely to be the element that was at input position i+1.

I think this algorithm persists because it's obvious that, on the i'th step,
every element has an equal chance of ending up at position i.  So, by
induction <wink>, all permutations are equally likely in the end.  That
argument doesn't make sense, but the flaw is hard to see.

Hint for the curious:  after the first step, every element is indeed equally
likely to be in the first position.  After the second step, the same is true
of the second position.  But after the second step it's no longer true that
every element is *still* equally likely to be in the first position; in
fact, there are n ways for the original first element to be unchanged (one
of which swaps it twice), 2*n-2 ways for the original second element to be
in the first position after the second step, and n-1 ways for each of the
remaining n-2 elements.

asymmetry-hides-in-symmetry-like-tears-in-the-rain-ly y'rs  - tim