如何在不知道n的情況下隨機選擇n個對象中的一個？

具體而言，如果您事先不知道行數，您將如何閱讀文本行，並選擇並打印一條隨機行？如何在不知道n的情況下隨機選擇n個對象中的一個？

是的，這是一個編程珍珠，我感到困惑的問題。

該解決方案選擇1st元素，然後選擇第二個概率爲1/2，第三個爲1/3，依此類推。

的算法：

i = 0 
while more input lines 
    with probability 1.0/++i 
    choice = this input line 
print choice

假設最終選擇是第三元件，所述概率是 1×1/2 X 1/3 X 3/4 X ... X n-2個/ n-1×n-1/n == 1/2n？但1/n應該是正確的。

來源

2011-09-01 deepsky

選擇元素3的概率並不完全取決於在步驟1或2中選擇的內容。因此，這裏不包含1或1/2的項。然後是1/n。 –

謝謝。現在有道理。 – deepsky

很酷的問題，沒想過！ – unkulunkulu

你的算法是正確的，但分析不是。你可以通過歸納來證明。鬆散：它當然適用於N = 1。如果它適用於N-1，那麼N會發生什麼？選擇第N個元素並覆蓋最後一個選擇的可能性爲1/N - 好。它不是（N-1）/ N的可能性。在這種情況下，使用前一步的選擇。但是在那個時候，所有元素都有1 /（N-1）的選擇機會。現在是1/N。好。

來源

2011-09-01 07:24:22

-1

這不是真正的隨機 - 因爲你更可能在文件的開頭選擇一行。您需要知道使其隨機的行數。（50％的時間你得到第一行！）

來源

2011-09-01 07:19:19

它是隨機的。事實上它不是[統一分佈]（http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29），並沒有使它不是隨機的。 – amit

請注意，如果選擇一條線，算法不會*返回*。它只是成爲當前的選擇。它確實有效。 –

@sean - 你是對的。但在這種情況下，選擇不會是一致的。在文件結束時它會更高。 –

方法1：進行第一遍以確定有多少行。然後隨機化它。方法2：使用你提到的方法。它的工作原理，但不會給每一行選擇的機會均等。

據我所知，不可能調整方法2來給每條線選擇相同的機會。在數學上，線的數量可以無限擴展到無窮大。

來源

2011-09-01 07:22:24 Mysticial

該算法是正確的。這個程序是否處理無限的輸入流是一個不同的問題，但是，OP表明輸入的大小是有限的;它只是不知道。 –

你的計算是錯誤的：

假設最終選擇是第三元件，所述概率是 1×1/2 X 1/3 X 3/4 X ... X n-2個/ N-1 X N-1/n的

真正的概率是：

（1×1/2 + 1×1/2）X 1/3 X 3/4 X .. 。x n-2/n-1 x n-1/n == 1/n

，因爲無論你選擇2或者你不選擇2（艇員選拔2有1/2的PROBA而不是艇員選拔2的1/2 PROBA）

來源

2011-09-01 07:36:30

讀1 讀2 50％的機率要麼，保留一個，丟棄一個。閱讀3 （我們應該有1和3或2和3）。 50％的機率，丟棄其他。繼續使用通過該文件的50％的機會，這會留下2行。對任一行採取50/50並且您有一條隨機線。甚至整個文件的可能性。

來源

2011-09-08 01:40:24

你是否在暗示你的最後一句話，被選中的概率對於該算法文件中的每一行都是一樣的？因爲情況並非如此。實際的概率分佈將是指數的。 – zinglon

如何在不知道n的情況下隨機選擇n個對象中的一個？

回答

相關問題