從文本文件中選擇K個隨機線

Question

這是從X行文本中選擇隨機行的原始問題的擴展，其中文本行選擇的概率爲1/X。訣竅在於如果查詢範圍爲[0,1）的隨機變量Y並返回小於1/J的值，則選擇第J行。

現在在這個新版本的問題中，我們必須選擇K個小於X的隨機線。我相信每條線的概率應該是K/X。

我被困在如何將原始解決方案擴展到K行。可能嗎？任何解釋都會很棒。

Answer 1

這可以使用原始算法的推廣來解決。直覺如下：從文件中維護k個候選行的列表，這些行最初被播種到前k行。然後，從該點開始，在看到該文件的第n行時：

• 選擇1和n之間的隨機值x（含）。
• 如果x> k，則忽略此元素。
• 否則，將元素x替換爲文件的第n行。

證明，這種正確的樣品每個概率是k元件/ n，其中n是文件中的行的總數，如下。假設n ≥ k。我們通過歸納法證明每個元素具有被拾取的概率k/n，通過顯示在看到z個元素之後，每個元素具有被選擇的概率k/z。特別是，這意味着在看到n個元素之後，每個元素都有根據需要的概率k/n。

作爲我們的歸納基礎，如果我們看到正好有k個元素，那麼每個元素都被挑選出來。因此，根據需要選擇的概率是k/k。對於感應步驟，假設對於某些z ≥ k，每個前z個元素已經以概率k/z選擇並考慮第（z + 1）個st元素。我們在範圍[1，z + 1]中選擇一個隨機自然數。以概率k /（z + 1），我們決定選擇這個元素，然後驅逐一些舊的元素。這意味着新元素以概率k /（z + 1）選擇。對於z個原始元素中的每一個，它在這一點上選擇的概率就是我們在檢查了第一個z元素（概率k/z，由我們的歸納假設）之後選擇它的概率，以及我們保留它是z /（z + 1），因爲我們用概率1 /（z + 1）代替它。因此，它選擇的新概率是（k/z）（z /（z + 1））= k /（z + 1）。因此，所有第一z + 1元素都以概率k /（z + 1）選擇，完成歸納。此外，該算法在O（n）時間內運行並且僅使用O（k）空間，這意味着運行時間與k的值無關。要看到這一點，請注意每次迭代都會運行O（1），並且總共有O（n）個交互。

如果您好奇，我將該算法的實現作爲C++ STL樣式算法available here on my personal site。

希望這會有所幫助！

Answer 2

首先使用第一種算法從X行中隨機選擇第一個元素。然後從其餘的X-1線中選擇第二個。運行這個過程K次。

任何給定的一組K行的概率是(X choose K)。我會留給你，以驗證這個算法給出了所需的均勻分佈。