算法练习(16):洗牌算法的一个错误示例(1.1.37)

知识点

  • 洗牌算法
  • 随机数

1.1.37 糟糕的打乱。假设在我们的乱序代码中你选择的是一个0 到N-1 而非i 到N-1 之间的随机整数。证明得到的结果并非均匀地分布在N! 种可能性之间。用上一题中的测试检验这个版本。


1.1.37 Bad shuffling. Suppose that you choose a random integer between 0 and N-1 in our shuffling code instead of one between i and N-1. Show that the resulting order is not equally likely to be one of the N! possibilities. Run the test of the previous exercise for this version.

分析

如果你选择的是一个0 到N-1 而非i 到N-1 之间的随机整数,那代码应该是如下所示:

public static void shuffle(double[] a)
{
   int N = a.length;
   for (int i = 0; i < N; i++)
   { 
      //区别就在于这一行
      int r = StdRandom.uniform(0,N - 1);
      double temp = a[i];
      a[i] = a[r];
      a[r] = temp;
    } 
}

那有这个i和没有i的区别在哪里呢。上一题我们已经给出过Fisher–Yates shuffle 洗牌算法的推导过程:由乱序播放说开了去-数组的打乱算法Fisher–Yates Shuffle
所以,Fisher–Yates shuffle 的核心在于将数组分成两部分,每取出一部分的任意数,放到另一部分中即可。

答案

```

public static class RandomArray {
private int M = 0;
private int[] a = null;

public int[] getA() {
    return a;
}

public void setA(int[] a) {
    this.a = a;
}

public RandomArray(int M) {
    this.M = M;
    this.a = new int[M];
    for (int i = 0; i < M; i++) {
        a[i] = i;
    }
}

}

public static class RandomChecker {
private double[][] matrix = null;

public double[][] getMatrix() {
    return matrix;
}

private int M = 0;
private int N = 0;

public RandomChecker(int M, int N) {
    this.M = M;
    this.N = N;
    matrix = new double[M][];
    for (int i = 0; i < matrix.length; i++) {
        matrix[i] = new double[M];
    }
}

public void execute() {
    for (int n = 0; n < this.N; n++) {
        RandomArray c = new RandomArray(M);
        int[] a = c.getA();
        StdRandom.shuffle(a);
        for (int k = 0; k < a.length; k++) {
            int i = a[k];
            int j = k;
            matrix[i][j] += 1;
        }
    }
}

public void print() {
top Created with Sketch.