कुछ संपत्ति को संतुष्ट यादृच्छिक सरणी तत्व चुनें

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) रिटर्न 0 <= k < n साथ एक यादृच्छिक पूर्णांक k।)

Answer 1

यह गणितीय रूप से कार्य करता है। प्रेरण से साबित किया जा सकता है।

स्पष्ट रूप से n = 1 तत्व संतोषजनक पी के लिए काम करता है।

एन + 1 तत्वों के लिए, हम संभाव्यता 1/(एन + 1) के साथ तत्व एन + 1 का चयन करेंगे, इसलिए इसकी संभावना ठीक है।लेकिन यह पूर्व एन तत्वों में से किसी एक को चुनने की अंत संभावना को कैसे प्रभावित करता है?

प्रत्येक पूर्व एन को संभाव्यता 1/n के साथ चयन करने का मौका मिला, जब तक हमें तत्व n + 1 नहीं मिला। अब, एन + 1 खोजने के बाद, एक 1/(एन + 1) मौका है कि तत्व एन + 1 चुना गया है, इसलिए एक एन/(एन + 1) मौका है कि पहले चुने गए तत्व को चुना गया है। जिसका मतलब है कि एन + 1 पाये जाने के बाद चुने जाने की इसकी अंतिम संभावना 1/एन * (एन/एन + 1) = 1/एन + 1 है - जो संभावना है कि हम समान वितरण के लिए सभी एन + 1 तत्वों के लिए चाहते हैं।

यदि यह n = 1 के लिए काम करता है, और यह n + 1 दिए गए n के लिए काम करता है, तो यह सभी n के लिए काम करता है।

Answer 2

हाँ, मैं इतना विश्वास है ?: करना होगा।

पहली बार जब आप मिलान तत्व का सामना करते हैं, तो आप निश्चित रूप से इसे चुनते हैं। अगली बार, आप 1/2 की संभावना के साथ नया मान चुनते हैं, इसलिए दो तत्वों में से प्रत्येक का बराबर मौका होता है। अगली बार, आप 1/3 की संभावना के साथ नया मान चुनते हैं, जिसमें प्रत्येक तत्व को 1/2 * 2/3 = 1/3 की संभावना के साथ छोड़ दिया जाता है।

मैं अब तक नाकाम रहने के इस रणनीति के बारे में एक विकिपीडिया लेख खोजने की कोशिश कर रहा हूँ, लेकिन ...

ध्यान दें कि अधिक आम तौर पर, आप सिर्फ एक नमूने के तौर पर अज्ञात लंबाई के एक अनुक्रम से बाहर उठा रहे हैं। आपका अनुक्रम प्रारंभिक अनुक्रम लेने और फ़िल्टर करने के द्वारा उत्पन्न होता है, लेकिन एल्गोरिदम को उस भाग की आवश्यकता नहीं होती है।

मैंने सोचा कि मैं MoreLINQ में एक LINQ ऑपरेटर यह करने के लिए मिल गया था, लेकिन मैं इसे में भंडार ... संपादित नहीं मिल सकता है: सौभाग्य से, यह अभी भी this answer से मौजूद है:

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

के लिए स्पष्टता की खातिर, मैं कोशिश करेंगे:

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

मेरे लिए

, कि यह अधिक स्पष्ट तुम क्या करने की कोशिश कर रहा है और स्वयं कुछ दस्तावेज़ीकृत है कर रहे हैं बनाता है। इसके शीर्ष पर, यह सरल और अधिक सुरुचिपूर्ण है, और अब यह स्पष्ट है कि प्रत्येक को भी वितरण के साथ चुना जाएगा।

Answer 4

प्रोग्रामिंग, पीजी का अभ्यास। 70, (मार्कोव श्रृंखला एल्गोरिथ्म) वहाँ उस के लिए एक समान एल्गोरिथ्म है:।

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

"सूचना आकस्मिक एक आइटम का चयन के लिए एल्गोरिथ्म है जब हम देखते हैं कि कैसे कई मदों पता नहीं है चर Nmatch सूची के रूप में मैचों की संख्या में गिना जाता है स्कैन किया जाता है। अभिव्यक्ति

rand() % ++nmatch == 0 

वेतन वृद्धि Nmatch और संभावना 1/Nmatch साथ बाद में सही मायने है। "

Answer 5

decowboy एक अच्छा सबूत है कि इस TopCoder