[erlang-questions] Speedy unsort:shuffle/1,2 ?
Richard O'Keefe
<>
Thu May 27 05:23:33 CEST 2010
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.
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.)
More information about the erlang-questions
mailing list