實(shí)現(xiàn)一個(gè)random?shuffle算法示例
引言
你是否有過(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)文章!
相關(guān)文章
VS2019 更新MSDN并創(chuàng)建快捷方式的實(shí)現(xiàn)
這篇文章主要介紹了VS2019 更新MSDN并創(chuàng)建快捷方式的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
C++通過(guò)msxml調(diào)用webservice示例分享
這篇文章主要介紹了C++通過(guò)msxml調(diào)用webservice示例分享,需要的朋友可以參考下2014-03-03
C++?OpenCV紅綠燈檢測(cè)Demo實(shí)現(xiàn)詳解
OpenCV(Open Source Computer Vision Library)是開(kāi)源的計(jì)算機(jī)視覺(jué)和機(jī)器學(xué)習(xí)庫(kù),提供了C++、 C、 Python、 Java接口,并支持Windows、 Linux、 Android、 Mac OS平臺(tái),下面這篇文章主要給大家介紹了關(guān)于C++?OpenCV紅綠燈檢測(cè)Demo實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下2022-11-11
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的三子棋項(xiàng)目
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的三子棋項(xiàng)目,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-08-08
使用ShellClass獲取文件屬性詳細(xì)信息的實(shí)現(xiàn)方法
本篇文章是對(duì)ShellClass獲取文件屬性詳細(xì)信息的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05
C++之類(lèi)和對(duì)象課后習(xí)題簡(jiǎn)單實(shí)例
下面小編就為大家?guī)?lái)一篇C++之類(lèi)和對(duì)象課后習(xí)題簡(jiǎn)單實(shí)例。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-07-07
C語(yǔ)言深入講解棧與堆和靜態(tài)存儲(chǔ)區(qū)的使用
對(duì)大多數(shù)C 語(yǔ)言初學(xué)者來(lái)說(shuō),堆棧卻是一個(gè)很模糊的概念。堆棧是一種數(shù)據(jù)結(jié)構(gòu),一個(gè)在程序運(yùn)行時(shí)用于存放的地方,相信這可能是很多初學(xué)者共同的認(rèn)識(shí),靜態(tài)存儲(chǔ)區(qū)即內(nèi)存在程序編譯的時(shí)候就已經(jīng)分配好,這塊內(nèi)存在程序的整個(gè)運(yùn)行期間都存在2022-04-04
C++函數(shù)參數(shù)取默認(rèn)值的深入詳解
本篇文章是對(duì)C++中函數(shù)參數(shù)取默認(rèn)值進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05

