隨機選擇矩陣索引一次

Question

我有一個1的矩陣（只是一個二維矢量的整數），我試圖隨機選擇一個索引，以便我可以將該1變爲0.我的目標是選擇每個矩陣的索引恰好是一次，因此在運行for循環的迭代次數與索引次數完全相同之後，矩陣將填充0（0實際上並不重要，替換1和1的數字本身是任意）。

我目前的方法很慢。它已經運行了一個while循環來檢查每一遍以查看是否還剩1。這顯然效率很低，但我不確定如何爲每個索引只做一次，並確保沒有重複，以便我可以更改爲for循環。任何建議都會非常有幫助！

Answer 1

只需在評論中提到的@Jonny生成一個隨機的矩陣索引序列。然後遍歷這個序列的每個元素。以下是一個Java實現我萬一寫的幫助：

import java.util.Random; 

public class Test { 

    public static void randomSelectMatrixIndex(int[][] matrix) { 
     int rows = matrix.length; 
     int cols = matrix[0].length; 
     int[] indices = new int[rows*cols]; 
     System.out.println("Index array before shuffle: "); 
     for (int i=0; i<indices.length; i++) { 
      indices[i] = i; 
      System.out.print(i+" ");    
     } 
     System.out.println(); 
     System.out.println(); 

     shuffle(indices); 

     System.out.println("Index array after shuffle: "); 
     for (int j=0; j<indices.length; j++) { 
      System.out.print(indices[j]+" "); 
      matrix[indices[j]/cols][indices[j]%cols] = 0; 
     } 
     System.out.println(); 
     System.out.println(); 
    } 

    private static void shuffle(int[] indices) { 
     Random ran = new Random(); 
     for (int i=indices.length; i>0; i--) { 
      int randomIndex = ran.nextInt(i); 
      int temp = indices[i-1]; 
      indices[i-1] = indices[randomIndex]; 
      indices[randomIndex] = temp; 
     } 
    } 

    private static void printMatrix(int[][] matrix) { 
     for (int i = 0; i < matrix.length; i++) { 
      for (int j = 0; j < matrix[i].length; j++) { 
       System.out.print(matrix[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 

    public static void main(String[] args) throws Exception { 

     int[][] matrix = {{1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1}, {1,1,1,1,1}}; 

     System.out.println("Matrix before random select: "); 
     printMatrix(matrix); 
     System.out.println(); 

     randomSelectMatrixIndex(matrix); 

     System.out.println("Matrix after random select: "); 
     printMatrix(matrix); 
    } 

} 

Answer 2

您使用這種算法，這是一個比較有效的，但仍然不是很有效，經過大量的迭代（請注意，最好的結果是，使用均勻分佈的隨機數發生器）：

select random index -> check if 1 
    |     |  | 
    |  repeat  |False |True 
    |--------------------|  |--Change value at index to 0 
              | 
              | 
             the end 

我不知道是否有什麼可以改變，使其更有效率...

Answer 3

簡單。使用嵌套循環創建一個指針向量，以便有一個指向矩陣中每個單元的指針。隨機選擇一個指針。將值更改爲0.從矢量中刪除指針。重複，直到矢量爲空。矩陣現在是空的。