[erlang-questions] Swap 2 elements within a list a la Erlang ?
ok
<>
Tue Jun 12 01:06:50 CEST 2007
On 9 Jun 2007, at 9:34 pm, Andreas Bakurov wrote:
> Hello all. I am new to Erlang and face a lot of dilemmas.
> I have implemented Knuth's or Fisher-Yates shuffle in Erlang
Your goal is presumably to create a random permutation of a list.
The technique you describe is a superb one for MUTABLE ARRAYS.
It is amazingly lousy for lists.
There is a published result that you cannot permute an immutable list
of N elements in less than O(N.lgN) time. I was halfway through
writing a paper on that myself when a kind colleague showed me the
paper. I don't have a copy.
Perhaps the simplest way to scramble a list is
[X || {_,X} <- lists:sort(
[{random:uniform(),Y} || Y <- List])]
- attach a random number to each element of the list
- sort, using the random numbers as primary keys
- remove the random numbers
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.
More information about the erlang-questions
mailing list