知识点
- 洗牌算法
- 随机数
1.1.36 乱序检查。通过实验检查表1.1.10 中的乱序代码是否能够产生预期的效果。编写一个程序ShuffleTest，接受命令行参数M 和N，将大小为M 的数组打乱N 次且在每次打乱之前都将数组重新初始化为a[i] = i。打印一个M×M 的表格，对于所有的列j，行i 表示的是i 在打乱后落到j 的位置的次数。数组中的所有元素的值都应该接近于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;
}
}
下面我们来分析一下shuffle这个单词
shuffle
英 ['ʃʌf(ə)l] 美 ['ʃʌfl]
v. 洗牌；推诿，推卸；拖曳，慢吞吞地走；搅乱
n. 洗牌，洗纸牌；混乱，蒙混；拖着脚走
其实关于洗牌算法有很多，大概百度一下可以看到如下算法：
Fisher–Yates shuffle 洗牌算法
Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。这个算法生成的随机排列是等概率的。同时这个算法非常高效。
Fisher and Yates 的原始版
Fisher–Yates shuffle 的原始版本，最初描述在 1938 年的 Ronald Fisher（上图） 和 Frank Yates 写的书中，书名为《Statistical tables for biological, agricultural and medical research》。他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。它给出了 1 到 N 的数字的的随机排列，具体步骤如下：
- 写下从 1 到 N 的数字
- 取一个从 1 到剩下的数字（包括这个数字）的随机数 k
- 从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位
- 重复第 2 步，直到所有的数字都被取出
- 第 3 步写出的这个序列，现在就是原始数字的随机排列
已经证明如果第 2 步取出的数字是真随机的，那么最后得到的排序一定也是。
现代方法
Fisher–Yates shuffle 算法的现代版本是为计算机设计的。由 Richard Durstenfeld 在1964年 描述。并且是被 Donald E. Knuth 在 《The Art of Computer Programming》 中推广。但是不管是 Durstenfeld 还是 Knuth，都没有在书的第一版中承认这个算法是 Fisher 和 Yates 的研究成果。也许他们并不知道。不过后来出版的 《The Art of Computer Programming》提到了 Fisher 和 Yates 贡献。
现代版本的描述与原始略有不同，因为如果按照原始方法，愚蠢的计算机会花很多无用的时间去计算上述第 3 步的剩余数字。这里的方法是在每次迭代时交换这个被取出的数字到原始列表的最后。这样就将时间复杂度从 O(n^2) 减小到了 O(n)。
inside-out算法
是一种重新检验随机上下文无关文法（probabilistic context-free grammar）生成几率的方式，由James K. Baker 於1979年提出，是一個一般化的向前向後演算法，用來作为随机上下文无关文法其隱馬爾可夫模型的属性評估。这种演算法是用來计算某种期望值，举例来说，可以用來成为最大期望算法（一种无监督的学习演算法）的一部分。
最后给出两种算法的代码实现：
网友评论