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

ok ok@REDACTED
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.

```