Unsorting(randomizing) a sequence
Charles G Waldman
cgw at fnal.gov
Thu Aug 19 17:58:31 CEST 1999
> > ...
> > 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.
Thanks for the labor-savings. The point I was getting at however was
that even with a perfect random number generator, if you're not
careful, you can write a function to turn those random numbers into
permutations which does not evenly distribute across the space of
permutations - for example favoring even permutations over odd
permutations, etc. The goodness of the random-number generator is
I really should go off and read more Knuth; as Dan Schmidt pointed out
all of this is discussed there; rather than devising clever
statistical tests, it's far better to *prove* from first principles
that the algorithm is correct.
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