引言

你是否有過(guò)類(lèi)似的煩惱？想從一個(gè)列表中取出若干個(gè)不重復(fù)的元素，但是不知道要如何去重？ 這里提供一種叫random shuffle的方法。

random shuffle

原理

shuffle有洗牌的意思，該方法也類(lèi)似洗牌，從一個(gè)列表的前綴中隨機(jī)取一個(gè)位置，和前綴的末尾做交換，這樣對(duì)于每一位，都類(lèi)似洗牌把它隨機(jī)插進(jìn)前面某個(gè)位置，就能實(shí)現(xiàn)把整個(gè)列表打亂成隨機(jī)的分布，最后我們只需要取打亂后列表的前iii位，即是不重復(fù)的了。

實(shí)現(xiàn)

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;
}

測(cè)試

對(duì)1−1001-1001−100進(jìn)行random shuffle，統(tǒng)計(jì)每個(gè)位置出現(xiàn)的值的期望，一共隨機(jī)1e5次，觀察每個(gè)位置的期望值。

測(cè)試方式

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";
	}
}

測(cè)試結(jié)果

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    

可以觀察到結(jié)果的期望分布十分均勻，都在50上下。

以上就是實(shí)現(xiàn)一個(gè)random shuffle算法示例的詳細(xì)內(nèi)容，更多關(guān)于random shuffle算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！