# Difference between revisions of "RandomShuffle"

From ErlangCentral Wiki

(→Solution) | |||

Line 36: | Line 36: | ||

</code> | </code> | ||

− | [[Category:CookBook]] | + | [[Category:CookBook]][[Category:ListRecipes]][[Category:NumberRecipes]] |

## Revision as of 00:14, 4 September 2006

## Problem

For some gaming applications, e.g. Poker, we would need a fair random shuffle. There are two basics algorithms for this both described by Knuth. The more well known Knuth/Fisher-Yates shuffle is O(n) but requires destructive updates. The shuffle listed is O(n log n) but works well for any functional language.

## Solution

We associate each element in the list with a random number. The list is then sorted based on the generated number. We repeat this process log(n) times to ensure a fair shuffle.

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