随机洗牌算法

最近和同事讨论棋牌类游戏中的一些算法技巧和网络通信技巧，说到抽牌算法。如何每次洗牌更加平均，这是一个比较容易出问题的地方。我们有非常多的算法可以使用，算非常容易想到，使用一个随机数即可。但当你做千次以及上万次测试时会发现，概率并非平均分布，游戏数字出现几率非常高，而一些数字出现几率很低。如何解决这个问题。网上搜了一下，还真有不少方法，一些高级方法基于概率学，但通常情况下速度不理想。最终发现一个名为“Fisher–Yates”的算法，大概介绍如下：

Fisher–Yates随机置乱算法也被称做高纳德置乱算法，通俗说就是生成一个有限集合的随机排列。Fisher-Yates随机置乱算法是无偏的，所以每个排列都是等可能的，当前使用的Fisher-Yates随机置乱算法是相当有效的，需要的时间正比于要随机置乱的数，不需要额为的存储空间开销。

算法的过程如下：

  1. 需要随机置乱的n个元素的数组a
  2. 从0到n开始循环，循环变量为i
  3. 生成随机数K，K为0到n之间的随机数
  4. 交换i位和K位的值

使用JavaScript代码实现如下：

var a = [0,1,2,3,4,5,6,7,8,9];


function p(arr)
{
	var k = 0;
	var temp = 0;
	for(var i=0;i<arr.length;i++)
	{
		k = Math.floor(Math.random()*(arr.length-i));
		temp = arr[i];
		arr[i] = arr[k];
		arr[k] = temp;
	}
}

console.log(a);
p(a);
console.log(a);

运行结果：

[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[ 9, 1, 0, 2, 4, 5, 6, 3, 7, 8 ]

看上去还可以，顺序被打乱了，我们来连续执行1000次，看一下各个数值的分布情况。

列代表对应位出现的次数，行代码数字。

0 1 2 3 4 5 6 7 8 9
0 94 85 109 108 85 103 105 113 107 91
1 100 106 103 106 84 103 105 113 107 91
2 100 114 96 87 103 105 88 103 101 103
3 105 92 105 99 117 103 103 87 83 106
4 100 99 95 108 112 105 88 94 98 101
5 88 120 91 111 100 106 103 92 100 89
6 102 113 96 90 97 107 88 110 100 97
7 104 94 103 91 98 76 114 108 106 196
8 112 93 97 89 99 107 97 104 95 107
9 95 84 105 111 105 102 113 85 99 101


我们可以看到，数组中一共10个数字，共执行1000次，如平均分布的话，出现次数为100次，根据表中的最大值计算，误差为20%左右。结果相对比较理想。我们再来做10000次运算测试。

0 1 2 3 4 5 6 7 8 9
0 1028 983 985 991 1022 1068 855 964 990 1014
1 1018 940 1020 1059 965 970 1008 1003 989 998
2 989 1048 987 1022 985 958 981 980 1051 999
3 937 994 1023 1110 1045 1004 1004 977 969 942
4 1004 1015 988 975 987 1020 1007 1033 986 985
5 1017 1010 1047 962 1063 993 982 922 993 1011
6 956 1018 966 1002 1037 1002 1018 1037 993 971
7 1005 1008 961 970 964 1009 1050 1039 986 1008
8 1043 990 997 970 943 965 985 1005 1043 1059
9 1003 994 1050 1026 924 970 1010 1010 1000 1013


10000次平均值应为1000，结果中误差为5%左右。当我们在服务器中进行大量随机元算时，此方法相对比较理想。

最后贴一下测试用例代码：

var a = [0,1,2,3,4,5,6,7,8,9];


function p(arr)
{
	var k = 0;
	var temp = 0;
	for(var i=0;i<arr.length;i++)
	{
		k = Math.floor(Math.random()*(arr.length-i));
		temp = arr[i];
		arr[i] = arr[k];
		arr[k] = temp;
	}
}

var log = [[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0]];

for(var i=0;i<10000;i++)
{
	p(a);
	for(var t=0;t<10;t++)
	{
		log[a[t]][t]++;
	}
}

console.log("    0,   1,   2,   3,   4,   5,   6,   7,   8,   9");

for(var i=0;i<10;i++)
{
	var str = "";
	for(var t=0;t<10;t++)
	{
		str += "  "+log[i][t];
	}
	console.log(i+" "+str);
}

关于Fisher-Yates算法，可以参考这里

enjoy!