[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