實(shí)現(xiàn)一個(gè)random?shuffle算法示例

更新時(shí)間：2022年05月18日 12:24:07 作者：Concyclics

這篇文章主要為大家介紹了實(shí)現(xiàn)一個(gè)random?shuffle算法示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

引言

你是否有過(guò)類似的煩惱？想從一個(gè)列表中取出若干個(gè)不重復(fù)的元素，但是不知道要如何去重？這里提供一種叫random shuffle的方法。

random shuffle

原理

shuffle有洗牌的意思，該方法也類似洗牌，從一個(gè)列表的前綴中隨機(jī)取一個(gè)位置，和前綴的末尾做交換，這樣對(duì)于每一位，都類似洗牌把它隨機(jī)插進(jìn)前面某個(gè)位置，就能實(shí)現(xiàn)把整個(gè)列表打亂成隨機(jī)的分布，最后我們只需要取打亂后列表的前iii位，即是不重復(fù)的了。

實(shí)現(xiàn)

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;
}

測(cè)試

對(duì)1−1001-1001−100進(jìn)行random shuffle，統(tǒng)計(jì)每個(gè)位置出現(xiàn)的值的期望，一共隨機(jī)1e5次，觀察每個(gè)位置的期望值。

測(cè)試方式

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";
	}
}

測(cè)試結(jié)果

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