Erlang shuffle

Torbjorn Tornkvist <>
Fri Aug 25 09:55:36 CEST 2006


Nice!

I suggest you add it to the Cookbook at trapexit.org.

Cheers, Tobbe


 wrote:
> Found myself needing a fair random shuffle function. Hopefully this is useful to someone else. Its O(n log n), i.e. not as fast as Fisher-Yates shuffle, assuming lists:keysort is O(n).  
> 
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> %%
> %% 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.
> 
> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
> 
> Regards
> 
> t
> 




More information about the erlang-questions mailing list