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    

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