Three dumb questions (ordered by dumbness descending)

[Bernhard Herzog]

Alex Martelli <aleax at aleax.it> writes:

> Once you do have a random or pseudo-random generator that fully
> satisfies you, Ian Bicking's snippet reimplementing shuffle as a
> Decorate-Sort-Undecorate idiom is truly excellent -- a little jewel,
> IMHO, despite the little typo in it.  It does, alas, end up a
> little slower than Tim Peters' original -- but losing a speed
> competition to Tim is no shame, and Ian's version only loses very
> very little indeed.  To wit (having corrected Ian's typo):
[...]
> def shuffle_ian(x):
>     newList = [(random(), i) for i in x]
>     newList.sort()
>     x[:] = [i[1] for i in newList]

What's missing, though, is a proof that shuffle_ian produces each
possible permutation with the same probability (assuming random() has
suitable properties)

One problem I can see is that there's a non-zero chance that there will
be at least two equal random numbers in newList in which case the
corresponding values of x are used to sort newList. This skews the
probabilities and furthermore means that shuffle_ian can only shuffle
lists whose items can be ordered which among others exludes complex
numbers.

   Bernhard

-- 
Intevation GmbH                 http://intevation.de/ 
Sketch                          http://sketch.sourceforge.net/ 
MapIt!                          http://mapit.de/