[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Håkan Huss]

On Thu, May 27, 2010 at 11:52, Johan Montelius <johanmon@REDACTED> wrote:
>
>> Contrast this with the version that takes into account the length of both
>> lists.
>>
>> Julian
>
> Very interesting, I didn't think about that. The same problem does not occur
> in my qsort version does it?
>
Actually, the same problem will occur for any version that uses only
unbiased coin-flips. To see why, construct a decision tree where every
internal node splits according to the outcome of a coin flip. The
leaves of this tree will then be the permutation generated by that
sequence of coin flips. Now, the probability of getting each
permutation is 1/2 to the m:th power, where m is the length of the
path to the permutation from the root. In order for the shuffle to be
fair, these must be equal, which means that the tree must be full and
complete. However, since there are n! possible permutations, this can
only happen if n! = 2^m, which is not the case (unless n<=2).

Regards,
/Håkan