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

[Björn-Egil Dahlberg]

On 2010-05-27 05:23, Richard O'Keefe wrote:
> The code that was posted is pleasantly fast but has a
> critical defect. Suppose the input is
> [A,B,C,D, E,F,G,H]
> then the output will be
> randperm([A,B,C,D]) ++ randperm([E,F,G,H])
> or
> randperm([E,F,G,H]) ++ randperm([A,B,C,D])
> It will never interleave the two blocks.

I had a hunch and why I voiced my second concern. One can see this when 
inspecting a shuffled list with a sequence of number. Groupings will 
appear in the list and that triggered my single neuron dedicated for 
detecting order at least.

>
> The simplest method I can think of for Erlang is
>
> random_permutation(L) ->
> unwrap(lists:sort(wrap(L, [])), []).
>
> wrap([X|Xs], L) -> wrap(Xs, [{random:uniform(),X}|L]);
> wrap([], L) -> L.
>
> unwrap([{_,X}|L], Xs) -> unwrap(L, [X|Xs]);
> unwrap([], Xs) -> Xs.
>
> This is a bit slower, but it does have every possible
> permutation as a logically possible output, and under
> the usual naive assumptions about RNGs they are all
> equally likely. (Under somewhat less naive assumptions
> if you have an k-bit seed you can generate at most 2**k
> different random sequences, and if 2**k < n! not all
> permutations will really be possible. But that applies
> to anything that uses a limited number of physically
> random bits.)

Is there no need for assigning unique numbers to the list when sorting 
it? I guess it boils down to how fair we want the list to be unsorted 
(or how one wants to word it).

// Björn-Egil