Implementaion of random.shuffle

[Steve Holden]

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 -------------