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

[Johan Montelius]

> Contrast this with the version that takes into account the length of  
> both lists.
>
> Julian

Very interesting, I didn't think about that. The same problem does not  
occur in my qsort version does it?

Come to think of it I don't think my version is guaranteed to terminate.  
If we are extremely unlucky the split will generate one empty lists and  
one list with all elements in it :-0

well, for those of you who like living on the edge here is a rewrite that  
(if it terminates:-) is quite quick.


shuffle(L)  ->
      shuffle(L, [], <<>>, rbit(12345), []).
  	
shuffle([], R, B, S, Sofar) -> {R, B, S, Sofar};
shuffle([I], R, B, S, Sofar) -> {R, B, S, [I|Sofar]};
shuffle(L, Rnd, Bin, Seed, Sofar) ->
      {R1, B1, S1, L1, L2} = split(L, Rnd, Bin, Seed, [], []),
      {R2, B2, S2, Q1} = shuffle(L1, R1, B1, S1, Sofar),
      shuffle(L2, R2, B2, S2, Q1).


split([], Rnd, Bin, Seed, L1, L2) ->
      {Rnd, Bin, Seed, L1, L2};
split([H|T], [R|Rnd], Bin, Seed, L1, L2) ->
      case R of
	0 ->
	    split(T, Rnd, Bin, Seed, [H|L1], L2);
	1 ->
	    split(T, Rnd, Bin, Seed, L1, [H|L2])
      end;
split(L, [], Bin, Seed, L1, L2) ->
     {Rnd, Rest, New} = rbit(Bin, Seed),
     split(L, Rnd, Rest, New, L1, L2).

rbit(Seed) ->
     crypto:start(),
     <<Seed>>.

rbit(<<>>, Seed) ->
     Bin = crypto:md5(Seed),
     rbit(Bin, Bin);
rbit(<<B1:1,B2:1,B3:1,B4:1,B5:1,B6:1,B7:1,B8:1, Rest/binary>>, Seed) ->
     {[B1,B2,B3,B4,B5,B6,B7,B8], Rest, Seed}.



-- 
Associate Professor Johan Montelius
Royal Institute of Technology - KTH
School of Information and Communication Technology - ICT