[ 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
