Mezclar elementos en una lista (reorganizar elementos de la lista aleatoriamente)

Question

Parte de mi programa requiere que pueda barajar aleatoriamente los elementos de la lista. Necesito una función tal que cuando le doy una lista, reorganice pseudoaleatoriamente los elementos en la lista.
Un cambio en la disposición Debe ser visible en cada llamada con la misma lista.

Mi implementación parece funcionar bien, pero creo que es bastante larga y está aumentando mi base de códigos y, además, tengo la sensación de que no es la mejor solución para hacerlo. Entonces necesito una implementación mucho más corta. Aquí está mi aplicación:

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

En ejecutarlo con cáscara:

 
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] 

Estoy motivado por el hecho de que en el stdlib no existe tal función. En algún lugar de mi juego, necesito mezclar las cosas y también necesito encontrar la mejor solución eficiente para el problema, no solo una que funcione.

¿Podría alguien ayudar a construir una versión más corta de la solución? probablemente aún más eficiente? Gracias

Answer 1

Tenga en cuenta que karl's answer es mucho más conciso y simple.

---

he aquí una solución bastante simple, aunque no necesariamente el más eficiente:

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

Por ejemplo, uno podría probablemente acabar con la operación ++ en nth_rest/3. No necesita sembrar el algoritmo aleatorio en cada llamada al random. Inícielo inicialmente cuando inicie su programa, así: random:seed(now()). Si lo semilla para cada llamada a uniform/1 sus resultados se vuelven sesgados (intente 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] 

Asociar un número aleatorio R con cada elemento X en L haciendo una lista de tuplas {R, X}. Ordenar esta lista y desempaquetar las tuplas para obtener una versión barajado de 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). 

principales() -> de reproducción aleatoria (listas: ss (1, 10)).