Перетасовывание элементов в списке (случайное изменение порядка элементов списка)

Question

Часть моей программы требует, чтобы я мог произвольно перемешивать элементы списка. Мне нужна такая функция, чтобы, когда я предоставляю ей список, она псевдослучайно переупорядочивает элементы в списке.
Изменение в расположении Должно быть видимым при каждом вызове с одним и тем же списком. ,

Моя реализация, кажется, работает просто отлично, но я чувствую, что она довольно длинная и увеличивает мою кодовую базу, а также у меня ощущение, что это не лучшее решение для этого. Так что мне нужна гораздо более короткая реализация. Вот моя реализация:

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

При запуске в оболочке:

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]

Меня мотивирует тот факт, что в STDLIB такой функции нет. Где-то в моей игре мне нужно все перемешать, а также мне нужно найти лучшее эффективное решение проблемы, а не только то, которое работает.

Может ли кто-нибудь помочь создать более короткую версию решения? наверное еще эффективнее? Спасибо

Answer 1

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

Свяжите случайное число R с каждым элементом X в L, составив список кортежей {R, X}. Сортируйте этот список и распакуйте кортежи, чтобы получить перемешанную версию L.

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

Answer 2

Обратите внимание, что ответ Карла гораздо более лаконичен и прост.

---

Вот довольно простое решение, хотя и не обязательно самое эффективное:

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

Например, можно было бы покончить с операцией ++ в nth_rest/3. Вам не нужно заполнять случайный алгоритм при каждом вызове random. Сначала запустите программу при запуске программы, например: random:seed(now()). Если вы заполняете его при каждом вызове uniform/1, ваши результаты становятся искаженными (попробуйте [shuffle:list([1,2,3]) || _ <- lists:seq(1, 100)]).

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 () -> shuffle (списки: seq (1, 10)).