日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后,達者為師

網站首頁 編程語言 正文

實現一個random?shuffle算法示例_C 語言

作者:Concyclics ? 更新時間: 2022-07-14 編程語言

引言

你是否有過類似的煩惱?想從一個列表中取出若干個不重復的元素,但是不知道要如何去重? 這里提供一種叫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上下。

原文鏈接:https://juejin.cn/post/7093484844918931464

欄目分類
最近更新