擅长:python、mysql、java
<p>“硬”的方法,而不是简单地乱翻列表,而是按顺序评估列表中的每一个元素,并以一种既依赖于你仍然需要选择的项目的数量,也依赖于可供选择的项目数量来选择项目。如果您没有将整个列表一次呈现给您(一种所谓的在线算法),这将非常有用。在</p>
<p>假设您需要选择<code>k</code>,其中<code>N</code>项。{cd3>每一个项目都有一次被选中的可能性。但是,如果您接受第一个项目,那么您只需要从<code>N-1</code>个项目中选择<code>k-1</code>个项目。如果您拒绝它,您仍然需要<code>k</code>个项目,这些项目来自<code>N-1</code>个项目。所以算法看起来像</p>
<pre><code>N = len(id_list)
k = 10 # For example
choices = []
for i in id_list:
if random.randint(1,N) <= k:
choices.append(i)
k -= 1
N -= 1
</code></pre>
<p>最初,第一个项目的选择概率为<code>k/N</code>。当你浏览你的列表时,<code>N</code>会逐渐减少,而{<cd1>}则会随着你实际接受项目而减少。请注意,总的来说,每个项目仍然有<code>p = k/N</code>被选中的机会。以列表中的第二项为例。让<code>pi</code>是您选择列表中第<code>i</code>个元素的概率。<code>p1</code>显然是{<cd3>},给定<code>k</code>和{<cd2>}的起始值。以<code>p2</code>为例。在</p>
^{pr2}$
<p>类似的(但更长的)分析适用于<code>p3</code>,<code>p4</code>等</p>