列表中的随机元素(随机重新排列列表元素)

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.

在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]

我的动机是在STDLIB中没有这样的功能.在我游戏的某个地方,我需要洗牌,我还需要找到解决问题的最佳解决方案,而不仅仅是一个有效的解决方案.

有人可以帮助构建更短版本的解决方案吗？可能更有效率？谢谢

Answer 1

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

通过制作元组{R,X}的列表,将随机数R与L中的每个元素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)]）。