假设我有一个名为的列表，elements每个列表满足或不满足某些布尔属性p。我想选择p随机分布且均匀分布的元素之一。我不知道有多少物品可以满足此属性p。
elements
p
以下代码会这样做吗？：
pickRandElement(elements, p) randElement = null count = 0 foreach element in elements if (p(element)) count = count + 1 if (randInt(count) == 0) randElement = element return randElement
（randInt(n)返回一个随机INT k与0 <= k < n。）
randInt(n)
k
0 <= k < n
它在数学上起作用。可以通过归纳证明。
显然适用于满足p的n = 1个元素。
对于n + 1个元素，我们将选择概率为1 /（n + 1）的元素n + 1，因此其概率为OK。但是，这如何影响选择前n个元素之一的最终概率呢？
在找到元素n + 1之前，每个先验n都有机会以1 / n的概率被选择。现在，在找到n + 1之后，有一个（/ n + 1）机会选择了元素n + 1，因此有一个（/ n + 1）机会使先前选择的元素保持选中状态。这意味着在n + 1次发现之后被选择的最终概率为1 / n *（n / n + 1）= 1 / n + 1-这是我们希望所有n + 1个元素均匀分布的概率。
如果它适用于n = 1，并且适用于给定n的n + 1，则适用于所有n。
