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

[Julian Tibble]

Apologies, the e-mail below did not get through to the list the first
time I sent it.

------------------

> Why use the length of the list? What is the advantage of using a coin-flip?
>
> randmerge([], L2) ->
>   L2;
> randmerge(L1, []) ->
>   L1;
> randmerge(L1, L2) ->
>   case random:uniform(2) of
>       1 ->
>           [hd(L1) | randmerge(tl(L1), L2)];
>       2 ->
>           [hd(L2) | randmerge(L1, tl(L2))]
>   end.

The function "randmerge(L,R)" should be fair - that is, it should
produce all interleavings of L and R with equal likelihood, but this
is not true with the coin-flip version.

To see why, consider computing randmerge([1,3], [2,4])
At each step, randmerge can choose the left list or the right list.
Therefore the choices are:

L L - 1,3,2,4
L R L - 1,2,3,4
L R R - 1,2,4,3
R L L - 2,1,3,4
R L R - 2,1,4,3
R R - 2,4,1,3

(note, after "L L" the left list is empty so there is no further random choice.
 similarly for "R R")

When using a coin-flip, the top and bottom cases both have probability
1/4. All the other cases have probability 1/8. Therefore randmerge is
not fair.

Contrast this with the version that takes into account the length of both lists.

Julian