On Jul 16, 5:53 pm, Steve Holden <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
