Three dumb questions (ordered by dumbness descending)

[Alex Martelli]

Bernhard Herzog wrote:
        ...
>> 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)

Among the "suitable properties" would be to have random() return
real numbers -- thus the probability of two equal numbers in N
calls becomes 0 -- or come from a pseudo-random generator arranged in a
plain/usual way so that it will never return two identical numbers
until you use up its cycle (e.g. a typical linear-congruential one).


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

Good point, of course -- an arbitrary pseudo-random (or HW random)
generator returning output with a finite number of bits DOES have a
non-0 chance of a duplicate, in general -- e.g., (1-2**53)**N prob of
no problems if 53 bits differ significantly and you generate N+1
truly-random numbers.


Alex