2012-01-11 1 views
11

Parte del mio programma mi richiede di essere in grado di mescolare casualmente gli elementi dell'elenco. Ho bisogno di una funzione tale che quando gli do una lista, essa riorganizzerà in modo pseudo-casuale gli elementi nella lista.
Un cambio di accordo È necessario essere visibile ad ogni chiamata con lo stesso elenco.

La mia implementazione sembra funzionare bene ma sento che è piuttosto lunga e sta aumentando la mia base di codice e inoltre, ho la sensazione che non sia la soluzione migliore per farlo. Quindi ho bisogno di un'implementazione molto più breve. Qui è la mia realizzazione:Riproduzione casuale di elementi in un elenco (riordinamento casuale degli elementi di elenco)

 
-module(shuffle). 
-export([list/1]). 
-define(RAND(X),random:uniform(X)). 
-define(TUPLE(Y,Z,E),erlang:make_tuple(Y,Z,E)). 

list(L)->  
    Len = length(L), 
    Nums = lists:seq(1,Len),  
    tuple_to_list(?TUPLE(Len,[],shuffle(Nums,L,[]))). 

shuffle([],_,Buffer)-> Buffer; 
shuffle(Nums,[Head|Items],Buffer)-> 
    {Pos,NewNums} = pick_position(Nums),  
    shuffle(NewNums,Items,[{Pos,Head}|Buffer]). 

pick_position([N])-> {N,[]}; 
pick_position(Nos)-> 
    T = lists:max(Nos), 
    pick(Nos,T). 

pick(From,Max)-> 
    random:seed(begin 
        (case random:seed(now()) of 
         undefined -> 
          NN = element(3,now()), 
          {?RAND(NN),?RAND(NN),?RAND(NN)}; 
         Any -> Any 
        end) 
       end 
       ), 
    T2 = random:uniform(Max), 
    case lists:member(T2,From) of 
     false -> pick(From,Max); 
     true -> {T2,From -- [T2]} 
    end. 

Su eseguirlo in guscio:

 
F:\> erl 
Eshell V5.8.4 (abort with ^G) 
1> c(shuffle). 
{ok,shuffle} 
2> shuffle:list([a,b,c,d,e]). 
[c,b,a,e,d] 
3> shuffle:list([a,b,c,d,e]). 
[e,c,b,d,a] 
4> shuffle:list([a,b,c,d,e]). 
[a,b,c,e,d] 
5> shuffle:list([a,b,c,d,e]). 
[b,c,a,d,e] 
6> shuffle:list([a,b,c,d,e]). 
[c,e,d,b,a] 
Sono motivato dal fatto che nel stdlib non c'è tale funzione. Da qualche parte nel mio gioco, ho bisogno di mescolare le cose e ho anche bisogno di trovare la migliore soluzione efficace al problema, non solo quella che funziona.

Qualcuno potrebbe contribuire a creare una versione più breve della soluzione? probabilmente ancora più efficiente? Grazie

risposta

4

Si prega di notare che karl's answer è molto più conciso e semplice.


Ecco una soluzione abbastanza semplice, anche se non necessariamente la più efficiente:

-module(shuffle). 

-export([list/1]). 

list([])  -> []; 
list([Elem]) -> [Elem]; 
list(List) -> list(List, length(List), []). 

list([], 0, Result) -> 
    Result; 
list(List, Len, Result) -> 
    {Elem, Rest} = nth_rest(random:uniform(Len), List), 
    list(Rest, Len - 1, [Elem|Result]). 

nth_rest(N, List) -> nth_rest(N, List, []). 

nth_rest(1, [E|List], Prefix) -> {E, Prefix ++ List}; 
nth_rest(N, [E|List], Prefix) -> nth_rest(N - 1, List, [E|Prefix]). 

Ad esempio, si potrebbe probabilmente fare a meno l'operazione ++ in nth_rest/3. Non è necessario effettuare il seeding dell'algoritmo casuale in ogni chiamata a random. Inizialo inizialmente quando inizi il tuo programma, in questo modo: random:seed(now()). Se lo si semina per ogni chiamata a uniform/1 i risultati diventano distorti (prova con [shuffle:list([1,2,3]) || _ <- lists:seq(1, 100)]).

+0

Grazie @Adam ottima soluzione. Lo adoro –

+0

ciao. Posso aggiungere che devi seminare prima di usare 'random: uniform'? altrimenti si otterranno gli stessi risultati in diverse esecuzioni della VM e in molte applicazioni questo non è voluto. – user601836

+0

@ user601836 Buon punto! Nota che devi farlo solo una volta per processo, e non per ogni esecuzione di 'shuffle: list/1'. –

68
1> L = lists:seq(1,10). 
[1,2,3,4,5,6,7,8,9,10] 

Associare un numero casuale R a ogni elemento X in L creando un elenco di tuple {R, X}. Ordina questo elenco e decomprimere le tuple per ottenere una versione mescolate di L.

1> [X||{_,X} <- lists:sort([ {random:uniform(), N} || N <- L])]. 
[1,6,2,10,5,7,9,3,8,4] 
2>  
+0

Votato !, amo anche questo! Grazie @karl –

+0

Questo metodo di riproduzione casuale produce risultati distorti a meno che tu non possa garantire che non vengano generati numeri casuali duplicati (che non puoi con 'casuale: uniforme/0'. – jvf

1
-module(shuffle). 

-compile(export_all). 

shuffle(L) -> 
    shuffle(list_to_tuple(L), length(L)). 

shuffle(T, 0)-> 
    tuple_to_list(T); 
shuffle(T, Len)-> 
Rand = random:uniform(Len), 
A = element(Len, T), 
B = element(Rand, T), 
T1 = setelement(Len, T, B), 
T2 = setelement(Rand, T1, A), 
shuffle(T2, Len - 1). 

principali() -> riordino (liste: seq (1, 10)).

+0

grazie @BlackMamba –

Problemi correlati