实现一个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.980650.997850.980150.9618
50.966250.948650.934850.9374
50.901350.867550.927450.8882
50.874850.865650.855550.8352
50.821850.83350.787650.8293
50.817450.747550.783350.7234
50.793550.765250.778750.6877
50.757850.719350.69450.6374
50.710650.673750.651150.643
50.636550.607950.626150.5958
50.588650.556150.583750.602
50.524150.55950.580650.5683
50.494350.516850.474350.4901
50.47950.472950.474550.4282
50.452150.362650.400550.4381
50.337350.354350.373850.4259
50.307150.340350.277350.2991
50.348550.330150.308750.2954
50.221650.259750.288250.2848
50.237550.222450.21450.2504
50.165650.1450.130450.1726
50.231950.157950.159950.1223
50.139650.02950.075950.1079
50.057350.021950.071650.0642
49.995750.036450.060449.9931

可以观察到结果的期望分布十分均匀，都在50上下。