概述
shuffle算法应用很多，比如n个元素里面随机抽取m个元素，最重要的特性就是我们要保证每个位置上出现任意一个数的概率都是1/n
void shuffle(vector<int>&arr)
{
for (int i=arr.size()-1;i>=0;--i)
{
swap(arr[rand()%(i+1)],arr[i]);
}
}
对于arr[i],洗牌后在第n-1个位置的概率是1/n（第一次交换的随机数为i）
在n-2个位置概率是[(n-1)/n] * [1/(n-1)] = 1/n，（第一次交换的随机数不为i，第二次为arr[i]所在的位置（注意，若i=n-1，第一交换arr[n-1]会被换到一个随机的位置））
在第n-k个位置的概率是[(n-1)/n] * [(n-2)/(n-1)] … [(n-k+1)/(n-k+2)] *[1/(n-k+1)] = 1/n
最后
以上就是俊逸鲜花为你收集整理的shuffle算法的全部内容，希望文章能够帮你解决shuffle算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[学习《算法导论》] 第一部分 基础知识为什么学习这本书第 1 章 算法在计算中的作用第 2 章 算法基础第 4 章 分治策略第5章 概率分析和随机算法](/uploads/reation/bcimg7.png)
发表评论 取消回复