实现一个random shuffle算法示例-C/C++开发

这篇文章主要为大家介绍了实现一个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