बूलियन की एक सरणी को देखते हुए, यादृच्छिक TRUE मान की अनुक्रमणिका का चयन करने का सबसे प्रभावी तरीका क्या है?

Question

आपको आकार एन की एक सरणी दी गई है, जिसमें मनमानी बूलियन मान शामिल हैं।

यादृच्छिक TRUE मान की अनुक्रमणिका को वापस करने का सबसे तेज़ तरीका क्या है।

एल्गोरिदम को यादृच्छिक रूप से किसी भी सूचकांक को TRUE युक्त वापस करना चाहिए।

Answer 1

कुछ इस तरह:

1: (1/1) * (1/2) * (2/3) * (3/4) = 1/4 
2: (1/2) * (2/3) * (3/4) = 1/4 
3: (1/3) * (3/4) = 1/4 
4: 1/4 = 1/4 

संपादित करें: स्टीव जेसप ने बताया चल बिन्दु तुलना

int count = 0; 
int index = -1; 
for (int i = 0; i != n; ++i) 
{ 
    if (values[i]) 
    { 
     ++count; 
     if (unit_random <= 1.0f/count) 
     { 
      index = i; 
     } 
    } 
} 

उदाहरण के लिए 4 मूल्यों के लिए

तो तुम अपने इंडेक्स के लिए निम्नलिखित संभावनाओं मिल अंत में एक बहुत ही समान वर्दी चयन का नेतृत्व करेंगे। rand के असतत प्रकृति के कारण

typedef unsigned long long u64; 
u64 product = u64(count) * rand(); 
if (product <= u64(RAND_MAX)) 

यह एकदम सही वितरण नहीं दे देंगे, लेकिन यह बेहतर होगा: मान लिया जाये कि unit_randomrand()/RAND_MAX तुलना के रूप में परिभाषित किया गया है करने के लिए बदला जा सकता है।

Answer 2

यह स्पष्ट नहीं है कि "यादृच्छिक रूप से विचलित" का अर्थ क्या है। क्या इसका मतलब है "कुछ अज्ञात वितरण के साथ"? यदि हां, तो सभी संभावित वितरणों का नाटक करना उतना ही संभव है, इसलिए "अपेक्षित वितरण" (जैसे "अपेक्षित मूल्य") समान है (सभी संभावित वितरणों का "औसत")। फिर कोई भी सूचकांक 1/2। तो आपका काम सरणी के माध्यम से जितनी जल्दी हो सके पुनरावृत्ति का कार्य बन जाता है। शुरुआत में शुरू करें, जैसे कि आप सामान्य रूप से एक सरणी को फिर से चालू करेंगे, जब तक कि आपको कोई वास्तविक मूल्य न हो।

Answer 3

इसे वापस करने के लिए, आपको सबसे पहले सही मानों की गणना करनी होगी (इसे छोड़ने का कोई तरीका नहीं है) और अपने सूचकांक को अन्य सरणी में जमा करें। और गिनने के बाद आपको 0 से एन -1 तक यादृच्छिक पूर्णांक उत्पन्न करना होगा (जहां एन सही मानों की संख्या है) और बनाए गए सरणी से मान चुनें।

छद्म अजगर में

:

indices=[] 

for i,val in enumerate(arr): 
    if val: 
     indices.append(i) 
randi = randint(0,len(indices)-1) 
return indices[randi] 

Answer 4

तेज समाधान - यह सोचते हैं कि आप एक ही सरणी पर बार-बार का चयन नहीं करते - एक यादृच्छिक सूचकांक लेने, इसे वापस अगर यह सच है, और यदि नहीं दोहराने के लिए है। सबसे अच्छे मामले में, जहां सभी प्रविष्टियां सत्य हैं, यह ओ (1) है; सबसे बुरे मामले में, जहां केवल एक प्रविष्टि सत्य है, यह ओ (एन) है (प्रत्येक प्रयास में एकमात्र सच्चे मूल्य को मारने का 1/एन मौका होता है, जिसका मतलब एन की कोशिश की अपेक्षित संख्या है)। यह किसी भी अन्य पोस्ट समाधान से भी बदतर नहीं है।

यदि आप सरणी को आमतौर पर लगभग सभी झूठी होने की उम्मीद करते हैं, हालांकि, आप एक और समाधान चुनना चाहेंगे, क्योंकि इस यादृच्छिक विधि के रनटाइम में भिन्नता उच्च होगी।

Answer 5

सरल समाधान: (? 1: एन) संभव अनुक्रमित का क्रमपरिवर्तन उत्पन्न और है कि क्रमचय वापसी सूचकांक के क्रम में अगर संबंधित मान सच

def randomTrue(x): 
    perm = randomPermute(0:len(x)) 
    for i in perm: 
     if x[i]: 
      return i