[erlang-questions] Random Permutations (Swap 2 elements within a list a la Erlang ?)

[Paulo Sérgio Almeida]

Hi,

Richard Carlsson wrote:
> ok wrote:
>> Here's another approach:
>>
>> 	random_partition(List) ->
>> 	    random_partition(List, [], []).
>>
>> 	random_partition([], Left, Right) ->
>> 	    {Left,Right};
>> 	random_partition([X|Xs], Left, Right) ->
>> 	    U = random:uniform(),
>> 	    if U >= 0.5 ->
>> 		random_partition(Xs, Left, [X|Right])
>> 	     ; U < 0.5 ->
>> 		random_partition(Xs, [X|Left], Right)
>> 	    end.
>>
>> 	randomise([]) ->
>> 	    [];
>> 	randomise([X]) ->
>> 	    [X];
>> 	randomise(Bigger) ->
>> 	    {Left, Right} = random_partition(Bigger),
>> 	    randomise(Left) ++ randomise(Right).
>>
>> This one really wants random bits, not random floats.  It actually
>> needs the same number of random bits (ceiling(N.lgN)) as the Fisher-
>> Yates method.
> 
> I think this should definitely go in the stdlib 'lists' module!

Actually, variants of the simple method ok mentioned tend to be faster 
(I measured about 6 times faster for lists with 100 and 1000 elements).

I happened to need generating random permutations and stuff and ended up 
writing a module rand.erl. This module implements a random number 
generator server process which keeps a seed and allows a single random 
number sequence to be generated for a whole application. (Once I forgot 
about seeding and got a bad surprise in which a set of processes 
generated all the same random numbers ...)

Interestingly, as the server process stores the seed, it can use 
internally the functional variants of the uniform functions while 
provide the same non-functional interface. By inlining the functions in 
the server process and due to the saving obtained by not using the 
process dictionary, the functions are as fast as the original from the 
random module, even though they use msg passing.

The module also provides a function for generating a vector of random 
numbers in a single invocation. This is used for implementing the random 
permutation and weighted random permutation (a variant in which elements 
have different probabilities of appearing first).

I include the module here. Feel free to use it.

Regards,
Paulo
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: rand.erl
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20070612/270b7f76/attachment.ksh>