Java 產生不重覆亂數

Lab的人要我給他一個產生不重覆亂數的方法,下面是兩種方式,第一種很慢,速度是O(n^2)被幹詰到死XDD

Java要產生亂數很簡單,只要呼叫Random類別就可以了,不過如果想要不重覆的亂數,有一些小方法可以用,這裡提供兩種方法:

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



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

(2) Collection移出法
第二種方法就快多了,尤其在產生大量亂數的時候更為明顯。分成三個部分來解釋:
  • 產生一個ArrayList,並且利用for loop塞值進去,你想要產生0~99的亂數,就丟100進去,他就會依序把0~99塞到ArrayList裡面。
  • 這個部份就是trick所在,裡用Collection的remove method,隨機的取index,並且移出,直到ArrayList的size = 0。因為本來在ArrayList裡面的數字就沒有重複(用for loop塞的),所以隨機取出的值也不會重複。

  • 最後一個部份就是去呼叫上面的方法並且宣告一個array來接收上面產生的亂數。


[UPDATE 2009/04/07]
強者我同學bluesway寫了一個比我快的版本(我也沒有覺得我的很快啦...),用的資料結構是Hash,大家可以參考XD


Share this post!

Bookmark and Share

3 意見:

匿名 提到...

這種方法的缺點是:
ArrayList.remove(i) 會把 i+1~n-1 之間的元素往前搬一格,
一旦 n 變大,搬動的工夫會很恐怖...

建議看看以下兩篇文章:

1. 產生數字不重複的亂數數列(2)

2. Fisher-Yates shuffle

Unknown 提到...

有看到使用Fisher-Yates方法實做的方法,的確快很多啊!

mickeyboss 提到...

public Test(int random_size)?????
public void Test(int random_size)
呵呵...