shuffling(洗牌) - webdancer's Blog

shuffling(洗牌)

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

 

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)中,因为要多次重复再训练集上进行,所以每次打乱训练集的顺序可以用洗牌算法。当然还有其他。
 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee