BeWithYou

胡搞的技术博客

  1. 首页
  2. 数据结构/实用算法/知识
  3. Fisher-Yates洗牌算法

Fisher-Yates洗牌算法


工作中用到了随机洗牌的算法,想起以前也在某次笔试题中遇到过这样的题目,当时觉得很简单,就是随机呗。现在的代码是要放到生产环境中的,不得不严肃的思考下,才发现之前想的确实太简单了。

之前想过这么几种思路:

1、每次随机从牌堆中抽一个位置的牌放到一个递增的位置上。

$arr = array(0,1,2,3,4,5,6);
$resultArr = array();
$len = count($arr);
while(--$len)
{
    array_push($resultArr,array_splice($arr,rand()%($len+1),1)[0]);
}
print_r($resultArr);
/*
Array
(
    [0] => 4
    [1] => 0
    [2] => 1
    [3] => 3
    [4] => 6
    [5] => 2
)
*/

感觉是没有错啦,而且用我大PHP写出来还是蛮简洁的,毕竟PHP的数组提供了很多很方便的方法。但是貌似有些废操作,array_splice这个函数执行后,会自动将弹出的元素后面集体前移,这一步虽然PHP帮助我们实现了,但目测底层还是要做跟人工相同的操作的,要保持下标连续。

2、每次抽随机两张牌交换位置,重复N次,N越大洗牌效果越好

这个想法跟人工洗牌有点类似,但是做法从直觉上就很山寨,因为总是随机抽取两张牌交换位置,如果N不够大的话,很大程度上会存在有的牌根本没操作到,有的牌重复操作了很多次。直接放弃吧。

3、目前普遍使用的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]

从某一端(比如尾部)开始,每次跟前面随机一个位置的牌交换(也有可能随机到自己)。交换后index-1,继续操作,直到遍历一遍数组,完成洗牌。复杂度O(n),只需要遍历一遍数组即可,也不用移动元素和新开空间。

这种做法覆盖了所有可能的情况,每张牌都有可能不在原来的位置上,也有可能在原来的位置上。其实洗牌方法中只要有一种情况不符合实际的可能性,就可以全盘否定了。

lua代码实现如下:

-- 洗牌
function poker:shuffle()
    math.randomseed(os.time())
    for i=#self.current_arr,1,-1 do
        j = math.floor(math.random() * (i) + 1)
        self.current_arr[i],self.current_arr[j] = self.current_arr[j],self.current_arr[i]
    end
end


参考 http://bost.ocks.org/mike/shuffle/ 的动画效果,用svg+js实现了下面的模拟洗牌。

 


回到顶部