[erlang-questions] Swap 2 elements within a list a la Erlang ?

[ok]

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.