Erlang Central

RandomShuffle

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

For some gaming applications, e.g. Poker, we would need a fair random shuffle. There are two basics algorithms for this both described by Knuth. The more well known Knuth/Fisher-Yates shuffle is O(n) but requires destructive updates. The shuffle listed is O(n log n) but works well for any functional language.

Solution

We associate each element in the list with a random number. The list is then sorted based on the generated number. We repeat this process log(n) times to ensure a fair shuffle.

```
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% shuffle(List1) -> List2
%% Takes a list and randomly shuffles it. Relies on random:uniform
%%

shuffle(List) ->
%% Determine the log n portion then randomize the list.
randomize(round(math:log(length(List)) + 0.5), List).

randomize(1, List) ->
randomize(List);
randomize(T, List) ->
lists:foldl(fun(_E, Acc) ->
randomize(Acc)
end, randomize(List), lists:seq(1, (T - 1))).

randomize(List) ->
D = lists:map(fun(A) ->
{random:uniform(), A}
end, List),
{_, D1} = lists:unzip(lists:keysort(1, D)),
D1.

```