select m objects from n objects randomly
Q: how to select m objects randomly from n objects with euqal possibility?
A: allocate an array of m elements to keep the final result.
put the first m objects into the array.
foreach object k numbered from m+1 to n, generate an random rational number a in [0, 1],
if a <= m/k then
generate an random integer number in [1, m], say i, remove the i-th element from the final result,
and put the kth number into it.
//PROVE the answer.
We can use mathematics induction.
The propositonal statement is P(n): the method in the answer can be used to select m objects out of n objects randomly, and each object is picked out with possibility of m/n, (n>=m).
Basis step:
P(m) is true since the answer put the first m elemets into the final result.
induction step:
The induction hypothesis is P(k) is true for all k>=m, then
the (k+1)-th element will be select with possibility of m/(k+1).
Any element kept in the final result before iteration k+1 has a possibility to be removed from the array which is m/(k+1) * (1/m), from the hypothesis, so it will stay in the final result with a possibility of m/k * (1 - m/(k+1) * (1/m)) = m/(k+1).
From the basis step and induction step, we have that P(n) is true for any integer n>=m.
最新文章
- charles 抓取eclipse中的请求
- 【转载】那些年我们一起清除过的浮动demo
- 安卓开发NDK环境搭建
- 基于Bootstrap的DropDownList的JQuery组件的完善版
- 把Linux安装到移动硬盘上
- Css - Table.css
- NDK 编译可执行程序
- 前端开发必备组件库【基于原生js、兼容主流浏览器、B/S必备】
- 运维老鸟教你安装centos6.5如何选择安装包
- .Net Core实现将文件上传到七牛云存储
- js浮点数运算精度问题
- AI 积分图
- VUE 多页面配置(一)
- 英语口语练习系列-C26-广告-人际关系-辨别物体-如果
- CSS--思维导图
- centos crontab 计划任务 设置与查看
- C++编译与链接(1)-编译与链接过程
- 单独安装VS2012装mono for android
- Queue<;T>;队列与Stack<;T>;堆栈
- String in Java
热门文章
- python urllib2详解及实例
- windows设置多长时间后自动关机 分类: windows常用小技巧 2014-04-15 09:35 230人阅读 评论(0) 收藏
- [PWA] 11. Serve skeleton cache for root
- Android(java)学习笔记224:横竖屏切换时Activity的生命周期
- oracle 添加自增索引
- tinkphp URL重写,支持伪静态
- android6.0源码分析之Camera API2.0下的Capture流程分析
- UIView ->; image &; 本地时间获取
- nodejs概论(实操篇)
- QFormLayout