Unsorting(randomizing) a sequence

[Dan Schmidt]

Charles G Waldman <cgw at fnal.gov> writes:

| Dan Schmidt writes:
|  > 
|  > Skip's method is fine if choice is allowed to equal i.  With that
|  > change, element exchange is no longer forced.  You can prove that
|  > it's a perfect shuffle by induction: the last element in the
|  > shuffled sequence has an equal chance of being any of the
|  > original elements, and so on.
| 
| Correct.  However, I'm curious, what is the definition of a "perfect
| shuffle"?  Just that each element of the permuted sequence has an
| equal chance of being any of the original elements?

Nope, you need to show that all permutations are equally probable.

| As I tried to point out in my earlier posting, there are plenty of
| ways of choosing permutations for which this condition holds, but
| still don't uniformly sample the symmetric group (set of all
| permutations).

You use induction.

We assume as the induction hypothesis that the method can randomize
n-1 elements perfectly.

Now, to randomize n elements, we pick one perfectly randomly to put in
the final spot, and randomize perfectly the other spots (by the
induction hypothesis).

There's a more formal discussion in Knuth, The Art of Computer Programming
vol. 2, sections 3.4.2 (algorithm P) and 3.3.2 (algorithm P).

-- 
                 Dan Schmidt -> dfan at harmonixmusic.com, dfan at alum.mit.edu
Honest Bob & the                http://www2.thecia.net/users/dfan/
Factory-to-Dealer Incentives -> http://www2.thecia.net/users/dfan/hbob/
          Gamelan Galak Tika -> http://web.mit.edu/galak-tika/www/