Unsorting(randomizing) a sequence

Tim Peters tim_one at email.msn.com
Wed Aug 18 03:20:23 CEST 1999


[Charles G Waldman, making heroic efforts to test the quality of
 random-permutation algorithms]
> ...
> Another, more straightforward way to test sampling strategies is just
> to keep track of how many times each permutation comes up.  However,
> since N! gets so large, it takes too long to build up decent
> statistics this way.

I'll save you a near-infinity of work, then <wink>:  Python's Wichmann-Hill
uniform generator has a period of around 1e12 to 1e13.  Since the point at
which you begin in the period completely determines the permutation that
will be generated, you can't get more than 1e13 distinct permutations out of
it.  So a sequence of length 16 is the longest for which it could even
conceivably produce all permutations; if you use it to, e.g., shuffle a deck
of cards, the number of permutations any algorithm based on WH can get back
is a vanishingly small fraction of the possibilities (since 52! ~= 1e66; we
can only get back at most 1 of each 1e66/1e13 = 1e53 possibilities).

So, in a real sense, even the best possible algorithm based on
random.random() is terrible, incapable of generating "almost all" of the
space for a measly deck of cards.

It's surprising that so few people get disturbed by this; but it's even more
surprising that some people do <wink>.

the-deck-is-always-rigged-in-subtle-ways-ly y'rs  - tim






More information about the Python-list mailing list