Implementaion of random.shuffle

[shabda raaj]

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