Thanks for these details. BB
Tim Peters wrote: > [ Boris Borcic] >> x.sort(cmp = lambda x,y : cmp(random.random(),0.5)) >> >> pick a random shuffle of x with uniform distribution ? > > Say len(x) == N. With Python's current sort, the conjecture is true > if and only if N <= 2. > >> Intuitively, assuming list.sort() does a minimal number of comparisons to >> achieve the sort, > > No idea what that could mean in a rigorous, algorithm-independent way. > >> I'd say the answer is yes. But I don't feel quite confortable >> with the intuition... can anyone think of a more solid argumentation ? > > If a list is already sorted, or reverse-sorted, the minimum number of > comparisons needed to determine that is N-1, and Python's current sort > achieves that. It first looks for the longest ascending or descending > run. If comparison outcomes are random, it will decide "yes, already > sorted" with probability 1/2**(N-1), and likewise for reverse-sorted. > When N > 2, those are larger than the "correct" probabilities 1/(N!). > So., e.g., when N=3, the sort will leave the list alone 1/4th of the > time (and will reverse the list in-place another 1/4th). That makes > the identity and reversal permutations much more likely than "they > should be", and the bias is worse as N increases. > > Of course random.shuffle(x) is the intended way to effect a > permutation uniformly at random. -- http://mail.python.org/mailman/listinfo/python-list
