Implementaion of random.shuffle
shabda raaj
shabda.raaj at gmail.com
Mon Jul 16 16:45:48 CEST 2007
On Jul 16, 5:53 pm, Steve Holden <st... at holdenweb.com> wrote:
> 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 -------------
Oh, I wasn't aware that I could see the source of all python modules.
I guess, then the implementation is correct(its just the knuth
shuffle,
moving downward), its just the doc which is in error.
Might be we should log a doc bug for this?
--Shabda
More information about the Python-list
mailing list