伪随机数对大列表的完全性洗牌

对一个列表(一维数组)的完全性洗牌(shuffle)操作,是要让其元素每种排列模式等概率出现。

列表元素个数为n,那么其全排列的数目就是n的阶乘“n!”。

伪随机数是有周期的,设周期为m。那基于伪随机数映射的元素排列模式也只会有m种。

当列表元素很多,n! 会是个天文数字,大于伪随机数周期,那样永远有一部分排列模式无法出现。

python标准库函数random.shuffle(x)就说明了——“请注意,即使对于小的len(x),x的排列总数也可以快速增长,大于大多数随机数生成器的周期。 这意味着长序列的大多数排列永远不会产生。 例如,长度为2080的序列是可以在 Mersenne Twister 随机数生成器的周期内拟合的最大序列。”

要对大于伪随机数周期的大列表完全性shuffle,怎么办呢

我采用的办法是多轮洗牌,让基本周期的乘积大于列表元素全排列数目“n!”,就保证了完全性shuffle的完成。

这里有一个启发式的方法:如果需要生成具有n中可能性的随机数,那么就需要一个循环周期长度为n^2的 PRNG(相关细节请参考 Pierre L'Ecuyer 的random number generation)。

我写了这个算法的实现python包,源码放在GitHub上,complete_shuffle

已经发布到了PyPI上,可以很方便的安装分发:

pip install complete-shuffle

此包还包括了Sattolo算法实现的对列表随机循环排列。算法介绍见Sattolo算法

等概率生成列表的“全错位排列”函数,功能实现了可以用于含重复元素的列表。我使用的是优化的接受-拒绝采样算法,时间复杂度为O(n)。生成均匀分布“全错位排列”还有一种优化算法,见Generating Random Derangements。此算法时间复杂度也是O(n),但声称其时间复杂度的常数项较低。我看意义不大。

顺便说python 3.9版已声明 random.shuffle() 的 random 形参将被弃用

我写这个包中函数就有等同于 random.shuffle() 的 random 的形参。可以替代标准库random.shuffle()函数了

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 源码:Lib/random.py 该模块实现了各种分布的伪随机数生成器。 对于整数,从范围中有统一的选择。 对于序...
    山海皆可平z阅读 3,385评论 0 1
  • Python random包可以用来生成随机数。随机数不仅可以用于数学用途,还经常被嵌入到算法中,用以提高算法效率...
    达闻西阅读 9,701评论 1 2
  • 随机数参与的应用场景大家一定不会陌生,比如密码加盐时会在原密码上关联一串随机数,蒙特卡洛算法会通过随机数采样等等。...
    Yookoe阅读 3,658评论 0 0
  • 标签: Python 模块 random是Python内建函数,作用是产生随机数1.导入模块: 2.random模...
    StansJ阅读 5,118评论 0 0
  • 推荐指数: 6.0 书籍主旨关键词:特权、焦点、注意力、语言联想、情景联想 观点: 1.统计学现在叫数据分析,社会...
    Jenaral阅读 11,076评论 0 5

友情链接更多精彩内容