अज्ञात लंबाई के अनुक्रम से यादृच्छिक रूप से एन आइटम उठाएं

Question

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

मैं एक समाधान पाया है जब एन = 1 (जो है, जब एक विशाल अनुक्रम से यादृच्छिक पर ठीक एक तत्व लेने की कोशिश कर रहा):

import random 
items = range(1, 10) # Imagine this is a huge sequence of unknown length 
count = 1 
selected = None 
for item in items: 
    if random.random() * count < 1: 
     selected = item 
    count += 1 

लेकिन मैं अन्य मूल्यों के लिए एक ही बात कैसे प्राप्त कर सकते हैं एन (कहते हैं, एन = 3)?

Answer 1

reservoir sampling का उपयोग करें। यह एक बहुत ही सरल एल्गोरिदम है जो किसी भी N के लिए काम करता है।

Here एक पायथन कार्यान्वयन है, और here एक और है।

Answer 2

जैसा कि मिश्रित जलाशयों नमूनाकरण कार्यों का उल्लेख किया गया है। एक और विकल्प आपके द्वारा देखे जाने वाले प्रत्येक नंबर के लिए एक यादृच्छिक संख्या उत्पन्न करता है और शीर्ष के संख्याओं का चयन करता है।

इसे करने के लिए, इसे के (हे यादृच्छिक संख्या, संख्या) जोड़े का ढेर बनाए रखें और जब भी आप ढेर में एक छोटे नंबर को सम्मिलित करते हैं तो यह ढेर में सबसे कम मूल्य से अधिक होता है।

Answer 3

यह केवल एक बार प्रत्येक नई वस्तु को स्वीकार या अस्वीकार करने के लिए पर्याप्त होना चाहिए, और, यदि आप इसे स्वीकार करते हैं, तो यादृच्छिक रूप से चुनी गई पुरानी वस्तु को फेंक दें।

मान लीजिए कि आपने यादृच्छिक रूप से के आइटमों को यादृच्छिक रूप से चुना है और आप एक (के + 1) वें आइटम देखते हैं। इसे संभाव्यता एन/(के + 1) के साथ स्वीकार करें और इसकी संभावनाएं ठीक हैं। वर्तमान वस्तुओं की संभावना एन/के साथ मिल गई है, और संभावना (एन/(के + 1)) (1/एन) = 1/(के + 1) के साथ फेंक दिया गया है इसलिए संभावना (एन/के) के माध्यम से जीवित रहें (के/(के + 1)) = एन/(के + 1) तो उनकी संभावनाएं भी ठीक हैं।

और हाँ मुझे लगता है कि किसी ने आपको जलाशय नमूनाकरण की ओर इशारा किया है - यह एक काम है कि यह कैसे काम करता है।

Answer 4

@ एनपीई सही है, लेकिन कार्यान्वित किए जा रहे कार्यान्वयन उप-इष्टतम हैं और बहुत "पायथनिक" नहीं हैं। यहाँ एक बेहतर कार्यान्वयन है: संपादित करें के रूप में @

def sample(iterator, k): 
    """ 
    Samples k elements from an iterable object. 

    :param iterator: an object that is iterable 
    :param k: the number of items to sample 
    """ 
    # fill the reservoir to start 
    result = [next(iterator) for _ in range(k)] 

    n = k - 1 
    for item in iterator: 
     n += 1 
     s = random.randint(0, n) 
     if s < k: 
      result[s] = item 

    return result 

पांडा -34 बाहर मूल संस्करण था त्रुटिपूर्ण बताया है, लेकिन नहीं, क्योंकि मैं बनाम randrangerandint उपयोग कर रहा था। मुद्दा यह है कि n के लिए मेरा प्रारंभिक मान इस तथ्य के लिए जिम्मेदार नहीं था कि randint सीमा के दोनों सिरों पर समावेशी है। इसे ध्यान में रखते हुए इस मुद्दे को हल करता है। (ध्यान दें: आप randrange का उपयोग भी कर सकते हैं क्योंकि इसमें न्यूनतम मूल्य और अधिकतम मूल्य पर विशेष शामिल है।)

Answer 5

यदि आपका अनुक्रम पर्याप्त है जो इसे स्मृति में पढ़ रहा है और यादृच्छिक रूप से सॉर्टिंग स्वीकार्य है, तो एक सीधा दृष्टिकोण होगा बस random.shuffle उपयोग करने के लिए हो सकता है:

import random 
arr=[1,2,3,4] 

# In-place shuffle 
random.shuffle(arr) 

# Take the first 2 elements of the now randomized array 
print arr[0:2] 
[1, 3] 

अपने अनुक्रम के प्रकार पर निर्भर करता है, आप किसी सूची में यह उस पर list(your_sequence) फोन करके कन्वर्ट करने के लिए आवश्यकता हो सकती है, लेकिन यह अपने अनुक्रम में वस्तुओं के प्रकार की परवाह किए बिना काम करेंगे ।

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

Answer 6

एक सरणी से आप एन यादृच्छिक आइटम दे देंगे के बाद एक्स

import random 
list(map(lambda _: random.choice(X), range(N))) 

Answer 7

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

from random import randint 

random_nums = [] 
N = # whatever number of random numbers you want 
r = # lower bound of number range 
R = # upper bound of number range 

x = 0 

while x < N: 
    random_num = randint(r, R) # inclusive range 
    if random_num in random_nums: 
     continue 
    else: 
     random_nums.append(random_num) 
     x += 1 

पाश के लिए खत्म हो गया है, जबकि पाश के लिए कारण यह है कि यह यादृच्छिक पीढ़ी में गैर लंघन के आसान कार्यान्वयन के लिए अनुमति देता है (यानी अगर आपने 3 डुप्लिकेट मिलता है, आप एन -3 नंबर प्राप्त नहीं होगा)।

Answer 8

मैं विकल्पों

from random import choices 

items = range(1, 10) 
new_items = choices(items, k = 3) 

print(new_items) 
[6, 3, 1]