RandomShuffle

From Erlang Community

(Difference between revisions)
Revision as of 15:11, 28 August 2006 (edit)
213.171.204.166 (Talk)
(Random Shuffle)
← Previous diff		 Revision as of 15:14, 28 August 2006 (edit) (undo)
213.171.204.166 (Talk)
(→Solution)
Next diff →
Line 14: Line 14:
%% Takes a list and randomly shuffles it. Relies on random:uniform %% Takes a list and randomly shuffles it. Relies on random:uniform
%% %%
 +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
shuffle(List) -> shuffle(List) ->

Revision as of 15:14, 28 August 2006

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