CODEWITHSUNDEEP
erlang
Muzaaya Joshua
Muzaaya Joshua

Reputation: 7836

Shuffling Elements in a List (randomly re-arrange List Elements)

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

Upvotes: 14

Views: 6283

Answers (4)

Roman Rabinovich
Roman Rabinovich

Reputation: 918

This will be a bit faster than the above solution, listed here as do2 for timing comparison.

-module(shuffle).
-export([
    time/1,
    time2/1,
    do/1,
    do2/1
]).

time(N) ->
    L = lists:seq(1,N),
    {Time, _} = timer:tc(shuffle, do, [L]),
    Time.
time2(N) ->
    L = lists:seq(1,N),
    {Time, _} = timer:tc(shuffle, do2, [L]),
    Time.
do2(List) ->
    [X||{_,X} <- lists:sort([ {rand:uniform(), N} || N <- List])].
do(List) ->
    List2 = cut(List),
    AccInit = {[],[],[],[],[]},
    {L1,L2,L3,L4,L5} = lists:foldl(fun(E, Acc) -> 
        P = rand:uniform(5), 
        L = element(P, Acc),
        setelement(P, Acc, [E|L])
    end, AccInit, List2),
    lists:flatten([L1,L2,L3,L4,L5]).

cut(List) ->
    Rand=rand:uniform(length(List)),
    {A,B}=lists:split(Rand, List),
    B++A.

Upvotes: 1

Adam Lindberg
Adam Lindberg

Reputation: 16587

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

Upvotes: 6

BlackMamba
BlackMamba

Reputation: 10252

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

Upvotes: 1

karl
karl

Reputation: 761

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>

Upvotes: 76

Related Questions