Boris Borcic wrote: > does > > x.sort(cmp = lambda x,y : cmp(random.random(),0.5)) > > pick a random shuffle of x with uniform distribution ? > > Intuitively, assuming list.sort() does a minimal number of comparisons to > achieve the sort, I'd say the answer is yes.
You would be mistaken (except for the trivial case of 2 elements). In m uniform, independant, random 2-way choices, there are 2**m equally probable outcomes. We can map multiple random outcomes to the same final output, but each will still have probability of the form n/2**m, where n is an integer. A random permutation requires that we generate outputs with probability 1/(n!). For n>2, we cannot reach the probability using a limited number of 2-way choices. Have you ever looked at the problem of making a perfectly uniform 1-in-3 choice when the only source of randomness is a perfect random bit generator? The algorithms terminate with probability 1, but are non-terminators in that there is no finite number of steps in which they must terminate. -- --Bryan -- http://mail.python.org/mailman/listinfo/python-list