实现一个random shuffle算法示例
引言
random shuffle
原理
实现
测试
测试结果
引言你是否有过类似的烦恼？想从一个列表中取出若干个不重复的元素，但是不知道要如何去重？ 这里提供一种叫random shuffle的方法。
random shuffle 原理shuffle有洗牌的意思，该方法也类似洗牌，从一个列表的前缀中随机取一个位置，和前缀的末尾做交换，这样对于每一位，都类似洗牌把它随机插进前面某个位置，就能实现把整个列表打乱成随机的分布，最后我们只需要取打乱后列表的前iii位，即是不重复的了。
实现template <typename T>
vector<T> my_random_shuffle(vector<T> input)
{
static mt19937 rnd(time(NULL));
for(uint64_t i=1; i<input.size(); i++)
{
swap(input[i], input[rnd()%i]);
}
return input;
}
测试
对1−1001-1001−100进行random shuffle，统计每个位置出现的值的期望，一共随机1e5次，观察每个位置的期望值。
测试方式
int main(int argc, char *argv[])
{
int n=100;
int t=1e5;
vector<double> input(n);
vector<double> ans(n,0);
for(int i=0;i<n;i++)
{
input[i]=i+1;
}
for(int i=0;i<t;i++)
{
int j=0;
for(auto x:my_random_shuffle(input))
{
ans[j]+=x;
j++;
}
}
for(auto &x:ans)
{
x/=t;
}
for(int i=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
可以观察到结果的期望分布十分均匀，都在50上下。
以上就是实现一个random shuffle算法示例的详细内容，更多关于random shuffle算法的资料请关注软件开发网其它相关文章！
