Перемешивание элементов в списке (произвольно перегруппируйте элементы списка)

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

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

-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 такой функции нет. Где-то в моей игре мне нужно перетасовать вещи, а также мне нужно найти лучшее эффективное решение проблемы, а не только то, что работает. Может ли кто-нибудь помочь построить более короткую версию решения? вероятно, еще более эффективен? Спасибо вам

Ответы

Ответ 1

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

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

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

Ответ 2

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>

Ответ 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).

Основной() →   shuffle (списки: seq (1, 10)).