[ Java 文章收集 ] Java 產生不重覆亂數

來源自 這裡 
Preface: 
這邊要產生不重覆亂數的方法，下面是三種方式，只要是暴力法都很慢，速度是O(n^2). Java要產生亂數很簡單，只要呼叫 Random 類別就可以了，不過如果想要不重覆的亂數，有一些小方法可以用，這裡提供三種方法. 

暴力比對法: 
這個 GenerateDuplicateRan 方法會接收一個整數，表示你要取得亂數的範圍，丟進去100表示你要取0~99之間的亂數: 

view plaincopy to clipboardprint?

1. public static int[] GenerateNonDuplicateRan1(int range)  
2. {  
3.     Random rand = new Random();  
4.     int rdm[] = new int[range];  
5.     List holeList = new ArrayList();  
6.     for(int i=0; i
7.       
8.     for(int i=0; i
9.     {  
10.         int pv=-1;  
11.         do{  
12.             pv = (int)(rand.nextDouble()*range);                  
13.         }while(!holeList.remove(Integer.valueOf(pv)));  
14.         rdm[i] = pv;  
15.     }  
16.     return rdm;  
17. }  

這個方法接收一個整數，表示你要取得亂數的最大範圍，呼叫 GenerateDuplicateRan(100) 則會回傳一個長度100的整數陣列，裡面就是0~99不重覆的整數。寫的方式很直覺，第一個for loop跑100次，每塞一個值就會去比對之前在陣列中的數字，如果相同就移除。缺點就是要產生大量亂數的時候很慢，因為有兩層for loop，速度是n^2，如果只是要少量亂數的人可以參考. 

Collection移出法: 
第二種方法就快多了，尤其在產生大量亂數的時候更為明顯。分成三個部分來解釋. 
1. 產生一個ArrayList，並且利用for loop塞值進去，你想要產生0~99的亂數，就丟100進去，他就會依序把0~99塞到ArrayList裡面. 
2. 用Collection的remove method，隨機的取index，並且移出，直到 ArrayList 的size = 0。因為本來在ArrayList裡面的數字就沒有重複(用for loop塞的)，所以隨機取出的值也不會重複! 
3. 最後一個部份就是去呼叫上面的方法並且宣告一個array來接收上面產生的亂數 
函數 GenerateNonDuplicateRan2 代碼如下: 

view plaincopy to clipboardprint?

1. public static int[] GenerateNonDuplicateRan2(int range)  
2. {  
3.     Random rand = new Random();  
4.     int rdm[] = new int[range];  
5.     List holeList = new ArrayList();  
6.     for(int i=0; i
7.     int cnt=0;  
8.     while(holeList.size()>0)  
9.     {  
10.         int pv = holeList.remove(rand.nextInt(holeList.size()));  
11.         rdm[cnt++] = pv;  
12.     }  
13.     return rdm;  
14. }  

HashSet 的暴力比較法: 
另一種方式是使用 HashSet unique element 的特性, 每次產生一個 random 的整數去比對 HashSet 是否已經看過, 否則就從新產生一個 random 的整數; 如果沒看過, 便將該整數加到 HashSet 與 返回的 整數陣列中: 

view plaincopy to clipboardprint?

1. public static int[] GenerateNonDuplicateRan3(int range)  
2. {  
3.     int rdm[] = new int[range];  
4.     Random rand = new Random();  
5.     HashSet set = new HashSet();  
6.     for(int i=0; i
7.     {  
8.         int pv = -1;  
9.         do  
10.         {  
11.             pv = rand.nextInt(range);  
12.         }while(!set.add(pv));  
13.         rdm[i] = pv;  
14.     }  
15.     return rdm;  
16. }  

測試代碼: 
底下是三種方法的使用代碼: 

view plaincopy to clipboardprint?

1. public static void main(String args[])  
2. {  
3.     int range = 1000;  
4.     long st = System.currentTimeMillis();  
5.     int[] rdm = Rdm.GenerateNonDuplicateRan1(range);  
6.     System.out.printf("\t[Info] GenerateNonDuplicateRan1 with Range=%d:\n", range);  
7.     long ut = System.currentTimeMillis()-st;  
8.     for(int i:rdm) System.out.printf("%d ", i);  
9.     System.out.println();  
10.     System.out.printf("\t[Info] Spending time=%d ms(%d)!\n\n", ut, rdm.length);  
11.       
12.     st = System.currentTimeMillis();  
13.     rdm = Rdm.GenerateNonDuplicateRan2(range);  
14.     System.out.printf("\t[Info] GenerateNonDuplicateRan2 with Range=%d:\n", range);  
15.     ut = System.currentTimeMillis()-st;  
16.     for(int i:rdm) System.out.printf("%d ", i);  
17.     System.out.println();  
18.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
19.       
20.     st = System.currentTimeMillis();  
21.     rdm = Rdm.GenerateNonDuplicateRan3(range);  
22.     System.out.printf("\t[Info] GenerateNonDuplicateRan3 with Range=%d:\n", range);  
23.     ut = System.currentTimeMillis()-st;  
24.     for(int i:rdm) System.out.printf("%d ", i);  
25.     System.out.println();  
26.     System.out.printf("\t[Info] Spending time=%d ms!(%d)\n\n", ut, rdm.length);  
27.       
28. }  

執行結果如下: 

[Info] GenerateNonDuplicateRan1 with Range=1000:
864 435 238 ...
[Info] Spending time=38 ms(1000)!

[Info] GenerateNonDuplicateRan2 with Range=1000:
406 821 595 ...
[Info] Spending time=1 ms!(1000)

[Info] GenerateNonDuplicateRan3 with Range=1000:
152 959 751 ...
[Info] Spending time=5 ms!(1000)

可以看的出來第二種方法最快!