random shuffles

[Peter Otten]

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. But I don't feel quite
> confortable with the intuition... can anyone think of a more solid
> argumentation ?

Anecdotal evidence suggests the answer is no:

>>> histo = {}
>>> for i in xrange(1000):
...     t = tuple(sorted(range(3), lambda x, y: cmp(random.random(), 0.5)))
...     histo[t] = histo.get(t, 0) + 1
...
>>> sorted(histo.values())
[60, 62, 64, 122, 334, 358]

versus:

>>> histo = {}
>>> for i in xrange(1000):
...     t = tuple(sorted(range(3), key=lambda x: random.random()))
...     histo[t] = histo.get(t, 0) + 1
...
>>> sorted(histo.values())
[147, 158, 160, 164, 183, 188]

Peter