怎么实现一个random shuffle算法

魁首哥

作者

怎么实现一个random shuffle算法

这篇文章主要介绍“怎么实现一个randomshuffle算法”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“怎么实现一个randomshuffle算法”文章能帮助大家解决问题。

引言

你是否有过类似的烦恼？想从一个列表中取出若干个不重复的元素，但是不知道要如何去重？这里提供一种叫random shuffle的方法。

random shuffle

原理

shuffle有洗牌的意思，该方法也类似洗牌，从一个列表的前缀中随机取一个位置，和前缀的末尾做交换，这样对于每一位，都类似洗牌把它随机插进前面某个位置，就能实现把整个列表打乱成随机的分布，最后我们只需要取打乱后列表的前iii位，即是不重复的了。

实现

template<typenameT>vector<T>my_random_shuffle(vector<T>input){staticmt19937rnd(time(NULL));for(uint64_ti=1;i<input.size();i++){swap(input[i],input[rnd()%i]);}returninput;}

测试

对1−1001-1001−100进行random shuffle，统计每个位置出现的值的期望，一共随机1e5次，观察每个位置的期望值。

测试方式

intmain(intargc,char*argv[]){intn=100;intt=1e5;vector<double>input(n);vector<double>ans(n,0);for(inti=0;i<n;i++){input[i]=i+1;}for(inti=0;i<t;i++){intj=0;for(autox:my_random_shuffle(input)){ans[j]+=x;j++;}}for(auto&x:ans){x/=t;}for(inti=0;i<n;i++){cout<<ans[i]<<"\t\t";if(i%4==3)cout<<"\n";}}

测试结果

50.9806 50.9978 50.9801 50.9618
50.9662 50.9486 50.9348 50.9374
50.9013 50.8675 50.9274 50.8882
50.8748 50.8656 50.8555 50.8352
50.8218 50.833 50.7876 50.8293
50.8174 50.7475 50.7833 50.7234
50.7935 50.7652 50.7787 50.6877
50.7578 50.7193 50.694 50.6374
50.7106 50.6737 50.6511 50.643
50.6365 50.6079 50.6261 50.5958
50.5886 50.5561 50.5837 50.602
50.5241 50.559 50.5806 50.5683
50.4943 50.5168 50.4743 50.4901
50.479 50.4729 50.4745 50.4282
50.4521 50.3626 50.4005 50.4381
50.3373 50.3543 50.3738 50.4259
50.3071 50.3403 50.2773 50.2991
50.3485 50.3301 50.3087 50.2954
50.2216 50.2597 50.2882 50.2848
50.2375 50.2224 50.214 50.2504
50.1656 50.14 50.1304 50.1726
50.2319 50.1579 50.1599 50.1223
50.1396 50.029 50.0759 50.1079
50.0573 50.0219 50.0716 50.0642
49.9957 50.0364 50.0604 49.9931