[問題] 1-42取出6+1個數字

[遙遠的旅人]

1-42 取 7用set 的 Contains判斷不取重複可能還好。

1-20000 取 10000呢？你很快就會覺得是不是掉進無窮回圈當中了。
(如果你不幸用遞迴寫，哪很快就會stack Over Flow了。)

之前Trace JDK程式碼時有看到一個好方法給大家參考。
原理如下：

假設陣列長度n，隨機取m個。

for(int i = arr.length-1;i>=0;i--)
{
int randPosition = Random.getInt(i);//取得0~i之間的隨機整數。
Swap(arr[i], arr[randPosition]);//替換值。
}
return arr[0]~ arr[m-1];

不考慮Random的實作效能的話，程式效率為O(n)。


--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.116.116

[._.]

(舉手) 問幾個問題...

這個看起來是從陣列最後方, 隨機選一個之前的元素跟後面的置換.

然後把整個陣列 n 跑完之後, 取前面的 m 個...

那為什麼不直接後面作 m 次以後直接取後面的 m 個呢?

另外取前面 n 個, 第一個會永遠不可能是自己吧?

最後感謝你提供 (對我來說) 如此易於了解的方法.

※ 引述《zanyking (遙遠的旅人)》之銘言：
: 1-42 取 7用set 的 Contains判斷不取重複可能還好。
: 1-20000 取 10000呢？你很快就會覺得是不是掉進無窮回圈當中了。
: (如果你不幸用遞迴寫，哪很快就會stack Over Flow了。)
: 之前Trace JDK程式碼時有看到一個好方法給大家參考。
: 原理如下：
: 假設陣列長度n，隨機取m個。
: for(int i = arr.length-1;i>=0;i--)
: {
: int randPosition = Random.getInt(i);//取得0~i之間的隨機整數。
: Swap(arr[i], arr[randPosition]);//替換值。
: }
: return arr[0]~ arr[m-1];
: 不考慮Random的實作效能的話，程式效率為O(n)。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.25.148.49

[勁過呂布]

※ 引述《zanyking (遙遠的旅人)》之銘言：
: 1-42 取 7用set 的 Contains判斷不取重複可能還好。
: 1-20000 取 10000呢？你很快就會覺得是不是掉進無窮回圈當中了。
: (如果你不幸用遞迴寫，哪很快就會stack Over Flow了。)
: 之前Trace JDK程式碼時有看到一個好方法給大家參考。
: 原理如下：
: 假設陣列長度n，隨機取m個。
: for(int i = arr.length-1;i>=0;i--)
: {
: int randPosition = Random.getInt(i);//取得0~i之間的隨機整數。
: Swap(arr[i], arr[randPosition]);//替換值。
: }
: return arr[0]~ arr[m-1];
: 不考慮Random的實作效能的話，程式效率為O(n)。


從你這一個方法，我倒想到了一個較另類的高效方法 :P

假設陣列長度 n, 隨機取 m 個

int arr[] = new int[n];
for (int i = 0; i < n; i++) arr[i] = i; // initialize

int result[] = new int[m];
for (int i = 0; i < m; i++)
{
int pos = Random.nextInt(n-i); // get the position from 0 - (n-i-1)
result[i] = arr[pos];
if (pos != n-i-1) {
Swap(arr[n-i-1], arr[pos]);
}
}

return result;


只需 loop m 次就可以得到不重覆的 m 個數字了 :D

--
《為了要得到真相，就要向原 PO 伸圖》

那就是伸圖魔人的沒圖沒真相原則，那時我們堅信那就是逼逼死的真實

 靠么，圖咧？


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.79.40.97

[遙遠的旅人]

※ 引述《ogamenewbie (._.)》之銘言：
: (舉手) 問幾個問題...
: 這個看起來是從陣列最後方, 隨機選一個之前的元素跟後面的置換.
: 然後把整個陣列 n 跑完之後, 取前面的 m 個...
: 那為什麼不直接後面作 m 次以後直接取後面的 m 個呢?


當然可以阿，這樣聰明多了。

那個pseudo Code是Trace來的，我只是直接把腦子裡的東西貼上用，
看來我還消化的不夠徹底，感謝指點。

: 另外取前面 n 個, 第一個會永遠不可能是自己吧?

不會，第n-1個跟之前連自己共n個元素作Swap也有可能取到自己啊。
所以雖然機率超低也還是有機會的。

: 最後感謝你提供 (對我來說) 如此易於了解的方法.

--

JAVA 是一個靜態型別reference指定、強物件型別判定的語言。

屬於類C/C++族。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.116.116

[資源有限慾望無窮]

【 在 ***@ptt.cc (遙遠的旅人) 的大作中提到: 】
: ※ 引述《ogamenewbie (._.)》之銘言：
: : (舉手) 問幾個問題...
: : 這個看起來是從陣列最後方, 隨機選一個之前的元素跟後面的置換.
: : 然後把整個陣列 n 跑完之後, 取前面的 m 個...
: : 那為什麼不直接後面作 m 次以後直接取後面的 m 個呢?
: 當然可以阿，這樣聰明多了。
: 那個pseudo Code是Trace來的，我只是直接把腦子裡的東西貼上用，
: 看來我還消化的不夠徹底，感謝指點。
: : 另外取前面 n 個, 第一個會永遠不可能是自己吧?
: 不會，第n-1個跟之前連自己共n個元素作Swap也有可能取到自己啊。
: 所以雖然機率超低也還是有機會的。
: : 最後感謝你提供 (對我來說) 如此易於了解的方法.

我想這就是洗牌法的延伸吧

像撲克牌洗牌一樣，假設n張牌一開始都照順序排好 (陣列初始為1~n)

洗一次牌就是任選兩張牌然後彼此交換位置 (陣列中任選2位置彼此Swap值)

要洗幾次就看你想要亂數有多亂，洗越多次理論上越亂，



最後要取出m個不重複的值 就從陣列中隨機取m個位置然後取值就好

不管是1-42 或1-400000 都可以這樣做，且複雜度是一樣的 XD



--
世界上有不能流淚的哀傷存在.那是對誰也無法說明的,
就算能夠說明,誰也不會理解的那種東西.那哀傷既不能
改變成任何形式,只能像無風之夜的雪那樣靜靜地逐漸
積在心裡而已.
--

※ 來源:‧資訊傳奇 inf.csie.thu.edu.tw‧[FROM: 220-139-169-158.dynamic.hinet.]