New submission from David Benbennick:
Since Python 2.1 [1], when random.shuffle was added, the documentation has said:
"""Note that for even rather small len(x), the total number of permutations of
x is larger than the period of most random number generators; this implies that
most permutations of a long sequence can never be generated."""
This comment is incorrect and misleading. In fact, I claim that shuffle can
produce "all" permutations for any representable sequence.
To shuffle a sequence of length N requires log(N!) ~ N * log(N/e) bits of
randomness [2]. The random module provides a generator with "a period of
2**19937-1", meaning you can get 2**19937 bits of randomness out of it before
it starts repeating.
All of which is to say that any representable sequence, say N < 2**50, will
need no more than 2**60 bits of randomness to shuffle. That is well within the
period of the random number generator.
Attached is a patch that deletes the comment.
An illustration of this misconception is at [3].
1: http://docs.python.org/release/2.1/lib/module-random.html
2:
https://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n
3:
http://stackoverflow.com/questions/3062741/maximal-length-of-list-to-shuffle-with-python-random-shuffle
--
assignee: docs@python
components: Documentation
files: mywork.patch
keywords: patch
messages: 196971
nosy: dbenbenn, docs@python
priority: normal
severity: normal
status: open
title: Remove misleading documentation for random.shuffle
Added file: http://bugs.python.org/file31593/mywork.patch
___
Python tracker
<http://bugs.python.org/issue18928>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
