Fisher-Yatesシャッフルとリザーバサンプリングの違い

Question

私は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; 
} 

私は両方の背後にある数学は同じですが、私はなぜ知らないと思います。 Btw、stackoverflowでコードを入力するとmarkdownを使用する必要はありません。素晴らしい！ 、あなたはメートル  ×  n個細胞を持っており、それらのKを選びたい、あなたのマインスイーパ例えば

+--------------+----------------+-----------------------------+------+-------+ 
| 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 |  |  | 
+--------------+----------------+-----------------------------+------+-------+ 

：

Answer 1

2つの違いは、彼らが異なることを行うということですこれはまさにリザーバのサンプリングがするものです。だから概念的には私にはもっと適切だと思われる。しかし、あなたはとにかくをO（メートル  ×  N）スペースを使用すると、あなたの全体の問題は、おそらく実際にパフォーマンスを心配するのに十分な大きさではないので、私はフィッシャー–イエーツのアプローチは大丈夫だと思うので、 、あまりにも。 （両方とも数学的には音です）