### 問題描述 程序最終結果用上的輸入數據只是部分（樣品），若將全部輸入放入內存再進行計算后取出結果，很可能會導致浪費掉大量的時間空間。輸入：m和n,使 0 < m < n?( m, n均為整數)。輸出：m個隨機整數的有序列表。（隨機整數不允許重復） ### 方案一：使用概率計算 ### 偽代碼 設：bigrand()能返回一個遠大于n的函數.randint(i, j)能返回一個i...j范圍內均勻選擇的隨機整數）代碼： ~~~ select = m remaining = n for i = [0, n) if (bigrand() % remaining) < select print i select— remaining-- ~~~ **錯誤思考：錯解本題** 初接觸這偽代碼，我想了很久，第一反應是，在偽代碼中，n是數值大小，m(雖然在題意看來是數量，不過從程序看來)也是數值大小，而bigrand()也是數值大小，它們的大小是包含關系，如果按這樣理解的話，如下圖： 再套進這個算法，其中有一句　if (bigrand() % remaining) < select　，是不是就意味著我選擇的數的大小都是得小于select這個數值的呢？如果是這樣，存在很大問題，[m, n)的數無法取出，達不到題目從n里面取m個隨機數的要求。 那么，現在問題是出在哪呢**?** ### 解說：正解 沒錯，select是在變小，但是，我們不可以忽略的一點是，結果輸出的不是select而是變量i，問題的根本是if真正判斷的是什么。觀察代碼時，我們可以將它們的幾個變量同時觀察，看它們間是否有聯系。設m=2, n=5，那么，假設我們進入了偽代碼中的循環語句，變量的變化如下所示：  這個算法的核心部分就是for里面的if語句，觀察可知，進入循環條件，每過一輪循環，i的值就會加1，而select的值需要視情況而定，如果bigrand()%remaining的數值符合if條件，select的數值就會加1，否則不變。至于remaing數值隨著i的增大而減小，這是碰巧嗎？三個數值間的聯系是什么？我們可以再看下圖：  假設，我們是要將結果放入到m1、m2兩個圈圈中，初始狀態時，m1、m2都為empty，remaining為5，以后仍可能輸出的i值為0、1、2、3、4五個；第1輪循環結束，可能輸出的值剩下4個，而這也與remaing的值一樣為4，此時，以后仍可能輸出的i值為1、2、3、4四個，而在剛剛的第1循環，如果符合了循環內的if(bigrand() % remaining) < select條件，m2或m1會裝入數值0（也就是說輸出了i）；就這樣進入一輪輪的循環，可以知道的是，remaining就是剩下還沒有抽取的數的個數，每一輪循環，i會增大1，可以理解為我們隨機選數的時候是從小到大計算數值是否符合條件，我們回顧原題，需要找出“有序”，“不重復”的隨機數，這里的“隨機”，我們可以從小到大篩選的原因是：我們是否進入的if條件，是一個“隨機”得出的結果，而這個“隨機”所關聯的是一個“概率”，我們從概率的角度去思考這個問題，**每個抽出的結果都能達到相同的“概率”時，即能達到“隨機”**。注意觀察還沒進入第1輪循環時，我們可取的數有5個，變量select（即圖中的m1和m2的數目一共）為2，是否進入循環，我們就看（邏輯上）是否抽中0，而抽中隨機數0（放入結果m1或m2）的概率為2/5，也就是select/k=m1/k+m2/k，那么我們如何能保證這個2/5呢？回看代碼中的if (bigrand() % remaining) < select，已知bigrand()取出的是隨機數，該隨機數取模5，即bigrand()%remaining有可能的結果是0, 1, 2, 3, 4，五個結果出現的概率是均等的，再滿足小于select=2的有0和1，也就是說，從這些均等的結果中，有1/5的(bingrand()%remaining=0)概率（可以放進m1）加上1/5的(bingrand()%remaining=1)概率(可以放進m2)，共2/5概率可以進入if條件執行if條件內的語句（放進m1或m2成為輸出的結果），這樣就保證了有2/5的概率可以取數值0作為最終結果，依此類推即可用均等的概率得出m1與m2?的值，輸出結果，達到“隨機”，“有序”的效果。 ### 方案二：逐個隨機插入 書中所講，這思路來源于一個學生，他建議“復印選區列表，用切紙機將副本切成一個個含有選區名的紙片，然后將這些紙片放入一個紙袋中并搖亂，再從中抽取需要數目的紙片。”這是一個生活中可以用上的方法，我們常說，計算機來源于生活，果然如此，這也體現了書中所講的“打破概念壁壘”的主題。偽代碼： ~~~ initialize set S to empty size = 0 while size < m do t = bigrand() % n if t is not in S insert t into S size++ print the elements of S in sorted order ~~~ **問題聯想與簡要思路提要** 這代碼看起來很簡單，我將其理解為“取樣放回再隨機抽取”，也就是從一個集合中隨機取一個數，每次取完后再將這個數放回集合中，如果下次取出的是同一個數則忽略這個結果，繼續取數，直到取得滿足條件的樣品數目為此。每次都是從總數中取一個數，那么每個數被抽中的概率必然是均等的。滿足題目“隨機”的這個條件。 我聯想到的是我以前高中常做的一道題，腦海中很容易就能反映出這個場景“有一個布袋，里面裝了n [0, 10)個標有號碼白球，每次從袋子里面取出1個球，每次取球后將球放回，問從布袋里面取出號碼xx的概率是多少？”雖然跟這題目所問的有些許不同，但是這場景實在是很像。解決題目時，聯系生活。 ### 方案三：內部亂序抽取 ~~~ for i = [0, n) swap(i, randint(i, n-1) ) // randint(i, j)從i...j范圍內均勻選擇的隨機整數的函數 ~~~ **問題聯想與簡要思路提要** 思路很簡單，將集合內部的順序打亂，然后再從這打亂中的集合取出m個數，取出來再進行排序，得出的即是結果。 ### 總結 這次對“取樣問題”進行了探討，剛開始沒有想到可以將問題優化為從數值集合中取樣的問題，更沒有想到可以由“概率”的這個角度去思考這個“隨機”的問題，又從書中解決問題的時候聯想到生活現象，書本實在能引發我的思考，解決問題時，可以先試試想想本身的問題有沒有可替換的方案，再可以想想方案還可以有哪些，思考方案的時候，還可以打破條條框框的概念，嘗試用另一種思維去思考問題。 **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8760304](http://blog.csdn.net/utimes/article/details/8760304)