list random shuffle实现

在项目中需要对list进行随机shuffle，但是在erlang的stdlib中没有这个函数。
因此需要自己实现一把。
参考google两种实现：

版本1（速度快，随机化不好）：
shuffle_v1(L) ->       
        List1 = [{random:uniform(), X} || X <- L],
        List2 = lists:keysort(1, List1),
        [E || {_, E} <- List2].

很简单为每个元素添加一个random的次序，随后通过sort进行排序，最后获取最终结果。


版本2（速度慢，随机化好）：
采用：Fisher-Yates shuffle
参考：http://www.itl.nist.gov/div897/sqg/dads/HTML/fisherYatesShuffle.html

shuffle_v2([]) ->
    [];
shuffle_v2(L = [_]) ->
    L;
shuffle_v2(L) ->
    shuffle1(1, L, length(L)).

shuffle1(Len, L, Len) ->
    L;
shuffle1(Cur, L, Len) ->
    S = Cur + round((Len - Cur) * random:uniform()),
    L2 = swap_element(L, Cur, S),
    shuffle1(Cur + 1, L2, Len).

swap_element(L, N, N) ->
    L;
swap_element(L, N1, N2) ->
    Z = lists:zip(lists:seq(1, length(L)), L),
    {value, E1} = lists:keysearch(N1, 1, Z),
    {value, E2} = lists:keysearch(N2, 1, Z),
    Z2 = lists:keyreplace(N1, 1,
                    lists:keyreplace(N2, 1, Z, E1),
                    E2),
    {_, Result} = lists:unzip(Z2),
    Result.

一句话描述算法：
Randomly permute N elements by exchanging each element ei with a random element from i to N. It consumes Θ(N log N) bits and runs in linear time.

评论

2 楼 fxsjy 2009-06-18  

@wangyuantao，正解，算法导论上有讲。

1 楼 wangyuantao 2009-06-10  

1)
S = Cur + round((Len - Cur) * random:uniform()),
应改成
S = random:uniform(Len - Cur + 1) + Cur - 1,
否则计算结果不对！

2)
可以严格证明，shuffle_v1和shuffle_v2产生的随机序列联合分布相同，因此无所谓“随机性”好坏。
理论上虽然shuffle_v1的复杂度O(nlogn)，shuffle_v2的复杂度O(n)（如果swap复杂度是O(1)），但是实验发现，v2的计算时间是v1的100倍以上。