Unsorting(randomizing) a sequence
Dan Schmidt
dfan at harmonixmusic.com
Wed Aug 18 16:03:50 CEST 1999
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
n1 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/
FactorytoDealer Incentives > http://www2.thecia.net/users/dfan/hbob/
Gamelan Galak Tika > http://web.mit.edu/galaktika/www/
More information about the Pythonlist
mailing list