云风的 BLOG: 洗牌

今天从 svn 中取下一个同事的代码，浏览了一下。其中一段是关于洗牌的。感觉实现的很乱，算法也没有选好。自己重新写了一个。

因为国庆的缘故，负责这块代码的同事提前回家了。我只好自己读代码实现。看完后，发现旧的实现是这样的：对于 N 张牌，每次随机抽出一张来，检查这张牌是否抽过。如果被抽取过，就重复抽取过程，直到不重复。然后记录下抽取的牌的位置。重复这个过程，直到得到一个随机序列。最后用这个序列将原始排列打乱。

这个方案给我的第一感觉并不好，因为当 N 较大时，最后需要重复抽取多次才可以成功。我估算了整个的时间复杂度大约是 O(N^2)

当然，洗牌这件事情可以有许多算法来解决。我重新写了一个，采用了最简单实现的方案。

新的方案是从牌套里随机找到两个位置，将其位置的牌交换。重复若干次后，便可以将牌洗乱。这里最关键的是需要找到一个合适的重复次数。

这个问题首先需要定义什么叫作“洗乱”。

我随便给出了一个定义：在洗牌过程中，任意一张牌不被抽到交换的概率小于 1/1000 。（这个定义不太符合直观感觉，这个下面会讨论）

简单的列出方程：( (n-2)/n ) ^ m <=1/1000 得到 m >= -3* ln 10 / ln (1-2/n)

对于 52 张牌，大约是 176 次。

之后，另一个同事给了我另一个方案。产生 N 个不易发生碰撞的随机数，比如 (0,1) 的浮点数，或是 [0,4G) 的整数。将这些数字排序，则可以得到一个被打乱次序的序列。

这个方案看起来更好，因为更接近洗乱牌的目的。我重新给一个“洗乱”的定义：每张牌在每个位置出现的概率相同。

反过来，我想知道前面我给出的交换法洗牌有多接近它。

要得到严格的数学分析似乎很困难。偷懒 google 了一下，原来好多人研究过类似问题了。看这里：

http://mathworld.wolfram.com/Shuffle.html

从这个链接找过去，有一篇论文。它讨论了另一种类似的洗牌方法，即第一次把第一张和随机一张牌交换，第二次把第二张和随机一张牌交换…… 重复做 N 次。

当 N 大于等于 18 时，用这个方法洗牌后，居然恒等排列（identity permutation）是最有可能出现的。（所谓恒等排列大概是指第 n 张排在第 n 个位置）。论文太长没精力读，不过这个结论还真是让人惊奇啊。

Comments

应该用每种排列出现概率相同来定义‘洗乱’，对于n>18时大概率出现恒等排列不认同。因为以此算法出现恒等排列的概率为1/n！是极小概率事件，《算法导论》p70-71页详细分析了，作者后两种生成随机序列的方法（随机优先级和便利i次将i与随机的i+1...n中的一个交换）。结论是这两种方法都可得到一个均匀的随机序列。

Posted by: 张斯禹 | (47) March 21, 2017 10:50 PM

其实这就是数组乱序算法,算法到轮上面就有提供O(n)算法,并给出了随机性的证明

Posted by: LYJ | (46) October 13, 2014 11:59 AM

感谢云风大的分享, 刚才看到了一篇文章分析了一下某几种的优劣, 写的通俗易懂(也就是说我都能看懂-_-)

http://coolshell.cn/articles/8593.html

Posted by: Seeker | (45) June 25, 2014 11:52 AM

伪随机数跟系统时间有关，其实已经很随机，不放心还可以和cpu温度，显卡温度进行运算两下子，这样基本没有办法作弊了。

然后线性扫一次随机交换即可，O(n)复杂度。

真正随机数，等量子计算机出来之后能有 ..

Posted by: leokan | (44) January 24, 2011 11:05 AM

直觉觉得楼主总有点不trust别人代码的感觉。

还有，楼主估计人家的复杂度是O(n^2)，好像是错的，应该是O(n*log(n))的。

还有你自己实现的那个也不咋地，最简单的
for(int i=0;i<n;i++){
swapArray(i, random(i,n))
}

Posted by: zhangfaen | (43) September 23, 2010 12:03 AM

比如说，对于1到5进行“洗牌”。原来顺序是1到5，第1张是1，…第5张是5。
然后，生成一定数量的随机数（参数，如果是游戏大厅的话，可以根据玩家情况，上线时间等），比如生成20个，其范围是1到5，比如生成的是：5，1；4，4；3，2；5，4；5，1；5，1；1，5；4，5；2，1；4，4。
然后，把这20个数作为“第几张”，依次取每2个，然后对这两张牌进行交换。有的位置可能交换多次，也可能恰好换回到原来的牌。按照上面的数据，先把第5张和第1张交换，然后把第4张和第4张交换（等于没换），…最后把第2张和第1张交换，把第4张和第4张交换（等于没换）。完成后，即完成了洗牌，得到：
3，4，2，5，1。
只要交换的次数足够，可以得到满意的洗牌结果。上面有人说了全排列的出现概率。还有，可以统计每张牌在每个位置出现的概率，或不在原来位置的概率。

Posted by: Anonymous | (42) July 26, 2008 07:58 PM

随机挑一张牌与第一张交换，然后随机2-n的牌中与第二张交换，3-n的牌中与第三张交换，可以归纳证明这个可以得到1-n各种排列，而且等概率。

Posted by: 玉米 | (41) October 24, 2007 09:45 AM

n张牌的排列有n!种，分成两类，一种是奇置换，一种是偶置换，奇置换可以写成奇数个对换（交换）的符合，偶置换反之。用对换试图生成所有的排列，如果固定对换个数的话是不可能的，奇数个对换合在一起不会生成偶置换。最简单情形，两张牌，一次对换，一定得不到恒等排列。如果每次对换选的两张牌可以是一样的，一样则不对换，但是对换的次数照常计数的话还是有可能产生比较均匀的各种排列分布（未进一步研究）。

Posted by: 玉米 | (40) October 24, 2007 09:38 AM

这样定义比较直接且妥当：

n 张牌的全排列有 n! 种。一种恰当的洗排算法应该让洗牌后的排列，对这 n! 种排列方案有均等的出现概率。

Posted by: Cloud | (39) October 11, 2007 07:54 PM

“从这个链接找过去，有一篇论文。它讨论了另一种类似的洗牌方法，即第一次把第一张和随机一张牌交换，第二次把第二张和随机一张牌交换…… 重复做 N 次....”
这是算法导论的一个习题，当时我给的答案是能正确的得到一个均匀随机排列。看来错得很厉害啊。

刚才帖了一次源码，格式完全乱了，算法大抵如下：第一次把第一张和随机一张交换，第二次把第二张与2～n 之间的随机一张交换...第i 次把第i 张与i～n 之间的随机一张交换。由循环不变式可以证明这样得到的会是一个均匀随机排列。

另外,"我重新给一个“洗乱”的定义：每张牌在每个位置出现的概率相同" 这个定义值得商榷：满足这一定义的一些算法并不能真正的得到完全随机排列。

Posted by: atyuwen | (38) October 11, 2007 07:05 PM

算法导法里的一个算法：
function randomize(A)
n=A.length
for i=1 to n
j=random(i,n)
swap A[i],A[j]

Posted by: atyuwen | (37) October 11, 2007 06:53 PM

这是我的一个扑克牌游戏的洗牌算法, 就是随机两两交换
for(int m = 0; m < 2; m++) {
//洗牌两次
for(int i = 0; i < MAX_CARDS; i++) {
int j = Util.getPositiveRange(0, 54);
//随机两两交换
if(i != j) {
byte tmp = cards[i];
cards[i] = cards[j];
cards[j] = tmp;
}
}
}

Posted by: Anonymous | (36) October 10, 2007 10:01 AM

我用的方法是先开一个A[N+1]的数组，存的值为rand()以cpu时间戳播种的值（同样也是1-n之间），然后对依照产生的随机数改变所有数字的位置！这样的复杂度为O(N)，效果也不错！应该回复在这里！

Posted by: 枫之羽 | (35) October 9, 2007 10:30 PM

其实用STL的话，偶经常产生1-n的数，然后直接random_shuffle一下...

Posted by: 极光炫影 | (34) October 8, 2007 01:23 PM

恒等排列？没看懂

Posted by: 安德尔斯 | (33) October 6, 2007 09:27 PM

确实像楼下好多同学说的，Kunth在TAOCP里有过随机问题的讨论。

不过我记得高爷爷当时重点强调过一件事，大意是说虽然很多人想了很多巧妙的随机数产生算法，不过大多数都没有Lehmer给的那个同余算法效果好。虽然他之后也讨论了很多随机算法。

不过在给出一堆随机算法之后，他又说算法要过关，一定要通过“谱检验”方法的检验才行。（感觉“谱检验”就是Schmidt正交化方法,Orz……）

而且针对“伪随机数”不够随机的说法（就像楼下有的同学说过的），Kunth在那一章的最后给了一个证明过程，结果就是伪随机数产生算法的结果序列与真正的随机序列的不同在序列足够长的情况下小于ε。也就是说伪随机数产生算法的结果序列是可以当作真正的随机序列的（别拍我，细节我也没记住）。

具体情况，有兴趣的同学去看《TAOCP第二卷：半数值算法》第三章吧。

其实那一卷最难的是第四章，反正我当年看第三章只是觉得全身发冷（当时是夏天），看了第四章发觉屋内早已是阴风四起…………

以下是从BaiDu知道搜过来的Lehmer的算法：

线性同余法(Linear Congruential Method)
目前使用的大多数随机数发生器是线性同余发生器，它是Lehmer于1951年提出的，其通式为
Xi+1=(aXi+c)mod m
Ui+1=Xi+1／m
其中a为乘子(常数)，C为增量(常数)，X0为种子，m为模。
线性同余法有如下特点：
(1)0≤Xi≤m-1,即Xi只能从0，1，2，……，m-1这m个整数中取值；
(2)适当选择m,a,c,可使Xi产生循环，无论X0取何值，其循环顺序是相同的。其循环周期称为发生器周期，记为P。若p=m,则称该发生器具有满周期。
回答者：flybird11 - 助理二级 5-17 02:07

Posted by: 星染流云 | (32) October 6, 2007 01:05 PM

改善那算法,把它作以N的全排列那样就好理解了:
for(i=0;i<N;i++){
i!=N-1时,j=随机数(i,N-1);
j!=i时,card[i]与card[j]交换;
}
这样就是N的全排列的一种情况,比那算法好理解一点儿,别的没有什么不同.

Posted by: Anonymous | (31) October 5, 2007 02:26 PM

对于“第一次把第一张和随机一张牌交换，第二次把第二张和随机一张牌交换…… 重复做 N 次”的算法
我用数值计算了一下N=54的情况，确实不够随机；与预期的完全随机偏差最大有35%之多(也就是某张牌出现在某个位置的几率比完全随机值高35%)！还尝试了使用两次该算法，偏差降低到1%！所以这个快速算法还是很有用的；

Posted by: housisong | (30) October 4, 2007 04:46 PM

玩魔方,乱扭几下,就难返回原样,时间复杂度不大,比如,a....b1b2....c把b2扭到a的位置,就是先把a...b1b2...c逆转为c...b2b1...a,再逆转c...b2为b2...c,逆转b1...a为a...b1,这就扭完了,没有用多久,横竖几下就相当于人工洗了,呵呵,胡扯的,你们想想更好的办法吧.

Posted by: Anonymous | (29) October 4, 2007 01:23 AM

有一个怪想法,能不能用排序的逆过程,hash,shell,这些排序不逆,也能产生出,只是基数不知道由什么产生,昨天,买了张36选7的彩票,就想了想这东西

Posted by: Anonymous | (28) October 4, 2007 12:44 AM

参见《编程珠玑》第二版，第十二章“抽样问题”，对这个有个详细的细致的讨论，其中Knuth的算法不错。

Posted by: 尉迟方 | (27) October 3, 2007 03:25 PM

C++标准库的random_shuffle，不是挺好了吗？

Posted by: Anonymous | (26) October 3, 2007 02:04 PM

数学推理过程方面不明白的，可以看那篇论文。

它只是想说明，这样操作，洗过后可能出现的各种随机排列方式并非均匀分布的。

其中，恒等排列（假设这种排列是没洗过的牌的排列）是所有可能性中最有可能出现的。

虽然是最有可能，但这种可能性也还是极小的。毕竟，一共有 n! 种排列方式。

Posted by: Cloud | (25) October 2, 2007 11:14 PM

我一直用的方法和云风所说的最后一种方法类似，但没明白恒等的意思。假设n张牌，从1~n中随机取一张牌和第一张牌交换，然后再从2~n中随机取一张牌和第二张牌交换，O(n)的复杂度，用下来没发现什么不妥啊！

Posted by: Anonymous | (24) October 2, 2007 10:49 PM

从链表中随机挑出一个节点并把这个节点从链表中取掉的时间复杂度是 O(N)

Posted by: Anonymous | (23) October 2, 2007 09:53 PM

楼下提到的随机选两张牌进行交换是可行，不过交换的次数不宜太多，好像N／2次比较好。以前我参加的一个研讨班有人讲过这个概率问题，进行N／2（不过也许是N，不记得了）交换得到的排列最随机。

另外Knuth的计算机程序设计艺术的书里有个简单简单的算法可以给出N个数的所有非重复排列。如果我没记错，只要给一个1－N！之间的数，那个算法可以计算出一个排列，非常高效的。不过不要问我是那卷第几页了，我也不知道，我是从一个论坛得知的，google一下应该可以找到一些相关信息。

Posted by: phoolimin | (22) October 2, 2007 08:05 PM

楼下楼下的楼下

抽到后要移动牌怎么会增加时间复杂度呢？难道你不知道有链表这东西？

随机数种子问题可以在一个单独的服务器上生成一个全局的随机数种子序列

Posted by: Anonymous | (21) October 2, 2007 03:46 PM

潜水N久终于发言了,因为这个和我的工作有点相关,随便说2句,关于洗牌我们原来用的方式就是随机数+嵌套循环的方式,原以为没问题结果出了问题就发生在这个随机上,如果服务器上2桌游戏同时开始的话随机数居然一样,分得的牌也一样,这个就造成了我们曾经最大的一个BUG,后来用到了GUID来做为变量来处理随机数才解决了这个问题.
云风大哥POPOGAME的项目也要过问啊.辛苦了

Posted by: 空心苹果 | (20) October 2, 2007 01:08 PM

我觉得最不用研究的就是洗牌了，因为的确没有任何一种洗牌方法是最好的。计算机实现的话，选一种最快的就行了

Posted by: nothanks | (19) October 2, 2007 11:46 AM

如果每次抽取后都要移动牌的话，时间复杂度还是 O(N^2)

最后的性能不一定比随机抽取再判断重复更好。性能取决于是产生随机数快还是移动内存快。

Posted by: Anonymous | (18) October 2, 2007 10:59 AM

大大国情都不休息？

Posted by: sheep | (17) October 2, 2007 10:39 AM

楼下的楼下是正解。
逻辑和数学不好的太多了。。。

Posted by: Anonymous | (16) October 2, 2007 05:20 AM

不存在重复抽取

Posted by: Anonymous | (15) October 1, 2007 05:09 PM

云风想太多了其实洗牌很简单每次随机都可以选出一张牌不存在什么重复抽取

比如有10张牌把这10张牌放入10个位置第一张牌随机1～10 得出的数不是牌而是“位置” 取出相应位置的牌比如随机到了5 就取出5的位置对应的牌“5” 然后把5以后所有位置的牌往前移第二轮随机1～9 比如又得到5 则取出5对应位置的牌“6” 第三轮随机1～8 如此一来每次随机都会得出一张随机的牌

Posted by: Anonymous | (14) October 1, 2007 05:08 PM

最后那个办法为什么是恒等排列？解释解释，我用过这个办法，没发现有什么问题。

Posted by: Anonymous | (13) October 1, 2007 08:25 AM

两两交换是可行的，但是随机的范围必须是递减的，才能刚好符合 P (上标52) (下标52) 那个啥排列组合

Posted by: Atry | (12) October 1, 2007 02:45 AM

<pre>
<html>
<body>
<script>
// generate an integer in [0, n)
function randomInteger(n) {
return Math.floor(Math.random() * n);
}

function shuffle(numberOfCard) {

var returnValue = new Array(numberOfCard);
for(var i = 0; i < numberOfCard; i++) {
returnValue[i] = i;
}

for(var i = numberOfCard; i > 0; i--) {
var r = randomInteger(i);
var t = returnValue[r];
returnValue[r] = returnValue[i - 1];
returnValue[i - 1] = t;
}

return returnValue;
}
</script>
</body>
</html></pre>

Posted by: Atry | (11) October 1, 2007 02:42 AM

我就不信这个邪,我就非要帖代码 - -

Posted by: Atry | (10) October 1, 2007 02:39 AM

<html> 
<body> 
<script>
 
// generate an integer in [0, n)
 
function randomInteger(n) { 
return Math.floor(Math.random() * n);
 
} 
 
function shuffle(numberOfCard) { 
   var returnValue = new Array(numberOfCard);
 
  for(var i = 0; i < numberOfCard; i++) { returnValue[i] = i; } 
  for(var i = numberOfCard; i > 0; i--) { 
    var r = randomInteger(i); 
    var t = mappingCard[r]; 
    mappingCard[r] = mappingCard[i - 1]; 
    returnValue[i - 1] = t;
 
  }
 
  return returnValue; 
} 
alert(shuffle(1)); 
alert(shuffle(2)); 
alert(shuffle(3)); 
alert(shuffle(4));
 
alert(shuffle(52));
 
</script> 
</body>
 
</html>

Posted by: Atry | (9) October 1, 2007 02:38 AM

我是猪，这个代码哪里需要用到两个数组，一个数组就行了。而且我的算法就相当于两两交换。两两交换当然是可行的

Posted by: Atry | (8) October 1, 2007 02:30 AM

<pre>
// generate an integer in [0, n)
function randomInteger(n) {
return Math.floor(Math.random() * n);
}

var mappingCard = new Array(numberOfCard);
for(var i = 0; i < numberOfCard; i++) {
mappingCard[i] = i;
}

var returnValue = new Array(numberOfCard);

for(var i = 0; i < numberOfCard; i++) {
var r = randomInteger(numberOfCard - i);
returnValue[i] = mappingCard[r];
mappingCard[r] = mappingCard[numberOfCard - i - 1];
}

return returnValue;
}

alert(shuffle(1));
alert(shuffle(2));
alert(shuffle(3));
alert(shuffle(4));
alert(shuffle(52));

</pre>
时间和空间都是 O(n)

Posted by: Atry | (7) October 1, 2007 02:18 AM

我想到了一种算法，虽然这个算法对于专业搞竞赛的人来说只是小儿科，不过我觉得还是要比你的算法好，不用排序。
稍等，我用JavaScript把这个算法写一下。

Posted by: Atry | (6) October 1, 2007 01:41 AM

还在想这个问题，好像大家的方法都用到了随机函数来决定抽取位置。

我提一个猜想：有没有可能不使用随机函数，也能达到把牌洗乱的目的呢？
比如，保存上一个牌局的牌套，然后再在这个基础上对牌的序号作运算。

个人不喜欢随机函数的原因是随机函数不随机，是伪随机数。

Posted by: 红色警戒 | (5) October 1, 2007 12:18 AM

楼下说的方法就是云风文章最后提到的那篇论文里讨论的方法。
人家已经有结论说了，当N>=18的时候，最有可能会出现恒等排列。
而一副牌54张（含大小王），用这个方法看来很有可能出现恒等排列。

所以还是支持云风的方法

Posted by: 红色警戒 | (4) September 30, 2007 11:37 PM

傻交换法还是笨了点,只需要在一次次数等同牌总张数的循环里,把第n张牌和第m张(m=rand(n~总牌数))交换就可以了

Posted by: Anonymous | (3) September 30, 2007 10:25 PM

我还是感觉云风的交换好一些。产生随机数再排序那个感觉过分依赖随机数发生器（也就是随机函数）。假如系统就是产生了一个例如：1，2，3，。。。N的序列，或者1，2，3。。。N,N-1,N-3这样的序列，那么整副牌基本上等于没洗开。
云风是产生了随机位置后再交换，这样就与随机数本身的序列没有关系了。
当然那个算法的好处就是效率高，不用判断是否重复。云风那个还要判断一下随机抽取的位置是否一样。

Posted by: 红色警戒 | (2) September 30, 2007 08:47 PM

恒等排列？还真有点吓人！！

Posted by: missdeer | (1) September 30, 2007 08:09 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

洗牌

Comments

Post a comment