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

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

13 голосов
/ 08 июня 2009

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

Ответы [ 5 ]

14 голосов
/ 08 июня 2009

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

Очевидно, работает для n = 1 элемента, удовлетворяющего п.

Для 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.

6 голосов
/ 08 июня 2009

Да, я верю в это.

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

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

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

Я думал, что для этого у меня есть оператор LINQ в MoreLINQ, но я не могу найти его в хранилище ... РЕДАКТИРОВАТЬ: К счастью, он все еще существует с этого ответа : 

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 голосов
/ 08 июня 2009

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

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

"Обратите внимание на алгоритм выбора одного элемент наугад, когда мы не знаем, как Есть много предметов. Переменная nmatch считает количество совпадений как список сканируется. Выражение 

rand() % ++nmatch == 0

увеличивает nmatch и затем становится истинным с вероятностью 1 / nmatch. "

1 голос
/ 08 июня 2009

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

0 голосов
/ 08 июня 2009

Для ясности, я бы попробовал: 

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

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

...