Shuffling Elements in a List (randomly re-arrange

问题:

Part of my program requires me to be able to randomly shuffle list elements. I need a function such that when i give it a list, it will pseudo-randomly re-arrange the elements in the list.
A change in arrangement Must be visible at each call with the same list.

My implementation seems to work just fine but i feel that its rather long and is increasing my code base and also, i have a feeling that it ain't the best solution for doing this. So i need a much shorter implementation. Here is my implementation:

-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 running it in 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]

I am motivated by the fact that in the STDLIB there is no such function. Somewhere in my game, i need to shuffle things up and also i need to find the best efficient solution to the problem, not just one that works.

Could some one help build a shorter version of the solution ? probably even more efficient ? Thank you

回答1:

Please note that karl's answer is much more concise and simple.

---

Here's a fairly simple solution, although not necessarily the most efficient:

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

For example, one could probably do away with the ++ operation in nth_rest/3. You don't need to seed the random algorithm in every call to random. Seed it initially when you start your program, like so: random:seed(now()). If you seed it for every call to uniform/1 your results become skewed (try with [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]

Associate a random number R with each element X in L by making a list of tuples {R, X}. Sort this list and unpack the tuples to get a shuffled version of 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).

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