从M个数中随机取出N个

简介:

看到这样一个题目:在M个数中,随机取出其中的N个,要求等概率。

这应该是一个比较简单的题目,看到题目后的第一想法是:维护一个关于这M个数的集合,然后每次随机从集合中抽一个数,抽N次即可。
等概率显然不是什么问题,当然前提是假设随机函数是等概率的,否则任何方法都免谈了。
对于其中的每一个数,它在每一次不被抽走的概率是:(M-1)/M、(M-2)/(M-1)、...、(M-N)/(M-N-1),到最后还没被抽走的概率就是(M-N)/M,也就是说它会被抽走的概率是N/M。

看到一个网友的解决思路,感觉很有意思:

在M个数中,随机取出其中的N个,那么每个数被选中的概率都是N/M。

对于其中的第一个数字,它被选中的概率是N/M,所以随机生成一个来自(0,1)之间的均匀分布的实数u。
如果u<N/M,则这个数被选中。于是问题简化为:对于剩下的M-1个数,等概率选择其中的N-1个,每个数被选中的概率都是(N-1)/(M-1);
否则,这个数字不被选中。问题简化为:对于剩下的M-1个数,等概率选择其中的N个,每个数被选中的概率都是N/(M-1);

简单分析一下概率:对于这第一个数字,它被选中的概率就是N/M。
对于剩下的M-1个数,任何一个数被选中的概率是: N/M * (N-1)/(M-1) + (1-N/M) * N/(M-1) = N/M. 因此满足题意。

这样的思路让人很受启发……


目录
相关文章
|
消息中间件 Kubernetes Docker
「译」在 Kubernetes 1.16 上启用和使用 Ephemeral(临时)容器
「译」在 Kubernetes 1.16 上启用和使用 Ephemeral(临时)容器
|
Python
df获取最后一行数据
df获取最后一行数据
820 0
|
8月前
|
自然语言处理 负载均衡 数据可视化
100万免费 Token!DeepSeek-R1满血版即刻拥有
随着DeepSeek在线使用需求的迅猛增长,服务器资源紧张和响应延迟问题日益突出。本文推荐使用百炼大模型服务平台,提供DeepSeek满血版调用的平替方案,支持OpenAI SDK或HTTP方式快速体验。DeepSeek-R1与DeepSeek-V3分别有100万免费Token,另有多款开源Qwen及Llama蒸馏模型支持调用。通过百炼平台,无需自行搭建基础设施,具备负载均衡和自动扩缩容机制,确保API调用稳定。搭配Chatbox可视化界面客户端,简化调用流程,预估费用为0元,免费试用额度耗尽后预计成本不超过1元。
|
人工智能 自然语言处理 Swift
"轻量级微调推理框架SWIFT:大模型时代的速度革命,让你秒变AI部署高手!"
【8月更文挑战第17天】随着AI技术的发展,大模型如GPT-3和BERT引领风潮,但其部署与推理速度面临挑战。为此,魔搭社区推出了SWIFT(Simple Weight-Integrated Fine-Tuning)框架,它采用轻量级微调技术,实现模型参数压缩与加速,确保大模型能在移动端和边缘设备上高效运行。SWIFT具备四大特点:创新微调方法减少训练参数;内置优化策略提高推理速度;跨平台支持便于部署;兼容主流预训练模型。通过示例可见,从加载预训练模型到模型的微调、评估及导出,SWIFT简化了工作流程,降低了大模型的应用门槛,促进了AI技术的实际应用。
1216 4
|
机器学习/深度学习 边缘计算 5G
|
存储 安全 Java
深度长文解析SpringWebFlux响应式框架15个核心组件源码
以上是Spring WebFlux 框架核心组件的全部介绍了,希望可以帮助你全面深入的理解 WebFlux的原理,关注【威哥爱编程】,主页里可查看V哥每天更新的原创技术内容,让我们一起成长。
543 3
|
缓存 应用服务中间件 nginx
[nginx]lua控制响应头
[nginx]lua控制响应头
304 0
|
机器学习/深度学习 人工智能 搜索推荐
详细探讨AI在个性化教育平台中学习路径推荐的应用
详细探讨AI在个性化教育平台中学习路径推荐的应用
|
机器学习/深度学习 自然语言处理 并行计算
一文搞懂Transformer架构的三种注意力机制
一文搞懂Transformer架构的三种注意力机制
1383 1