选择满足一定性质的随机数组元素 [英] Choose random array element satisfying certain property

问题描述

假设我有一个名为 elements 的列表，每个元素满足或不满足某个布尔属性 p.我想通过均匀分布随机选择满足 p 的元素之一.提前不知道有多少项满足这个属性p.

Suppose I have a list, called elements, each of which does or does not satisfy some boolean property p. I want to choose one of the elements that satisfies p by random with uniform distribution. I do not know ahead of time how many items satisfy this property p.

下面的代码会这样做吗?:

Will the following code do this?:

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) 返回一个随机整数 k，其中 0 <= k .)

(randInt(n) returns a random int k with 0 <= k < n.)

推荐答案

它以数学方式工作.可以用归纳法证明.

It works mathematically. Can be proven by induction.

显然适用于满足 p 的 n = 1 元素.

Clearly works for n = 1 element satisfying p.

对于n+1个元素，我们会以1/(n+1)的概率选择第n+1个元素，所以它的概率是可以的.但这如何影响选择先验 n 个元素之一的最终概率?

For n+1 elements, we will choose the element n+1 with probability 1/(n+1), so its probability is OK. But how does that effect the end probability of choosing one of the prior n elements?

先验 n 中的每一个都有机会以 1/n 的概率被选中，直到我们找到元素 n+1.现在，在找到 n+1 之后，有 1/(n+1) 次机会选择元素 n+1，因此有 n/(n+1) 次机会选择先前选择的元素.这意味着它在 n+1 找到后被选中的最终概率是 1/n * (n/n+1) = 1/n+1 —— 这是我们想要所有 n+1 元素均匀分布的概率.

Each of the prior n had a chance of being selected with probability 1/n, until we found element n+1. Now, after finding n+1, there is a 1/(n+1) chance that element n+1 is chosen, so there is a n/(n+1) chance that the previously chosen element remains chosen. Which means its final probability of being the chosen after n+1 finds is 1/n * (n/n+1) = 1/n+1 -- which is the probability we want for all n+1 elements for uniform distribution.

如果它适用于 n = 1，并且适用于给定 n 的 n+1，那么它适用于所有 n.

If it works for n = 1, and it works for n+1 given n, then it works for all n.

这篇关于选择满足一定性质的随机数组元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！