اختر عنصر مجموعة عشوائي مرضية بعض العقارات

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

يعمل رياضيا. يمكن إثباتها عن طريق الحث.

يعمل بوضوح ل n = 1 عنصر مرضية ص.

عناصر N + 1، سوف نختار العنصر N + 1 مع احتمال 1 / (N + 1)، لذلك احتماله على ما يرام. ولكن كيف يؤثر ذلك على احتمال انتهاء اختيار أحد العناصر السابقة؟

كان لكل من سابقة ن فرصة المحتملة مع احتمال 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.

Answer 2

نعم أعتقد ذلك.

في المرة الأولى التي تواجه فيها عنصرا مطابقا، يمكنك بالتأكيد اختيارها. في المرة القادمة، يمكنك اختيار القيمة الجديدة مع احتمال 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;
}

Answer 3

في ممارسة البرمجة, ، pg. 70، (خوارزمية سلسلة ماركوف) هناك خوارزمية مماثلة لذلك:

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

"لاحظ خوارزمية تحديد عنصر واحد بشكل عشوائي عندما لا نعرف عدد العناصر الموجودة هناك. تحسب المتغير NMatch عدد التطابقات حيث يتم فحص القائمة. التعبير

rand() % ++nmatch == 0

الزيادات NMatch ومن ثم صحيح مع احتمال 1 / NMatch. "

Answer 4

Decowboy لديه دليل لطيف على أن هذا يعمل على topcoder.

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

بالنسبة لي، هذا يجعلها أكثر وضوحا ما تحاول القيام به وهو المستندات الذاتية. علاوة على ذلك، فإنه أبسط وأكثر أناقة، ومن الواضح الآن أن يتم اختيار كل منها بتوزيع حتى.