Unsorting(randomizing) a sequence
Dan Schmidt
dfan at harmonixmusic.com
Wed Aug 18 10:03:50 EDT 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
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/
More information about the Python-list
mailing list