I quite often find myself wanting to randomize the order of a list, so much so that I wonder if it shouldn’t be included in the lists module. The simplest solution I came up with uses lists:sort/2:
1> F = fun(_A, _B) -> case rand:uniform(2) of 1 -> true; 2 -> false end end,
2> lists:sort(F, "abcdefghijklmnopqrstuvwxyz").
"klzyivxjhfewtcdubasrpqognm"
Anyone have a better way to do this?
I would enumerate it with random numbers and sort by that:
randomize(String) ->
Ns = [ rand:uniform() || _ <- String ],
{_, Randomized} = lists:unzip(lists:keysort(1, lists:zip(Ns, String))),
Randomized.
1> S = "abcdefghijklmnopqrstuvwxyz".
"abcdefghijklmnopqrstuvwxyz"
2> randomize(S).
"pyzgdwcnxrohlefumtjqabkvis"
Not sure if it’s better than sort with rand in comparison function 
In the general case I’d say it is. Comparison sorts rely on the fact that if A < B and B < C, then A < C. If you return random comparison results, A >= C may happen despite A < B, B < C, which can lead to really funny behavior with some algorithms. I’m not sure it’s a problem for the merge sort lists:sort/1,2 uses though.
randomize_list(List) ->
D = lists:keysort(1, [{rand:uniform(), A} || A <- List]),
{_, D1} = lists:unzip(D),
D1.
Is a version we’ve used in the past.
The {Min, Avg, Max} results are:
1> L = randomize:list(1000).
2> randomize:test(1000, compare, L).
{261,348,1392}
3> randomize:test(1000, zip1, L).
{139,196,969}
4> randomize:test(1000, zip2, L).
{121,188,626}
The zip versions use floats, which is unfortunate. I refactored with rand:uniform/1 and got a 20% improvement.
randomize.erl:
-module(randomize).
-export([compare/1, zip1/1, zip2/1, list/1, test/3]).
compare(List) ->
F = fun(_A, _B) ->
case rand:uniform(2) of
1 -> true;
2 -> false
end
end,
lists:sort(F, List).
zip1(String) ->
Ns = [ rand:uniform() || _ <- String ],
{_, Randomized} = lists:unzip(lists:keysort(1, lists:zip(Ns, String))),
Randomized.
zip2(List) ->
D = lists:keysort(1, [{rand:uniform(), A} || A <- List]),
{_, D1} = lists:unzip(D),
D1.
list(N) ->
list(N, []).
list(0, Acc) ->
Acc;
list(N, Acc) ->
list(N - 1, [rand:bytes(20) | Acc]).
test(N, F, L) ->
test(N, F, L, []).
test(0, _, _, Acc) ->
Times = lists:sort(Acc),
Minimum = hd(Times),
Maximum = lists:last(Times),
F = fun(T, A) ->
A + T
end,
Total = lists:foldl(F, 0, Times),
Average = Total div length(Times),
{Minimum, Average, Maximum};
test(N, F, L, Acc) ->
{Time, _} = timer:tc(?MODULE, F, [L]),
test(N - 1, F, L, [Time | Acc]).
I agree with @John, and so does Wikipedia that has a section about the suggested random number method:
An alternative method assigns a random number to each element of the set to be shuffled and then sorts the set according to the assigned numbers. The sorting method has the same asymptotic time complexity as Fisher–Yates: although general sorting is O(n log n), numbers are efficiently sorted using Radix sort in O(n) time. Like the Fisher–Yates shuffle, the sorting method produces unbiased results. However, care must be taken to ensure that the assigned random numbers are never duplicated, since s…
To get it correct, duplicate random numbers have to be handled. I suppose that when stripping off the random numbers from the result one can collect all with the same random number in a list and then call the algorithm recursively to shuffle that sub-list, before continuing stripping.
Using 48 bit random integers is probably a good speed compromise, with low probability for generated number collision, but collisions will anyway happen once in a blue moon…
The trick of using a comparison function returning random values is also described, in the second paragraph in the same section. It is bad since the sort function may be derailed in strange ways, but at least certainly produce skewed element distribution.
For our split-and-merge sort I guess it will get strange element distribution such as; maybe elements early in the original list ends up early in the shuffled list, and that perhaps elements close together in the original list ends up fairly close together in the shuffled list…
I suppose it would also be possible to implement Fisher-Yates using a map with integer keys, but will not guess how the performance will be compared to “assign random numbers and sort”…
… so maybe an addition to the lists module would be justified?
But shouldn’t that just implement Fisher Yates instead of other methods. I have an implementation for that in some old project available. Its fully functional (re-implementation of some Haskell version from Oleg Kiselyov) … just need to find it
… you wouldn’t have to search if was in the lists module.
I’m all for having it in lists FWIW I found it and dumped it down there. The algorithm was a bit hard to understand need time to get into it again. Also this code is from 2013 … and I didn’t get to optimise it for speed
Here is the original algorithm together with the description.
AFAIK: The content of the linked is still the state of the art of functional perfect shuffle implementation.
%% adapted from haskell
%% http://okmij.org/ftp/Haskell/perfect-shuffle.txt
build_tree(List) ->
grow_level([{leaf, X} || X <- List]).
grow_level([Node]) ->
Node;
grow_level(L) ->
grow_level(inner(L)).
inner([]) ->
[];
inner([_]=X) ->
X;
inner([E1,E2|Rest]) ->
[join(E1, E2) | inner(Rest)].
join({leaf, _}=L, {leaf, _}=R) ->
{node, 2, L, R};
join({node, Ct, _, _}=L, {leaf, _}=R) ->
{node, Ct+1, L, R};
join({leaf, _}=L, {node, Ct, _, _}=R) ->
{node, Ct+1, L, R};
join({node, Ctl, _, _}=L, {node, Ctr, _, _}=R) ->
{node, Ctl+Ctr, L, R}.
shuffle(Elements) ->
N = length(Elements),
shuffle(Elements, [ random:uniform(N-I+1)-1 || I <- lists:seq(1,N-1) ]).
shuffle(Elements, Randseq) ->
shuffle1(build_tree(Elements), Randseq).
shuffle0({leaf, E}, []) ->
[E];
shuffle0(Tree, [Ri|Rest]) ->
extract_tree(Ri, Tree, fun(T) -> shuffle0(T, Rest) end).
extract_tree(0, {node, _, {leaf, E}, R}, K) ->
[E|K(R)];
extract_tree(1, {node, 2, {leaf, _}=L, {leaf, R}}, K) ->
[R|K(L)];
extract_tree(N, {node, C, {leaf, _}=L, R}, K) ->
extract_tree(N-1, R, fun(New_r) -> K({node, C-1, L, New_r}) end);
extract_tree(N, {node, N1, L, {leaf, E}}, K) when N+1 == N1 ->
[E|K(L)];
extract_tree(N, {node, C, {node, C1, _, _}=L, R}, K) ->
if N < C1 ->
extract_tree(N, L, fun(New_l) -> K({node, C-1, New_l, R}) end);
true ->
extract_tree(N-C1, R, fun(New_r) -> K({node, C-1, L, New_r}) end)
end.
shuffle1({leaf, E}, []) ->
[E];
shuffle1(Tree, [Ri|Rest]) ->
{E, New} = extract_tree1(Ri, Tree),
[E | shuffle1(New, Rest)].
extract_tree1(0, {node, _, {leaf, E}, R}) ->
{E, R};
extract_tree1(1, {node, 2, {leaf, _}=L, {leaf, E}}) ->
{E, L};
extract_tree1(N, {node, C, {leaf, _}=L, R}) ->
{E, New_r} = extract_tree1(N-1, R),
{E, {node, C-1, L, New_r}};
extract_tree1(N, {node, N1, L, {leaf, E}}) when N+1 == N1 ->
{E, L};
extract_tree1(N, {node, C, {node, C1, _, _}=L, R}) ->
if N < C1 ->
{E, New_l} = extract_tree1(N, L),
{E, {node, C-1, New_l, R}};
true ->
{E, New_r} = extract_tree1(N-C1, R),
{E, {node, C-1, L, New_r}}
end.
I changed random to rand and compared:
1> L1 = randomize:list(1000).
2> randomize:test(1000, zip, L1).
{98,171,1489}
3> randomize:test(1000, shuffle, L1).
{237,297,1108}
4> L2 = randomize:list(100000).
5> randomize:test(1000, zip2, L2).
{31684,52129,132021}
6> randomize:test(1000, shuffle, L2).
{140372,178963,555508}
… so there’s a small cost for being perfect. 
My, how this takes me back to the 80s, when I was trying ti figure out how to generate a ranom permutation in Prolog. It turns out that Prolog can permute a list in linear expected time, but it was already a proven result that it took O(n.lg n) time oin the pointer machine model, hence in a pure functional language.
I believe you can do it thus:
To permute a list of n items randomly,
If n < 2, reurn the list
Otherwise generate a random subset of size
floor(n/2) and its complement,
Permute them, and concatenate them.
This takes O(n.log n) time and random numbers.
It!s basically a randomised quicksort.
The shuffle code can be optimised of course e.g. the tuples can be shortened (leaf and node atoms are only for readability and then we could profile and see where to streamline.
Probably the fastest way would be a Fisher Yates NIF but that could be always a optimisation later on after a API function is in lists
Firstly, I think a shuffle function belongs in the rand module, and would be happy to introduce it, if I can find the time…
I tried to understand the Haskell perfect shuffle link by @peerst, and to me it seems that it builds on the same basic idea as Fisher-Yates; it inserts all elements in a lookup structure, in this case a “complete binary tree”, and then extracts and removes one at the time using a uniform random value over the remaining elements.
I implemented that with a map as lookup structure instead, and on my laptop it shuffles 1’000’000 elements in just over 5 s. Hard to compare with anything, I know, but here is the code:
-spec shuffle2(list()) -> list().
shuffle2(List) ->
{ShuffledList, State} = shuffle2_s(List, seed_get()),
_ = seed_put(State),
ShuffledList.
-spec shuffle2_s(list(), state()) -> {list(), state()}.
shuffle2_s(List, State)
when is_list(List) ->
case List of
[] ->
{List, State};
[_] ->
{List, State};
_ ->
M = maps:from_list(lists:enumerate(List)),
N = maps:size(M),
shuffle2_s(M, State, N, [])
end.
shuffle2_s(M0, State0, N, Acc)
when is_map(M0), is_integer(N) ->
if
N =:= 0 -> {Acc, State0};
true ->
X = maps:get(N, M0),
case uniform_s(N, State0) of
{N, State1} ->
M1 = maps:remove(N, M0),
shuffle2_s(M1, State1, N - 1, [X | Acc]);
{K, State1} when is_integer(K) ->
Y = maps:get(K, M0),
M1 = (maps:remove(N, M0))#{K := X},
shuffle2_s(M1, State1, N - 1, [Y | Acc])
end
end.
I also have a function that tags with random values and sorts, but after reading the Haskell document I start to realize that such an algorithm has to produce a more or less skewed distribution… But it does the same job, not correctly then, in 1.7 s.
Those times are with the default PRNG. With crypto:rand_seed() it gets much slower, but using crypto:rand_seed_alg(crypto_cache) instead brings about the same speed back again.
If shuffle was added to the rand module - does it make sense to add two options?
For comparison, on my laptop, a Fisher-Yates shuffle of an array of a million elements
takes 40 milliseconds. In Smalltalk. (Admittedly a very good Smalltalk.)
Nearly all the time is going in random number generation.
So the standard against which we should measure a shuffling algorithm is
“how much longer does it take than generating that many random numbers.”
Which Haskell document says that decorate-with-uniform-randoms-then-sort-then-undecorate
“HAS to produce a more or less skewed distribution”?
%% If the list count is less than 300, use the
confuse_list1function to shuffle the list; otherwise, useconfuse_list2. %% If the order of magnitude is uncertain, directly useconfuse_list2.
confuse_list1(List) →
TupleList = list_to_tuple(List),
TupleSize = tuple_size(TupleList),
confuse_list1(TupleSize, TupleSize, TupleList).confuse_list1(0, _TupleSize, TupleList) → tuple_to_list(TupleList);
confuse_list1(Index, TupleSize, TupleList) →
ChangeIndex = rand:uniform(TupleSize),
Value1 = element(Index, TupleList),
Value2 = element(ChangeIndex, TupleList),
TupleList1 = setelement(Index, TupleList, Value2),
TupleList2 = setelement(ChangeIndex, TupleList1, Value1),
confuse_list1(Index - 1, TupleSize, TupleList2).transfer_maps(, Index, Map) → {Index - 1, Map};
transfer_maps([Element | List], Index, Map) →
transfer_maps(List, Index + 1, Map#{Index => Element}).confuse_list2(List) →
{Cnt, Map} = transfer_maps(List, 1, #{}),
confuse_list2(Cnt, Cnt, Map).confuse_list2(0, _Size, Map) → maps:values(Map);
confuse_list2(Index, Size, Map) →
ChangeIndex = rand:uniform(Size),
#{Index := Value1, ChangeIndex := Value2} = Map,
confuse_list2(Index - 1, Size, Map#{Index := Value2, ChangeIndex := Value1}).
Posted by @peerst:
https://okmij.org/ftp/Haskell/perfect-shuffle.txt
Furthermore, if we have a sequence of N elements and associate with
each element a key – a random number uniformly distributed within [0,
M-1] (where N!>M>=N), we have the configurational space of size M^N
(i.e., M^N ways to key the sequence). There are N! possible
permutations of the sequence. Alas, for N>2 and M<N!, M^N is not
evenly divisible by N!. Therefore, certain permutations are bound to
be a bit more likely than the others.
But that argumentation doesn’t cover if we have a “random” numbers with no duplicates, nor if we permute the duplicates. And I don’t fully get the math in the argument.
Removing the element at index N from the map is not necessary because you never look at it again. Not removing it makes the shuffle somewhat faster, at least on my computer. In the following benchmark run, rand:shuffle3/1 is the name of the modified function that doesn’t remove any map elements:
% erlperf --init_runner_all 'lists:seq(1, 1_000_000).' 'r(L) -> rand:shuffle2(L).' 'r(L) -> rand:shuffle3(L).'
Code || QPS Time Rel
r(L) -> rand:shuffle3(L). 1 1 750 ms 100%
r(L) -> rand:shuffle2(L). 1 1 1000 ms 75%
Because decorate-with-uniform-random-numbers-then-sort-then-undecorate apparently works when the random numbers has no duplicates; an interesting approach came to mind:
We can use a lookup data structure to detect duplicates and decorate, and if that data structure is ordered we can also use it to sort and undecorate. With gb_trees this becomes quite beautiful:
shuffle_s(List, State) ->
shuffle_s(List, State, gb_trees:empty()).
shuffle_s([], State, T) ->
{gb_trees:values(T), State};
shuffle_s([X | L], State0, T) ->
{K, State1} = rand:uniform(1 bsl 56, State0),
case gb_trees:is_defined(K, T) of
true ->
shuffle_s([X | L], State1, T);
false ->
shuffle_s(L, State1, gb_trees:insert(K, X, T))
end.
That runs in about 4.5 s for 1’000’000 elements on my laptop.
Alas, maps are so fast, and lookup time is important for this algorithm so the correspoding not quite as beautiful maps rewrite that has to explicitly sort and undecorate runs in about 3.3 s:
shuffle_s(List, State) ->
shuffle_s(List, State, #{}).
shuffle_s([], State, M) ->
{[X || {_,X} <- lists:keysort(1, maps:to_list(M))], State};
shuffle_s([X | L], State0, M) ->
{K, State1} = rand:uniform(1 bsl 56, State0),
case maps:has_key(K, M) of
true ->
shuffle_s([X | L], State1, M);
false ->
shuffle_s(L, State1, maps:put(K, X, M))
end.
This is approaching (half the speed) the maybe incorrect decorate-then-sort-then-reiterate-duplicates’ 1.7 s…