# [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.

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

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.

```