random shuffles

[Tim Peters]

[ 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.