[erlang-questions] Fisher-Yates shuffle in Erlang

Andreas Bakurov <>
Sun Jun 10 15:36:07 CEST 2007


This is a Fisher-Yates shuffle in Erlang.
http://www.nist.gov/dads/HTML/fisherYatesShuffle.html

It uses list->tuple->list transform for swapping (zip->unzip methods).

If you find some bugs, please tell me about it.
The problem with my implementation is that it is not tail recursive.

----------------------------------------------------------------------
All this mess is because I'm skeptical about the implementation given in:
http://wiki.trapexit.org/index.php/RandomShuffle

if it is 'fair' shuffler, e.g. each possible permutation has equal 
probability to be an outcome.
For n elements of list the number of different permutations is n! hence 
the probability of each permutation is 1/n! .

Fisher-Yates algorithm is fair (if you don't consider random number 
generation process)
----------------------------------------------------------------------

shuffle([]) ->
    [];

shuffle([E]) ->
    [E];

shuffle(List) ->
    G = round(random:uniform() * (length(List) - 1)) + 1,   % 1-based 
indexing of elements
    [N|R] = swap_elements(1, G, List),
    [N|shuffle(R)].  % not tail recursive


% Swap element on position A with B
swap_elements(Ida, Idb, List) when Ida == Idb ->
    List;

swap_elements(Ida, Idb, List) ->
    Z = lists:zip(lists:seq(1, length(List)), List),
    {_, A} = lists:keysearch(Ida, 1, Z),
    {_, B} = lists:keysearch(Idb, 1, Z),
    {_, Result} = lists:unzip(lists:keyreplace(Ida, 1, 
lists:keyreplace(Idb,1, Z, A) , B)),
    Result.



More information about the erlang-questions mailing list