Three dumb questions (ordered by dumbness descending)
Bernhard Herzog
bh at intevation.de
Tue Sep 24 14:36:50 CEST 2002
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/
More information about the Python-list
mailing list