洗牌算法是一種非常巧妙但又很好理解的算法
用于從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ù)
- 我們來遍歷這個數(shù)組,第一個元素是1卵贱,假設我們隨機到了它跟4這個元素交換為止滥沫,數(shù)組變?yōu)閧4,2,3,1,5}。任意一個數(shù)在第一位的概率都是1/5
- 繼續(xù)遍歷键俱,第二個元素是2兰绣,我們從第2個到第5個這4個元素中隨機,假設我們隨機到了2本身编振,那么數(shù)組還是{4,2,3,1,5}缀辩。這個算法牛逼的地方到了,因為2逃過了第一輪交換,且在第二輪被選中臀玄,那么它出現(xiàn)在第二位的概率是4/5*1/4=1/5
- 繼續(xù)遍歷瓢阴,第三個元素是3,我們從第3個到第5個這3個元素中隨機健无,假設我們隨機到了5炫掐,數(shù)組變?yōu)閧4,2,5,1,3}。5出現(xiàn)在第三位的概率是4/53/41/3=1/5
- 繼續(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
- 最后剩下的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)