又是一道跟概率相关的简单问题。话说我的概率学的太差了,趁这个机会也从头开始补习一下。
【有趣的题目|等概率随机排列数组(洗牌算法)】 问题描述:假设有一个数组,包含n个元素。现在要重新排列这些元素,要求每个元素被放到任何一个位置的概率都相等(即1/n),并且直接在数组上重排(in place),不要生成新的数组。用 O(n) 时间、O(1) 辅助空间。
算法是非常简单了,当然在给出算法的同时,我们也要证明概率满足题目要求。
先想想如果可以开辟另外一块长度为n的辅助空间时该怎么处理,显然只要对n个元素做n次(不放回的)随机抽取就可以了。先从n个元素中任选一个,放入新空间的第一个位置,然后再从剩下的n-1个元素中任选一个,放入第二个位置,依此类推。
按照同样的方法,但这次不开辟新的存储空间。第一次被选中的元素就要放入这个数组的第一个位置,但这个位置原来已经有别的(也可能就是这个)元素了,这时候只要把原来的元素跟被选中的元素互换一下就可以了。很容易就避免了辅助空间。
用Python来写一段简单的程序描述这个算法:
1
2 3 4 5 6 7 |
from
random
import Random
def Shuffle (li ): rand = Random ( ) for x in xrange ( len (li ) - 1 , 0 , - 1 ): # 逆序遍历li y = rand. randint ( 0 , x ) # 从剩余数据中随机选取一个 li [x ] , li [y ] = li [y ] , li [x ] # 将随机选取的元素与当前位置元素互换 |
来计算一下概率。如果某个元素被放入第i(1≤i≤n)个位置,就必须是在前 i - 1 次选取中都没有选到它,并且第 i 次选取是恰好选中它。其概率为:
pi=n?1n×n?2n?1×?×n?i+1n?i+2×1n?i+1=1n
可见任何元素出现在任何位置的概率都是相等的。
实际上Python用户一定知道,在Random类中就有现成的shuffle方法,处理方法与我上面的程序是一样的。顺便也贴在这里学习一下。以下代码来自于 Python 2.5 Lib\random.py:
250
251 252 253 254 255 256 257 258 259 260 261 262 |
def shuffle
(
self
, x
,
random
=
None
,
int
=
int
):
"""x, random=random.random -> shuffle list x in place; return None. Optional arg random is a 0-argument function returning a random float in [0.0, 1.0); by default, the standard random.random. """ if random is None: random = self. random for i in reversed ( xrange ( 1 , len (x ) ) ): # pick an element in x[:i+1] with which to exchange x[i] j = int ( random ( ) * (i+ 1 ) ) x [i ] , x [j ] = x [j ] , x [i ] |
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 推荐系统论文进阶|CTR预估 论文精读(十一)--Deep Interest Evolution Network(DIEN)
- Python专栏|数据分析的常规流程
- 分析COMP122 The Caesar Cipher
- Python|Win10下 Python开发环境搭建(PyCharm + Anaconda) && 环境变量配置 && 常用工具安装配置
- Python绘制小红花
- Pytorch学习|sklearn-SVM 模型保存、交叉验证与网格搜索
- OpenCV|OpenCV-Python实战(18)——深度学习简介与入门示例
- python|8. 文件系统——文件的删除、移动、复制过程以及链接文件
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)