洗牌算法-從m個對象里隨機取出n個不重復的對象

洗牌算法是一種非常巧妙但又很好理解的算法

用于從m個對象里隨機取出n個不重復的對象(n<m)

先來思考一個簡單的問題霎苗,從0-99里面隨機選取一個正整數(shù)怎么做魏铅,Math.random()*100搞定

那么我有一個長度為100的數(shù)組芒率,存了100個不重復的元素,需要從中隨機選取50個不能重復的元素該怎么做晴竞?Math.random()*100來50次亲族,按下標取到50個元素。但是要求不能重復呀拂蝎,所以每隨機一次都要去判斷這個數(shù)字是否已經(jīng)出現(xiàn)過穴墅,直到這個數(shù)字沒有出現(xiàn)過為止。這顯然太麻煩了呀匣屡。

那我們不妨換一種思路封救,如果我們把這個長度為100的數(shù)組中的元素隨機打亂順序,就像洗牌一樣捣作,然后直接取前50個元素不就好了誉结。

OK,那么怎樣算隨機打亂順序券躁?每一個元素出現(xiàn)在任一位置的概率均相等惩坑,才算隨機打亂順序。這就用到了洗牌算法也拜。一句話就可以解釋:遍歷每一個元素以舒,將它和包括自身及之后的所有元素中隨機選取的一個元素進行交換,直到遍歷夠需要的數(shù)量為止

比如有一個數(shù)組慢哈,里面存的{1,2,3,4,5}蔓钟,我們需要隨機取出其中不重復的3個數(shù)

  1. 我們來遍歷這個數(shù)組,第一個元素是1卵贱,假設我們隨機到了它跟4這個元素交換為止滥沫,數(shù)組變?yōu)閧4,2,3,1,5}。任意一個數(shù)在第一位的概率都是1/5
  2. 繼續(xù)遍歷键俱,第二個元素是2兰绣,我們從第2個到第5個這4個元素中隨機,假設我們隨機到了2本身编振,那么數(shù)組還是{4,2,3,1,5}缀辩。這個算法牛逼的地方到了,因為2逃過了第一輪交換,且在第二輪被選中臀玄,那么它出現(xiàn)在第二位的概率是4/5*1/4=1/5
  3. 繼續(xù)遍歷瓢阴,第三個元素是3,我們從第3個到第5個這3個元素中隨機健无,假設我們隨機到了5炫掐,數(shù)組變?yōu)閧4,2,5,1,3}。5出現(xiàn)在第三位的概率是4/53/41/3=1/5
  4. 繼續(xù)遍歷睬涧,第4個元素是1募胃,我們從第4個到第5個這2個元素中隨機,假設我們隨機到了3畦浓,數(shù)組變?yōu)閧4,2,5,3,1}痹束。我們要注意,雖然3之前被交換到了第5位讶请,但是它并沒有被選中過祷嘶,只是遍歷到了它而被動交換,3出現(xiàn)在第四位的概率是4/53/42/3*1/2=1/5
  5. 最后剩下的1留在了第5位夺溢,1出現(xiàn)在第五位的概率同樣也是4/53/42/3*1/2=1/5

我們可以看到论巍,每一個元素出現(xiàn)在任一位置的概率均為1/5。我為了解釋這個算法风响,進行了一輪完整的遍歷嘉汰,在實際應用中,因為我們只要取到不重復的3個數(shù)就可以状勤,所以遍歷到第3輪結束鞋怀,拿到{4,2,5}就可以停止了。

再注意一下持搜,這個數(shù)組的長度是5密似,需要隨機取3個不重復的數(shù),其實隨機取到2個不重復的數(shù)以后葫盼,剩下的3個數(shù)不就是隨機的3個數(shù)了么残腌?所以我們遍歷到第2輪結束,扔掉{4,2},剩下的{3,1,5}同樣也滿足隨機取出不重復的3個數(shù)贫导。

代碼如下:

import random

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 6  # 取出6個不重復的數(shù)字

num = (len(arr) - count) if count > len(arr) / 2 else count
for i in range(0, num):
    temp = arr[i]
    rand = random.randint(i, len(arr) - 1)
    arr[i] = arr[rand]
    arr[rand] = temp

result = arr[num:] if count > len(arr) / 2 else arr[:num]
print(result)
最后編輯于
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末抛猫,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子脱盲,更是在濱河造成了極大的恐慌邑滨,老刑警劉巖日缨,帶你破解...
    沈念sama閱讀 216,372評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件钱反,死亡現(xiàn)場離奇詭異,居然都是意外死亡,警方通過查閱死者的電腦和手機面哥,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評論 3 392
  • 文/潘曉璐 我一進店門哎壳,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人尚卫,你說我怎么就攤上這事归榕。” “怎么了吱涉?”我有些...
    開封第一講書人閱讀 162,415評論 0 353
  • 文/不壞的土叔 我叫張陵刹泄,是天一觀的道長。 經(jīng)常有香客問我怎爵,道長特石,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,157評論 1 292
  • 正文 為了忘掉前任鳖链,我火速辦了婚禮姆蘸,結果婚禮上,老公的妹妹穿的比我還像新娘芙委。我一直安慰自己逞敷,他們只是感情好,可當我...
    茶點故事閱讀 67,171評論 6 388
  • 文/花漫 我一把揭開白布灌侣。 她就那樣靜靜地躺著推捐,像睡著了一般。 火紅的嫁衣襯著肌膚如雪侧啼。 梳的紋絲不亂的頭發(fā)上玖姑,一...
    開封第一講書人閱讀 51,125評論 1 297
  • 那天,我揣著相機與錄音慨菱,去河邊找鬼焰络。 笑死,一個胖子當著我的面吹牛符喝,可吹牛的內(nèi)容都是我干的闪彼。 我是一名探鬼主播,決...
    沈念sama閱讀 40,028評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼协饲,長吁一口氣:“原來是場噩夢啊……” “哼畏腕!你這毒婦竟也來了?” 一聲冷哼從身側響起茉稠,我...
    開封第一講書人閱讀 38,887評論 0 274
  • 序言:老撾萬榮一對情侶失蹤描馅,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后而线,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體铭污,經(jīng)...
    沈念sama閱讀 45,310評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡恋日,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,533評論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了嘹狞。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片岂膳。...
    茶點故事閱讀 39,690評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖磅网,靈堂內(nèi)的尸體忽然破棺而出谈截,到底是詐尸還是另有隱情,我是刑警寧澤涧偷,帶...
    沈念sama閱讀 35,411評論 5 343
  • 正文 年R本政府宣布簸喂,位于F島的核電站,受9級特大地震影響燎潮,放射性物質(zhì)發(fā)生泄漏娘赴。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,004評論 3 325
  • 文/蒙蒙 一跟啤、第九天 我趴在偏房一處隱蔽的房頂上張望诽表。 院中可真熱鬧,春花似錦隅肥、人聲如沸竿奏。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽泛啸。三九已至,卻和暖如春秃症,著一層夾襖步出監(jiān)牢的瞬間候址,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評論 1 268
  • 我被黑心中介騙來泰國打工种柑, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留岗仑,地道東北人。 一個月前我還...
    沈念sama閱讀 47,693評論 2 368
  • 正文 我出身青樓聚请,卻偏偏與公主長得像荠雕,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子驶赏,可洞房花燭夜當晚...
    茶點故事閱讀 44,577評論 2 353

推薦閱讀更多精彩內(nèi)容