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		 Current revision (00:14, 4 September 2006) (edit) (undo)
Bfulgham (Talk | contribs)

 
(One intermediate revision not shown.)
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) ->
Line 35: Line 36:
</code> </code>
-[[Category:CookBook]]+[[Category:CookBook]][[Category:ListRecipes]][[Category:NumberRecipes]]

Current revision

[edit] 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.

[edit] 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