选择满足某些属性的随机数组元素

小编典典

选择满足某些属性的随机数组元素

algorithm

假设我有一个名为的列表，elements每个列表满足或不满足某些布尔属性p。我想选择p随机分布且均匀分布的元素之一。我不知道有多少物品可以满足此属性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。）

阅读 220

2020-07-28

共1个答案

小编典典

它在数学上起作用。可以通过归纳证明。

显然适用于满足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。

2020-07-28