Riproduzione casuale di elementi in un elenco (riordinamento casuale degli elementi di elenco)

Question

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:

 
-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

Answer 1

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)]).

Answer 2

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>  

Answer 3

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