习题1.1.37
糟糕的打乱。假设在我们的乱序代码中你选择的是一个 0 到 N-1 而非 i 到 N-1 之间的随机整数。证明得到的结果并非均匀地分布在 N! 种可能性之间。用上一题中的测试检验这个版本。
要点分析
一.
这里我们再次给出Shuffle方法的实现:
public static void shuffle(double[] a) { int N = a.length; for (int i = 0; i < N; i++) { // 将 a[i]和in a[i..N-1] 中任意一个元素交换 int r = i + StdRandom.uniform(N-i); double temp = a[i]; a[i] = a[r]; a[r] = temp; } }
题目中将 0到 N-1而非 i 到 N-1,即改动的是 r 的赋值语句:
public static void shuffle(double[] a) { int N = a.length; for (int i = 0; i < N; i++) { // 将 a[i]和in a[i..N-1] 中任意一个元素交换 int r = 0 + StdRandom.uniform(N-i); //将i改为0 double temp = a[i]; a[i] = a[r]; a[r] = temp; } }
其实此时的
0 + StdRandom.uniform(N-i);
就相当于(课本第19页)
StdRandom.uniform(0,N-i);
也就是返回一个从[ 0, N-i )之间的一个int值
而之前的
i + StdRandom.uniform(N-i);
就相当于
StdRandom.uniform(i,N);
二.
那么上面提到的
StdRandom.uniform(0,N - i);
和改动之前的
StdRandom.uniform(i,N);
有什么不同呢?
这里我在查阅了kyson老师的专栏后[1],了解到这正是著名的洗牌算法的核心所在:Fisher–Yates shuffle 的核心在于将数组分成两部分,每取出一部分的任意数,放到另一部分中即可。
以[ i, N)为例,比如此时i = ,2,N = 5,则将a[2] 和 a[2] 或 a[3] 或 a[4] 交换
而[0,N – i)的话,此时i = 2,N = 5,则是将a[2] 和 a[0] 或 a[1] 或 a[1] 交换
这样就会导致最后的结果分布不是1/(N!),所以[ 0, N-i )是不符合这个要求的。
另外,课本中给出shuffle方法的是从数组的第一个元素开始,我们也可以从数组的最后一个元素开始,即:
随机从数组中抽出一个元素,然后与最后个元素交换,相当于把这个随机抽取的元素放到了数组最后面去,表示它已经是被随机过了,同时被换走的那个元素跑到前面去了,会在后续的重复操作中被随机掉。一轮操作过后,下一轮我们只在剩下的n-1个元素也就是数组的前n-1个元素中进行相同的操作,直到进行到第一个[2]
最后我们用答案检验一下我们上面的理论是否正确吧!
参考答案
import edu.princeton.cs.algs4.StdRandom; public class Thirty_seven { /** * @description: 将大小为N的数组,打乱N次 * @param: a 要打乱的数组 * @return: 已经打乱完成的数组 */ public static void shuffle(double[] a) { int N = a.length; for (int i = 0; i < N; i++) { // 将 a[i]和in a[0..N-1] 中任意一个元素交换 int r = 0 + StdRandom.uniform(N-i); double temp = a[i]; a[i] = a[r]; a[r] = temp; } } /** * @description: 初始化数组 * @param: a:需要初始化的数组 * @return: Nothing */ public static void array_initialization(double[] a) { for (int i = 0; i < a.length ; i++) { a[i] = i; } } /** * @description: 将数组打乱N次 * @param: N 打乱N次 * @param: a 要打乱的数组 * @return: 存储M * M这个表格的数组 */ public static double[][] upset(int N,double[] a) { double[][] count = new double[a.length][a.length]; //初始化用于存储M * M这个表格的数组 for (int i = 0; i < N; i++) { array_initialization(a); //打乱前重新初始化 // StdRandom.shuffle(a); //打乱数组 shuffle(a); //打乱数组 compute(a,count); //计算要打印的表格的值 } return count; } /** * @description: 计算M * M 表格中,每个元素的值 * @param: a 已经打乱的数组a * @param: count 存储M * M表格的数组 * @return: Nothing */ public static void compute(double[] a,double[][] count) { double[] b = new double[a.length]; array_initialization(b); //初始化数组b,用来和已经打乱的数组a比较 int c,d; for (int i = 0; i < a.length; i++) { c = (int)a[i]; d = (int)b[i]; count[c][d] += 1.0; //行i表示i在打乱后落到j的次数行i表示i在打乱后落到j的次数 } } /** * @description: 打印一个M * M 的表格, * @param: count:存储打印信息的数组 * @return: Nothing */ public static void print(double[][] count) { for (int i = 0; i < count.length; i++) { for (int j = 0; j < count.length; j++) { System.out.print(count[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { int M = Integer.parseInt(args[0]); int N = Integer.parseInt(args[1]); double[] a = new double[M]; print(upset(N,a)); } } 从命令行中输入 M = 4,N = 5 输出: 0.0 2.0 1.0 2.0 0.0 1.0 3.0 1.0 0.0 2.0 1.0 2.0 5.0 0.0 0.0 0.0
参考资料
[1] Kyson老师专栏
[2] 刘哇勇的部落格
请登录之后再进行评论