Выберите случайный элемент массива, удовлетворяющий определенному свойству

Предположим, у меня есть список, называемый 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.)

Ответ 1

Это работает математически. Может быть доказано индукцией.

Ясно работает для элемента n = 1, удовлетворяющего p.

Для n + 1 элементов мы выберем элемент n + 1 с вероятностью 1/(n + 1), поэтому его вероятность ОК. Но как это влияет на конечную вероятность выбора одного из предыдущих n элементов?

Каждый из предыдущих 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 элементов для равномерного распределения.

Если он работает для n = 1, и он работает для n + 1, заданного n, то он работает для всех n.

Ответ 2

Да, я так считаю.

В первый раз, когда вы сталкиваетесь с соответствующим элементом, вы определенно выбираете его. В следующий раз вы выберете новое значение с вероятностью 1/2, чтобы каждый из двух элементов имел равные шансы. В следующий раз вы выбираете новое значение с вероятностью 1/3, оставляя каждый из других элементов с вероятностью 1/2 * 2/3 = 1/3.

Я пытаюсь найти статью в Википедии об этой стратегии, но пока не удается...

Обратите внимание, что в более общем плане вы просто выбираете случайную выборку из последовательности неизвестной длины. Ваша последовательность генерируется, беря начальную последовательность и фильтруя ее, но алгоритм не требует этой части вообще.

Я думал, что для этого в LINK-операторе в MoreLINQ мне понадобится оператор LINQ, но я не могу найти его в репозитории... EDIT: К счастью, он все еще существует из this ответить:

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;
}

Ответ 3

В Практике программирования, стр. 70, (Алгоритм цепи Маркова) существует аналогичный алгоритм для этого:

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

"Обратите внимание на алгоритм выбора одного случайным образом, когда мы не знаем, как многие предметы есть. Переменная nmatch подсчитывает количество совпадений как список проверяется. Выражение
rand() % ++nmatch == 0
увеличивает nmatch и в этом случае true с вероятностью 1/nmatch. "

Ответ 4

У decowboy есть хорошее доказательство того, что это работает на TopCoder

Ответ 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))

Для меня это намного облегчает то, что вы пытаетесь сделать, и самодокументируетесь. Кроме того, он проще и элегантнее, и теперь очевидно, что каждый будет выбран с четным распределением.