Hrvoje Niksic wrote: > Steve Holden <[EMAIL PROTECTED]> writes: > >> So it would appear that the developers chose the Knuth algorithm >> (with a slight variation) for *their* implementation. Now you have >> to ask yourself whether your surmise is genuinely correct (in which >> case the documentation may contain a bug) or whether the >> documentation is indeed correct and you are in error. > > That is a good question. The random module uses the Mersenne twister, > which has a repetition period of 2**19937. The number of n-sized > permutations of a list with n elements is n!, while each shuffle > requires n calls to the PRNG. This means that to be able to generate > all permutations, the PRNG must have a period of at least n! * n. In > the case of MT, it means that, regarding the period, you are safe for > lists with around 2079 elements. shuffle's documentation may have > been written before the random module was converted to use the MT. > > 2**19937 being a really huge number, it's impossible to exhaust the > Mersenne twister by running it in sequence. However, there is also > the question of the spread of the first shuffle. Ideally we'd want > any shuffle, including the first one, to be able to produce any of the > n! permutations. To achieve that, the initial state of the PRNG must > be able to support at least n! different outcomes, which means that > the PRNG must be seeded by at least log2(n!) bits of randomness from > an outside source. For reference, Linux's /dev/random stops blocking > when 64 bits of randomness are available from the entropy pool, which > means that, in the worst case, shuffling more than 20 elements cannot > represent all permutations in the first shuffle!
Thanks for this thoughtful analysis. I believe we can therefore leave the documentation (which almost certainly *was* written before the adoption of MT) alone for now. regards Steve -- Steve Holden +1 571 484 6266 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenweb http://del.icio.us/steve.holden --------------- Asciimercial ------------------ Get on the web: Blog, lens and tag the Internet Many services currently offer free registration ----------- Thank You for Reading ------------- -- http://mail.python.org/mailman/listinfo/python-list
