在实现Fisher-Yates费雪耶兹随机置乱算法时,可能会出现偏差,尽管这种偏差是非常不明显的。原因:一是实现算法本身出现问题;二是算法基于的随机数生成器。
1.实现上每一种排列非等概率的出现
在算法流程里 j 的选择范围是从0...i-1;这样Fisher-Yates算法就变成了Sattolo算法,共有(n-1)!种不同的排列,而非n!种排列。
j在所有0...n的范围内选择,则一些序列必须通过n^n种排列才可能生成。
2.Fisher-Yates费雪耶兹算法使用的随机数生成器是PRNG伪随机数生成器
这样的一个伪随机数生成器生成的序列,完全由序列开始的内部状态所确定,由这样的一个伪随机生成器驱动的算法生成的不同置乱不可能多于生成器的不同状态数,甚至当可能的状态数超过了排列,不正常的从状态数到排列的映射会使一些排列出现的频率超过其他的。所以状态数需要比排列数高几个量级。
很多语言或者库函数内建的伪随机数生成器只有32位的内部状态,意味着可以生成2^32种不同的序列数。如果这样一个随机器用于置乱一副52张的扑克牌,只能产生52! = 2^225.6种可能的排列中的一小部分。对于少于226位的内部状态的随机数生成器不可能产生52张卡片的所有的排列。
伪随机数生成器的内部状态数和基于此生成器的每种排列都可以生成的最大线性表长度之间的关系: