选择满足一定属性的随机数组元素

Question

假设我有一个名为 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 。）

Answer 1

它在数学上是有效的。 可以用归纳法证明。

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

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

每个先验 n 都有机会以 1/n 的概率被选择，直到找到元素 n+1。 现在，找到 n+1 后，有 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。

Answer 2

是的，我相信是这样。

当你第一次遇到匹配的元素时，你肯定会选择它。 下一次，您以 1/2 的概率选择新值，因此两个元素中的每一个都有相同的机会。 接下来，您以 1/3 的概率选择新值，而其他每个元素的概率也为 1/2 * 2/3 = 1/3。

我试图找到一篇关于此策略的维基百科文章，但到目前为止失败了......

请注意，更一般地说，您只是从未知长度的序列中挑选一个随机样本。 您的序列恰好是通过获取初始序列并对其进行过滤而生成的，但该算法根本不需要该部分。

我以为我在 MoreLINQ 中有一个 LINQ 运算符来执行此操作，但我在存储库中找不到它...编辑：幸运的是，它仍然存在于 这个答案：

public static T RandomElement<T>(this IEnumerable<T> source,
                                 Random rng)
{
    T current = default(T);
    int count = 0;
    foreach (T element in source)
    {
        count++;
        if (rng.Next(count) == 0)
        {
            current = element;
        }            
    }
    if (count == 0)
    {
        throw new InvalidOperationException("Sequence was empty");
    }
    return current;
}

Answer 3

在编程实践中，第 14 页。 70、（马尔可夫链算法）有一个类似的算法：

[...]
  nmatch = 0;
  for ( /* iterate list */ )
    if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
      w = suf->word;
[...]

“注意选择一个的算法
当我们不知道如何时随机项目
有很多项目。 变量
nmatch 将匹配数计算为
列表被扫描。 表达式

rand() % ++nmatch == 0 
  

递增nmatch，然后为真
概率为 1/n 匹配。”

Answer 4

decowboy 有一个很好的证据，证明这适用于 TopCoder

Answer 5

为了清楚起见，我会尝试：

pickRandElement(elements, p)
     OrderedCollection coll = new OrderedCollection
     foreach element in elements
          if (p(element))
               coll.add(element)
     if (coll.size == 0) return null
     else return coll.get(randInt(coll.size))

对我来说，这使得你想要做的事情更加清晰，并且是自我记录的。 最重要的是，它更简单、更优雅，而且现在很明显，每个都会以均匀分布的方式被选择。