如何实现一个random shuffle？

引言

你是否有过类似的烦恼？想从一个列表中取出若干个不重复的元素，但是不知道要如何去重？
这里提供一种叫random shuffle的方法。

random shuffle

原理

shuffle有洗牌的意思，该方法也类似洗牌，从一个列表的前缀中随机取一个位置，和前缀的末尾做交换，这样对于每一位，都类似洗牌把它随机插进前面某个位置，就能实现把整个列表打乱成随机的分布，最后我们只需要取打乱后列表的前$i$位，即是不重复的了。

实现

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-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上下。