Fisher-Yates Shuffle高效随机算法

前些天在做算法题时,遇到了一个觉得有意思的东西:

注意红色的箭头

要求是返回的排列顺序的概率应该相同,当时想的是把每一种排列都弄出来,然后emm,就3X2种而已,后来看看别人的写的,haha,自己还是幼稚了些。

在任何编程语言中最流行的混乱技术称为Fisher-Yates Shuffle,这就是我们在这里使用的。Fisher-Yates Shuffle首先在数组中的任何位置选择一个随机元素,然后使用数组中的最后一个元素进行交换。在下一步中,它从数组中除最后一个元素之外的任何位置选择一个随机元素,并将其与倒数第二个元素交换。它一直持续到交换每个元素为止。

emm,1.0

更清晰的图片可以看可汗学院的那个链接,自己录屏技术有限,请谅解一下下哈。

升级版的,暂时没写源码。

2.0

这是其中的一个实现:

实现的效果

源码:https://github.com/Jiangjao/python_learn_demo/blob/master/Fisher-Yates%20shuffle

reference:Wiki:https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

                可汗学院: https://www.khanacademy.org/computing/computer-programming/programming-games-visualizations/memory-game/a/grid-of-tiles

部分图片来源:谷歌

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

相关阅读更多精彩内容

  • 知识点 洗牌算法 随机数 1.1.36 乱序检查。通过实验检查表1.1.10 中的乱序代码是否能够产生预期的效果...
    kyson老师阅读 1,304评论 0赞 50
  • 大家好,我是IT修真院郑州分院第七期的学员冯亚超,一枚正直纯洁善良的WEB程序员 今天给大家分享一下,洗牌算法具体...
    f056917阅读 880评论 0赞 0
  • # Python 资源大全中文版 我想很多程序员应该记得 GitHub 上有一个 Awesome - XXX 系列...
    小迈克阅读 3,179评论 1赞 3
  • 我没有多好的文采,没有丰富的语言。请耐心看一看 1996年11月的一天,我出生在山东的一个小镇,一个普通的小镇...
    星月凤阅读 402评论 0赞 0
  • 水是生命之源,五行之首,尤其是当今水污染严重,喝水是件大事情,宁可三日不吃饭,也不宁愿一日不喝水。 美国《国际癌症...
    半山风雨楼阅读 1,111评论 2赞 4

友情链接更多精彩内容