Archive

Posts Tagged ‘fisher’

Shuffle a list (deck)

October 27, 2009 Leave a comment

Dopo che avete creato un mazzo di carte per un qualsiasi gioco voi stiate implementando, si pone il problema di mescolare tale mazzo, in modo da ottenere una versione dello stesso in cui le carte non siano piu ordinate per valore e seme, ma seguano un ordine casuale.

Dopo essermi sbattuto un po su google, ho trovato un paio di risorse: un algoritmo da seguire in questi casi, il FISHER-YATES (Knuth shuffle) e un po di codice gia implementato dai simpatici ragazzi di TRAP-EXIT e LITERATEPROGRAMS.

Dopo aver letto entrambi gli articoli sono arrivato al seguente codice, ottenuto dal codice di TRAP-EXIT modificando alcuni nomi di variabile:

shuffle(Deck) ->
   randomize(round(math:log(length(Deck)) + 0.5), Deck).

randomize(1, Deck) ->
   randomize(Deck);

randomize(T, Deck) ->
   lists:foldl(fun(_E, Acc) ->
                  randomize(Acc)
               end, randomize(Deck), lists:seq(1, (T - 1))).

randomize(Deck) ->
   D = lists:map(fun(A) ->
                    {random:uniform(), A}
             end, Deck),
   {_, D1} = lists:unzip(lists:keysort(1, D)),
   D1.

La complessita asintotica di tale codice viene quantificata come O(n log n).

A seguire il codice di LITERATE PROGRAMS, come potete vedere questa implementazione appare molto piu compatta…

shuffle(Deck) -> shuffle(Deck, []).

shuffle([], Acc) -> Acc;

shuffle(Deck, Acc) ->
  {Leading, [H | T]} = lists:split(random:uniform(length(Deck)) - 1, Deck),
  shuffle(Leading ++ T, [H | Acc]).

In questo caso il risultato della complessita asintotica appare essere O(n)….
Ora sta a voi decidere quale implementazione usare…o se farvene una vostra…e ricordate di passare nei siti da cui ho tratto i codici listati sopra!

 

Categories: Erlang Tags: , , ,