RandomShuffle

From Erlang Community

Revision as of 15:14, 28 August 2006 by 213.171.204.166 (Talk)

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.
Retrieved from "http://www.trapexit.org/RandomShuffle"
Erlang/OTP Projects
Personal tools