實現一個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算法的資料請關註WalkonNet其它相關文章！