random shuffles

[bryanjugglercryptographer at yahoo.com]

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.

You would be mistaken (except for the trivial case of 2 elements).

In m uniform, independant, random 2-way choices, there are 2**m
equally probable outcomes. We can map multiple random outcomes
to the same final output, but each will still have probability of the
form
n/2**m, where n is an integer.

A random permutation requires that we generate outputs with
probability 1/(n!). For n>2, we cannot reach the probability using a
limited number of 2-way choices.


Have you ever looked at the problem of making a perfectly uniform
1-in-3 choice when the only source of randomness is a perfect random
bit generator? The algorithms terminate with probability 1, but are
non-terminators in that there is no finite number of steps in which
they must terminate.


-- 
--Bryan