Home > Erlang > Shuffle a list (deck)

Shuffle a list (deck)


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: , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: