algorithm - Fisher-Yates 随机抽样和水库抽样之间的区别

Question

我知道F-Y和reservoir sampling都可以实现shuffle array。比如我们在一个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。太棒了!

Answer 1

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

+--------------+----------------+-----------------------------+------+-------+
| 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 方法也很好。 (它们在数学上都是合理的。)