shabda raaj wrote:
> I was going through the docs for module-random
> <http://docs.python.org/lib/module-random.html> And I came through this,
>
> * shuffle*( x[, random])
>
>
> Shuffle the sequence x in place. The optional argument random is a
> 0-argument function returning a random float in [0.0, 1.0); by
> default, this is the function random().
>
> 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.
>
> Why would we need to generate the total number of permutations for the
> list while trying to shuffle it? Should not we just use a knuth shuffle
> <http://en.wikipedia.org/wiki/Knuth_shuffle#Shuffling_algorithms> which
> does not require us to generate the total number of permutations. As
> long as len(x) is smaller than period of random number generator, a
> permutation can be generated.
>
> A quick first draft of implemetation might be,
>
> import random
>
> def shuffle(list_):
> for i in range(len(list_)):
> j = random.randint(i, len(list_)-1)
> list_[i], list_[j] = list_[j], list_[i]
> if __name__ == '__main__':
> a = range(100)
> shuffle(a)
> print a
>
> This is my first post to the list, I am not sure if this is the correct
> place to ask these questions. Please advise if this is not the correct
> place.
>
This is an excellent place to post the question. If it were to turn out
that your concerns were genuine that you might end up posting a patch to
the issue tracker and possibly then involving the developers. Until your
suspicions are confirmed, however, let the developers get on with
development.
You, like all (or most) Python users, have the source of the standard
library at your disposal. Had you looked at .../Lib/random.py you would
have found that the implementation of shuffle() reads as follows:
def shuffle(self, x, random=None, int=int):
"""x, random=random.random -> shuffle list x in place; return None.
Optional arg random is a 0-argument function returning a random
float in [0.0, 1.0); by default, the standard random.random.
"""
if random is None:
random = self.random
for i in reversed(xrange(1, len(x))):
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
x[i], x[j] = x[j], x[i]
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.
Note that there is no intent to generate all permutations of the list
and then choose one (that would indeed be a sub-optimal solution). The
documentation is only talking about whether the algorithm can in theory
produce all possible permutations of all possible input lists. It's
possible that the comment in the documentation is left over from an
earlier version. What do you think?
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
