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

[Richard O'Keefe]

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.)