[erlang-questions] Fisher-Yates shuffle in Erlang

Andreas Bakurov andreasmk2@REDACTED
Sun Jun 10 15:36:07 CEST 2007

This is a Fisher-Yates shuffle in Erlang.

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:

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]) ->

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 ->

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)),

More information about the erlang-questions mailing list