shuffling(洗牌) - webdancer's Blog

shuffling(洗牌)

webdancer posted @ 2012年4月22日 17:36 in 算法 with tags 算法 , 2491 阅读

Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. —wikipedia

1.如何洗牌？

我们玩扑克牌时洗牌可以使用Riffle方法，可以参考http://www.youtube.com/watch?v=uh8iMZY4Nb4

2.洗牌算法

那么计算机如何洗牌呢？这就涉及到怎么设计一个洗牌算法，其中Fisher–Yates shuffle是常用到的洗牌算法，非常简单。

伪代码如下：

To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

python代码实现：

def fyshuffling(a):
    for i in range(len(a)-1,0,-1):
        j=random.randint(0,i)
        a[i],a[j]=a[j],a[i]

注：在python的random模块中提供了shuffle方法,使用的也是Fisher–Yates shuffle算法。

云风在blog里面也讨论过，http://blog.codingnow.com/2007/09/shuffle.html下面的讨论有很多。

3.应用。

在随机梯度下降(stochastic gradient descent)中，因为要多次重复再训练集上进行，所以每次打乱训练集的顺序可以用洗牌算法。当然还有其他。