雜談·一個(gè)神一般的隨機(jī)算法

——TechZone(Harris)

這篇文章融痛，我們從一個(gè)經(jīng)典的面試題開始講起壶笼。這個(gè)題目，可能會(huì)有很多形式雁刷，但是背后的邏輯是一樣的：如何寫出一個(gè)公平的洗牌算法覆劈。

洗牌嘛，不就是個(gè)隨機(jī)算法嗎沛励？直接搞一個(gè)數(shù)組责语，把牌全部放進(jìn)去，然后對(duì)調(diào)兩張牌目派，隨機(jī)k次即可坤候。

你要敢這樣回答，那面試官肯定會(huì)問(wèn)企蹭，k取多少呢白筹？

顯然不能是個(gè)常量，如果你取10,000谅摄，如果只有100張牌徒河，顯然太多了，如果有100,000張呢送漠？又太少了顽照。

那你可能會(huì)想，讓k隨著牌的數(shù)量變化不就行了螺男？嗯棒厘，的確，這個(gè)想法已經(jīng)比剛剛的強(qiáng)很多了下隧，但是你要敢這么回答奢人，面試官多半會(huì)壞笑然后問(wèn)你，你這個(gè)算法淆院，公平嗎何乎？
再回去看看問(wèn)題：如何寫出一個(gè)公平的洗牌算法。

剛剛忙活了那么久土辩，其實(shí)連問(wèn)題的本質(zhì)都沒(méi)有觸及支救。這題的關(guān)鍵，在于設(shè)計(jì)公平拷淘。

一個(gè)面試官面試各墨，往往看的不是你是否答對(duì)了問(wèn)題，因?yàn)橐坏烂嬖囶}启涯，答案不只一種贬堵。如果你有對(duì)題目足夠強(qiáng)的思維能力恃轩，你就是面試官要的人。如果你看到這道題黎做，一開始就是從公平入手叉跛，那么你是很優(yōu)秀的。因?yàn)楸吵鲆粋€(gè)算法很容易蒸殿，但是這種探求問(wèn)題根源的思維角度筷厘，絕不是一朝之功。這是一種不斷面對(duì)問(wèn)題宏所，不斷解決問(wèn)題而逐漸鍛煉出來(lái)的能力酥艳。

那么我們就來(lái)看看，對(duì)于這個(gè)算法楣铁，公平的定義是什么玖雁。

如果有n張牌，那么排序的可能性就是n!盖腕。我們可以生成所有的可能性，然后隨機(jī)選一個(gè)浓镜。這種算法是絕對(duì)公平的溃列。但是，復(fù)雜度太高膛薛。這個(gè)復(fù)雜度達(dá)到了听隐。因?yàn)槲覀冃枰?jì)算種排列，那么就至少需要的時(shí)間哄啄。

有的同學(xué)可能對(duì)這樣的復(fù)雜度不太感冒雅任。這是一個(gè)比還要高的復(fù)雜度。是n個(gè)2相乘咨跌，而也是n個(gè)數(shù)沪么，而這些數(shù)除了1比2小以外，其他的數(shù)都≥2锌半。而已經(jīng)是指數(shù)爆炸了禽车，在n≥4的時(shí)候，以極快的速度超越刊殉。

這個(gè)算法的確是公平的殉摔，但是時(shí)間不能允許。

我們?cè)贀Q一種角度去思考公平的問(wèn)題记焊。公平其實(shí)也可以理解為逸月，我們每一張牌出現(xiàn)在每一個(gè)位置的概率都相等。這個(gè)定義和上面提到的暴力算法其實(shí)是等價(jià)的遍膜，學(xué)過(guò)概率論的同學(xué)可以去證明下碗硬。根據(jù)這個(gè)定義腐缤，我們就可以很快寫出一個(gè)簡(jiǎn)單的算法：

for (int i = n-1; i >= 0; i--)
    swap(arr[i], arr[rand() % (i +1)]);

說(shuō)它簡(jiǎn)單，是因?yàn)榫鸵粚友h(huán)肛响。

小伙伴們可以看看這個(gè)循環(huán)在干什么岭粤。其實(shí)就是將下標(biāo)為i的元素，和一個(gè)隨機(jī)下標(biāo)的元素交換位置特笋。而為了確保隨機(jī)的數(shù)在[0,i]的范圍內(nèi)剃浇，我們用了取余運(yùn)算除以(i+1)。

這個(gè)算法就是大名鼎鼎的 Knuth-Shuffle猎物，即 Knuth 洗牌算法虎囚。

原理待會(huì)兒再講，我們先來(lái)看看這個(gè)傳奇般的人物蔫磨。

中文名:高納德淘讥。算法理論的創(chuàng)始人。我們現(xiàn)在所使用的各種算法復(fù)雜度分析的符號(hào)堤如，就是他發(fā)明的蒲列。上世紀(jì)60-70年代計(jì)算機(jī)算法的黃金時(shí)期,近乎就是他一手主導(dǎo)的。他的成就實(shí)在是太多搀罢，一本書估計(jì)都寫不完蝗岖。

大家最津津樂(lè)道的，就是他所寫的《The Art of Computer Programming 》榔至，簡(jiǎn)稱TAOCP 抵赢。這套書準(zhǔn)備寫七卷，然后唧取，到今天還沒(méi)有寫完铅鲤，但已經(jīng)被《科學(xué)美國(guó)人》評(píng)為可以媲美相對(duì)論的巨著。微軟還是IT界老大的時(shí)代枫弟，蓋茨就說(shuō)過(guò)邢享，如果你看完了這套書的第一卷本，那你直接給我發(fā)簡(jiǎn)歷媒区。

TAOCP

至于這套書為什么寫這么慢驼仪，因?yàn)槔项^子當(dāng)時(shí)寫這本書，寫到一半覺(jué)得時(shí)下的排版工具都太爛了袜漩，于是轉(zhuǎn)手就發(fā)明了現(xiàn)在流行的LaTeX……

另外绪爸，他可能也覺(jué)得當(dāng)時(shí)的所有編程語(yǔ)言都無(wú)法描述自己的思想，于是自己發(fā)明了一套抽象邏輯語(yǔ)言用于展示這套書的邏輯部分……

（感受到了和大佬的差距）

下面這句話宙攻，和大家共勉：

A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
——Donald E. Knuth 1978

下面就來(lái)看看具體是怎么通過(guò)這樣一個(gè)簡(jiǎn)單的算法來(lái)實(shí)現(xiàn)絕對(duì)公平的奠货。

其實(shí)，可怕的地方座掘，就在于太簡(jiǎn)單……
我們用5個(gè)數(shù)字來(lái)簡(jiǎn)單模擬下這個(gè)算法：

1 2 3 4 5

這個(gè)算法递惋，會(huì)在5個(gè)元素中選出一個(gè)元素和最后一個(gè)元素交換柔滔。假設(shè)我們選擇3。就變成這樣：

1 2 5 4 3

那么這個(gè)3出現(xiàn)在最后的概率是多少呢萍虽？從5個(gè)里面挑嘛睛廊，那肯定是嘛。

再選一個(gè)杉编，假設(shè)選到了1超全，那么就變成這樣：

4 2 5 1 3

這個(gè)1出現(xiàn)在這個(gè)位置的概率又是多少呢？

上面那一輪邓馒，1沒(méi)被挑走嘶朱，而這一輪里面挑走了。

還是等于光酣！

繼續(xù)疏遏，假設(shè)這次是2。

4 5 2 1 3

概率依舊

假設(shè)下一個(gè)是4救军，那么

5 4 2 1 3

概率

而這樣5就只能在第一個(gè)位置了财异，概率還是

大家看到了，自始至終缤言，所有的位置出現(xiàn)的概率都是相等的宝当，如果數(shù)組長(zhǎng)度是n，那么每個(gè)位置的概率就是胆萧，而復(fù)雜度，比少了太多太多……

這個(gè)算法不僅僅可以用來(lái)洗牌俐东，很多場(chǎng)景下的隨機(jī)都可以使用跌穗。大家可以自己思考下，也可以運(yùn)用于實(shí)際的解題甚至是開發(fā)之中虏辫。

其實(shí)大家應(yīng)該有感覺(jué)了蚌吸，算法絕對(duì)不是枯燥的邏輯堆砌，而是神一般的邏輯創(chuàng)造砌庄。這個(gè)世界也是如此羹唠，盡管極其復(fù)雜，變化萬(wàn)千娄昆，但又竟是如此簡(jiǎn)潔佩微，巧妙而優(yōu)雅……