algorithm - Fisher-Yates混洗与水库采样之间的差异

我知道f-y和储层取样都可以实现洗牌排列。例如，我们在m*n的扫雷板上部署了k枚炸弹。
我已经完成了示例代码：

public int[][] init2(int width, int length, int num){
    int[][] board = int[width][length];
    int[] bomb = new int[num];
    for(int i =0; i<num; i++){
        bomb[i] = i;
    }
    Random rand = new Random();
    for(int i = num; i<width*length; i++){
        int pos = rand.nextInt(i);
        if(pos < num){
            bomb[pos] = i;
        }
    }
    // TO DO
    // and then restore the pos to board
}

// Fisher–Yates shuffle
public int[][] init3(int width, int length, int num){
    int[][] board = int[width][length];
    for(int i =0; i<num; i++){
        board[i%width][i/width] = 1;
    }
    Random rand = new Random();
    for(int i = num; i<width*length; i++){
        int pos = rand.nextInt(i+1);
        swap(board, i, pos);
    }
}

public void swap(int[][] board, int pos1, int pos2){
    int temp = board[pos1%width][pos1/width];
    board[pos1%width][pos1/width] = board[pos2%width][pos2/width];
    board[pos2%width][pos2/width] = temp;
}

我认为两者背后的数学原理是一样的，但我不知道为什么。
顺便说一下，如果我们在stackoverflow上输入代码，似乎不需要使用markdown太神了！

最佳答案

两者的区别在于它们做的事情不同：

+--------------+----------------+-----------------------------+------+-------+
| ALGORITHM    | INPUT(S)       | OUTPUT                      | TIME | SPACE |
+--------------+----------------+-----------------------------+------+-------+
| FISHER-YATES | n elements     | A list containing all n     | O(n) | O(n)  |
| SHUFFLE      |                | elements in a random order  |      |       |
+--------------+----------------+-----------------------------+------+-------+
| RESERVOIR    | n elements and | A set containing k of the n | O(n) | O(k)  |
| SAMPLING     | an integer k   | elements, selected randomly |      |       |
+--------------+----------------+-----------------------------+------+-------+

以扫雷艇为例，您有m×n个单元，希望选择其中的k个，这正是水库采样的作用所以这在概念上更适合我。但既然你打算使用O（m×n）空间，而且由于你的整个问题可能还不足以真正担心性能，我认为Fisher-Yates方法也不错（它们在数学上都是正确的。）