Các yếu tố xáo trộn trong danh sách (sắp xếp lại các yếu tố danh sách ngẫu nhiên)

Question

Một phần của chương trình của tôi yêu cầu tôi có thể trộn ngẫu nhiên các phần tử danh sách. Tôi cần một chức năng như vậy khi tôi đưa cho nó một danh sách, nó sẽ giả ngẫu nhiên sắp xếp lại các phần tử trong danh sách.
Thay đổi sắp xếp Phải hiển thị trong mỗi cuộc gọi có cùng danh sách.

Triển khai của tôi dường như hoạt động tốt nhưng tôi cảm thấy rằng nó khá dài và đang tăng cơ sở mã của tôi và cũng có thể, tôi có cảm giác rằng đó không phải là giải pháp tốt nhất để làm điều này. Vì vậy, tôi cần thực hiện ngắn hơn nhiều. Dưới đây là thực hiện của tôi:

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

On chạy nó trong vỏ:

 
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] 

Tôi thúc đẩy bởi một thực tế rằng trong stdlib không có chức năng như vậy. Một nơi nào đó trong trò chơi của tôi, tôi cần phải xáo trộn mọi thứ và tôi cũng cần phải tìm ra giải pháp hiệu quả nhất cho vấn đề, không chỉ là giải pháp hiệu quả.

Một số người có thể giúp xây dựng một phiên bản ngắn hơn của giải pháp không? có lẽ còn hiệu quả hơn? Cảm ơn bạn

Answer 1

Xin lưu ý rằng karl's answer ngắn gọn và đơn giản hơn nhiều.

---

Dưới đây là một giải pháp khá đơn giản, mặc dù không nhất thiết phải là hiệu quả nhất:

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

Ví dụ, một có thể có thể loại bỏ các ++ hoạt động trong nth_rest/3. Bạn không cần phải thêm thuật toán ngẫu nhiên vào mọi cuộc gọi đến random. Hạt giống nó ban đầu khi bạn bắt đầu chương trình của bạn, như vậy: random:seed(now()). Nếu bạn gieo hạt giống cho mọi cuộc gọi đến uniform/1, kết quả của bạn sẽ bị sai lệch (hãy thử với [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] 

Kết hợp số ngẫu nhiên R với từng phần tử X trong L bằng cách tạo danh sách các bộ dữ liệu {R, X}. Sắp xếp danh sách này và giải nén các tuples để có được một phiên bản xáo trộn của 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). 

main() -> ngẫu nhiên (danh sách: seq (1, 10)).