[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Håkan Huss]

On Thu, May 27, 2010 at 09:39, Johan Montelius <johanmon@REDACTED> wrote:
> On Thu, 27 May 2010 02:47:03 +0200, Toby Thain <toby@REDACTED>
> wrote:
>
>> It won't. Use Fisher-Yates or an equivalent method.
>> http://en.wikipedia.org/wiki/Fisher–Yates_shuffle
>
> Fisher-Yates (or the Knuth version) uses teh fact that you can access
> elements in an array and do the shuffling in O(n). If we have a list to
> shuffle the same algorithm will be O(n2) since we have to run down the list
> do find the element we want to shuffle.
>
> If we are working with lists I think any solutions is a version of
> merge-sort or quick-sort and have a O(n*lg(n)) complexity.
>
Indeed. The random merge that has been shown here earlier can be
corrected by replacing the coin flip with a choice that takes into
account the length of the lists:

-module(unsort).

-export([unsort/1]).

unsort(L) ->
   unsort(L, length(L)).

unsort(L, Len) when Len < 2 ->
   L;
unsort(L, Len) ->
   L1_len = Len div 2,
   L2_len = Len - L1_len,
   {L1, L2} = lists:split(L1_len, L),
   randmerge(unsort(L1, L1_len), L1_len, unsort(L2, L2_len), L2_len).


randmerge([], 0, L2, _) ->
   L2;
randmerge(L1, _, [], 0) ->
   L1;
randmerge(L1, L1_len, L2, L2_len) ->
   case random:uniform(L1_len + L2_len) of
       N when N =< L1_len ->
           [hd(L1) | randmerge(tl(L1), L1_len - 1, L2, L2_len)];
       _ ->
           [hd(L2) | randmerge(L1, L1_len, tl(L2), L2_len - 1)]
   end.

/Håkan