Выберите случайный элемент массива, удовлетворяющий определенное свойство
Для любого, кто запутался в множественном троичном синтаксисе (как я), это выглядит так:
var yourVar = condition1 ? someValue
: condition2 ? anotherValue
: defaultValue;
Вы можете добавить столько условий, сколько захотите.
Вы можете прочитать далее https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Conditional_Operator
5 ответов
Это работает математически. Может быть доказано по индукции.
Очевидно, работает для n = 1 элемента, удовлетворяющего p.
Для n + 1 элемента мы выберем элемент n + 1 с вероятностью 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 + 1 при данном n, то он работает для всех n.
Да, я так считаю.
Когда вы впервые встречаетесь с совпадающим элементом, вы обязательно выбираете его. В следующий раз вы выбираете новое значение с вероятностью 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;
}
В Практика программирования , стр. 70, (Алгоритм цепи Маркова) для этого есть аналогичный алгоритм:
[...]
nmatch = 0;
for ( /* iterate list */ )
if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
w = suf->word;
[...]
«Обратите внимание на алгоритм выбора одного элемент наугад, когда мы не знаем как есть много предметов. Переменная nmatch считает количество совпадений как список просматривается. Выражение
rand ()% ++ nmatch == 0увеличивает nmatch и затем принимает значение true with probability 1/nmatch."
decowboy имеет хорошее доказательство того, что это работает на TopCoder
For clarity's sake, I would try:
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))
To me, that makes it MUCH clearer what you're trying to do and is self-documenting. On top of that, it's simpler and more elegant, and it's now obvious that each will be picked with an even distribution.