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

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

Answer 1

它以数学方式工作.可以通过归纳证明.

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

对于n + 1个元素,我们将选择概率为1 /(n + 1)的元素n + 1,因此其概率为OK.但是,这会如何影响选择前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;
}