erlang - recorrer - Mezclar elementos en una lista(reorganizar aleatoriamente los elementos de la lista)

listas netlogo

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 hacer esto. Entonces necesito una implementación mucho más corta. Aquí está mi implementació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.

Al ejecutarlo en shell:

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 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 la respuesta de karl es mucho más concisa y simple.

Aquí hay una solución bastante simple, aunque no necesariamente la 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 probablemente podría eliminar 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 siembras para cada llamada a uniform/1 tus resultados se vuelven sesgados (prueba con [shuffle:list([1,2,3]) || _ <- lists:seq(1, 100)] ).

Answer 2

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

main () -> shuffle (listas: seq (1, 10)).

Answer 3

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}. Ordena esta lista y descomprime las tuplas para obtener una versión mezclada de L.

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