14

假设我有一个名为 的列表，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)的随机整数。）k0 <= k < n

4

5 回答 5

14

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

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

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

在我们找到元素 n+1 之前，每个先前的 n 都有机会以 1/n 的概率被选中。现在，在找到 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。

于 2009-06-08T18:38:18.410 回答
6

是的，我相信是的。

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

我正在尝试查找有关此策略的 Wikipedia 文章，但到目前为止失败了...

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

我以为我在 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;
}
于 2009-06-08T17:59:51.160 回答
3

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

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

“当我们不知道有多少项目时，请注意随机选择一项的算法。变量 nmatch 在扫描列表时计算匹配的数量。表达式

rand() % ++nmatch == 0

递增 nmatch，然后以 1/nmatch 的概率为真。"

于 2009-06-08T18:13:56.317 回答
1

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

于 2009-06-08T19:13:52.257 回答
0

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

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))

对我来说，这让你更清楚你想要做什么并且是自我记录。最重要的是，它更简单、更优雅，现在很明显，每一个都将以均匀分布的方式被挑选出来。

于 2009-06-08T18:12:22.357 回答