知識(shí)點(diǎn)
- 洗牌算法
- 隨機(jī)數(shù)
1.1.36 亂序檢查。通過(guò)實(shí)驗(yàn)檢查表1.1.10 中的亂序代碼是否能夠產(chǎn)生預(yù)期的效果。編寫(xiě)一個(gè)程序ShuffleTest，接受命令行參數(shù)M 和N，將大小為M 的數(shù)組打亂N 次且在每次打亂之前都將數(shù)組重新初始化為a[i] = i。打印一個(gè)M×M 的表格，對(duì)于所有的列j，行i 表示的是i 在打亂后落到j(luò) 的位置的次數(shù)。數(shù)組中的所有元素的值都應(yīng)該接近于N/M。
1.1.36 Empirical shuffle check. Run computational experiments to check that our shuffling code on page 32 works as advertised. Write a program ShuffleTest that takes command-line arguments M and N, does N shuffles of an array of size M that is initialized with a[i] = i before each shuffle, and prints an M-by-M table such that row i gives the number of times i wound up in position j for all j. All entries in the array should be close to N/M.
分析
表1.1.10 中的亂序代碼如下：
public static void shuffle(double[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{ // Exchange a[i] with random element in a[i..N-1]
int r = i + StdRandom.uniform(N-i);
double temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
下面我們來(lái)分析一下shuffle這個(gè)單詞
shuffle
英 ['??f(?)l] 美 ['??fl]
v. 洗牌；推諉，推卸；拖曳，慢吞吞地走；攪亂
n. 洗牌，洗紙牌；混亂，蒙混；拖著腳走
其實(shí)關(guān)于洗牌算法有很多，大概百度一下可以看到如下算法：
Fisher–Yates shuffle 洗牌算法
Fisher–Yates shuffle 算法是一個(gè)用來(lái)將一個(gè)有限集合生成一個(gè)隨機(jī)排列的算法（數(shù)組隨機(jī)排序）。這個(gè)算法生成的隨機(jī)排列是等概率的。同時(shí)這個(gè)算法非常高效。
Fisher and Yates 的原始版
Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher（上圖） 和 Frank Yates 寫(xiě)的書(shū)中，書(shū)名為《Statistical tables for biological, agricultural and medical research》。他們使用紙和筆去描述了這個(gè)算法，并使用了一個(gè)隨機(jī)數(shù)表來(lái)提供隨機(jī)數(shù)。它給出了 1 到 N 的數(shù)字的的隨機(jī)排列，具體步驟如下：
- 寫(xiě)下從 1 到 N 的數(shù)字
- 取一個(gè)從 1 到剩下的數(shù)字（包括這個(gè)數(shù)字）的隨機(jī)數(shù) k
- 從低位開(kāi)始，得到第 k 個(gè)數(shù)字（這個(gè)數(shù)字還沒(méi)有被取出），把它寫(xiě)在獨(dú)立的一個(gè)列表的最后一位
- 重復(fù)第 2 步，直到所有的數(shù)字都被取出
- 第 3 步寫(xiě)出的這個(gè)序列，現(xiàn)在就是原始數(shù)字的隨機(jī)排列
已經(jīng)證明如果第 2 步取出的數(shù)字是真隨機(jī)的，那么最后得到的排序一定也是。
現(xiàn)代方法
Fisher–Yates shuffle 算法的現(xiàn)代版本是為計(jì)算機(jī)設(shè)計(jì)的。由 Richard Durstenfeld 在1964年 描述。并且是被 Donald E. Knuth 在 《The Art of Computer Programming》 中推廣。但是不管是 Durstenfeld 還是 Knuth，都沒(méi)有在書(shū)的第一版中承認(rèn)這個(gè)算法是 Fisher 和 Yates 的研究成果。也許他們并不知道。不過(guò)后來(lái)出版的 《The Art of Computer Programming》提到了 Fisher 和 Yates 貢獻(xiàn)。
現(xiàn)代版本的描述與原始略有不同，因?yàn)槿绻凑赵挤椒ǎ薮赖挠?jì)算機(jī)會(huì)花很多無(wú)用的時(shí)間去計(jì)算上述第 3 步的剩余數(shù)字。這里的方法是在每次迭代時(shí)交換這個(gè)被取出的數(shù)字到原始列表的最后。這樣就將時(shí)間復(fù)雜度從 O(n^2) 減小到了 O(n)。
inside-out算法
是一種重新檢驗(yàn)隨機(jī)上下文無(wú)關(guān)文法（probabilistic context-free grammar）生成幾率的方式，由James K. Baker 於1979年提出，是一個(gè)一般化的向前向後演算法，用來(lái)作為隨機(jī)上下文無(wú)關(guān)文法其隱馬爾可夫模型的屬性評(píng)估。這種演算法是用來(lái)計(jì)算某種期望值，舉例來(lái)說(shuō)，可以用來(lái)成為最大期望算法（一種無(wú)監(jiān)督的學(xué)習(xí)演算法）的一部分。
最后給出兩種算法的代碼實(shí)現(xiàn)：
見(jiàn)小專欄算法練習(xí)(15):驗(yàn)證洗牌算法的正確性(1.1.36)
