मैं एनएल तत्वों को एक पर्ल सरणी से यादृच्छिक रूप से कैसे ले सकता हूं?

Question

मेरे पास P आकार के साथ एक सरणी है, A = [a1,a2,a3,...aP]। मुझे q सरणी ए

पर नमूना देना है I q पुनरावृत्तियों के साथ एक लूप का उपयोग करने की योजना है, और यादृच्छिक रूप से प्रत्येक पुनरावृत्ति पर ए से एक elment चुनें। लेकिन मैं यह कैसे सुनिश्चित कर सकता हूं कि प्रत्येक पुनरावृत्ति पर उठाई गई संख्या अलग होगी?

Answer 1

अन्य उत्तर सभी सरणी, जो O(n) है फेरबदल शामिल है। इसका मतलब मूल सरणी (विनाशकारी) को संशोधित करना या मूल सरणी (स्मृति गहन) की प्रतिलिपि बनाना है।

इसे और अधिक मेमोरी कुशल बनाने का पहला तरीका मूल सरणी को घुमाने के लिए नहीं बल्कि इंडेक्स की सरणी को घुमाने के लिए है।

# Shuffled list of indexes into @deck 
my @shuffled_indexes = shuffle(0..$#deck); 

# Get just N of them. 
my @pick_indexes = @shuffled_indexes[ 0 .. $num_picks - 1 ]; 

# Pick cards from @deck 
my @picks = @deck[ @pick_indexes ]; 

यह @deck की सामग्री के कम से कम स्वतंत्र है, लेकिन इसके अभी भी ओ (nlogn) प्रदर्शन और हे (एन) स्मृति।

एक अधिक कुशल एल्गोरिदम (आवश्यक रूप से तेज़ नहीं है, अब आपके सरणी पर बड़ा निर्भर करता है) सरणी के प्रत्येक तत्व को देखना है और यह तय करना है कि यह इसे सरणी में बनाने जा रहा है या नहीं। यह how you select a random line from a file without reading the whole file into memory के समान है, प्रत्येक पंक्ति में 1/एन मौका होने का मौका है जहां एन लाइन संख्या है। तो पहली पंक्ति में 1/1 मौका है (इसे हमेशा चुना जाता है)। अगले में 1/2 है। फिर 1/3 और इतने पर। प्रत्येक पिक पिछले पिक ओवरराइट करेगा। इसके परिणामस्वरूप प्रत्येक पंक्ति में 1/total_lines मौका होता है।

आप इसे अपने लिए बाहर कर सकते हैं। एक लाइन फ़ाइल में 1/1 मौका होता है ताकि पहले व्यक्ति को हमेशा चुना जा सके। एक दो पंक्ति फ़ाइल ... पहली पंक्ति में 1/1 है और जीवित रहने का 1/2 मौका है, जो 1/2 है, और दूसरी पंक्ति में 1/2 मौका है। एक तीन पंक्ति फ़ाइल के लिए ... पहली पंक्ति में 1/1 मौका लेने का मौका है, फिर 1/2 * 2/3 जीवित रहने का मौका 2/6 या 1/3 है। और इसी तरह।

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

थोड़ा संशोधन के साथ, यह कई चुनौतियों के लिए काम करता है। 1/$position मौका के बजाय, यह $picks_left/$position है। प्रत्येक बार जब कोई पिक सफल होता है, तो आप $ picks_left कमी करते हैं। आप उच्च पद से निम्न तक काम करते हैं। पहले के विपरीत, आप ओवरराइट नहीं करते हैं।

my $picks_left = $picks; 
my $num_left = @$deck; 
my @picks; 
my $idx = 0; 
while($picks_left > 0) { # when we have all our picks, stop 
    # random number from 0..$num_left-1 
    my $rand = int(rand($num_left)); 

    # pick successful 
    if($rand < $picks_left) { 
     push @result, $deck->[$idx]; 
     $picks_left--; 
    } 

    $num_left--; 
    $idx++; 
} 

यह how perl5i implements its pick method (अगली रिलीज आने वाला) है।

यह समझने के लिए कि यह क्यों काम करता है, 4 तत्व सूची से 2 चुनने का उदाहरण लें। प्रत्येक को उठाए जाने का 1/2 मौका होना चाहिए।

1. (2 picks, 4 items):   2/4 = 1/2 

काफी सरल। अगले तत्व में 1/2 मौका है कि एक तत्व पहले से ही चुना जाएगा, जिस स्थिति में इसकी संभावना 1/3 है। अन्यथा इसकी संभावना 2/3 है। गणित हो रहा है ...

2. (1 or 2 picks, 3 items): (1/3 * 1/2) + (2/3 * 1/2) = 3/6 = 1/2 

अगला एक 1/4 मौका दोनों तत्वों को पहले ही उठाया जाएगा कि (1/2 * 1/2) है, तो यह कोई मौका नहीं है; 1/2 मौका है कि केवल एक ही चुना जाएगा, फिर इसमें 1/2 होगा; और शेष 1/4 कि किसी भी आइटम को नहीं चुना जाएगा, जिस स्थिति में यह 2/2 है।

3. (0, 1 or 2 picks, 2 items): (0/2 * 1/4) + (1/2 * 2/4) + (2/2 * 1/4) = 2/8 + 1/4 = 1/2 

आखिरकार, आखिरी वस्तु के लिए, पिछले 1/2 में पिछली पिक ली गई थी।

4. (0 or 1 pick, 1 items):  (0/1 * 2/4) + (1/1 * 2/4) = 1/2 

बिल्कुल एक सबूत नहीं है, लेकिन स्वयं को समझाने के लिए अच्छा यह काम करता है।

Answer 2

आप आकार पी के साथ दूसरा सरणी, बूलियन बना सकते हैं और सही चुनिंदा संख्याओं के लिए स्टोर कर सकते हैं। और जब अंक चुना जाता है, तो दूसरी तालिका की जांच करें; यदि "सत्य" में आपको अगला चुनना होगा।

Answer 3

आप अपने सरणी को यादृच्छिक रूप से अनुमति देने के लिए Fisher-Yates shuffle algorithm पर शक कर सकते हैं और फिर पहले q तत्वों का एक टुकड़ा उपयोग कर सकते हैं। यहाँ PerlMonks से कोड है:

# randomly permutate @array in place 
sub fisher_yates_shuffle 
{ 
    my $array = shift; 
    my $i = @$array; 
    while (--$i) 
    { 
     my $j = int rand($i+1); 
     @$array[$i,$j] = @$array[$j,$i]; 
    } 
} 

fisher_yates_shuffle(\@array); # permutes @array in place 

आप शायद के बाद यह q यादृच्छिक चयनित तत्व है फेरबदल बंद होने से इस अनुकूलन कर सकते हैं। (वैसे यह लिखा है, आप पिछले क्ष तत्वों चाहेंगे।)

Answer 4

perldoc perlfaq4 से:

मैं कैसे एक सरणी बेतरतीब ढंग से शफ़ल करते हैं?

पर्ल 5.8.0 या बाद में स्थापित आप या तो किया है, या अगर आपके पास अदिश-सूची-Utils 1.03 या बाद में स्थापित है, तो आप कह सकते हैं:

use List::Util 'shuffle'; 
@shuffled = shuffle(@list); 

यदि नहीं, तो आप एक का उपयोग कर सकते फिशर-येट्स शफल।

sub fisher_yates_shuffle { 

    my $deck = shift; # $deck is a reference to an array 
    return unless @$deck; # must not be empty! 

    my $i = @$deck; 
    while (--$i) { 
     my $j = int rand ($i+1); 
     @$deck[$i,$j] = @$deck[$j,$i]; 
    } 
} 


# shuffle my mpeg collection 
# 

my @mpeg = <audio/*/*.mp3>; 
fisher_yates_shuffle(\@mpeg); # randomize @mpeg in place 
print @mpeg; 

---

तुम भी List::Gen इस्तेमाल कर सकते हैं:

my $gen = <1..10>; 
print "$_\n" for $gen->pick(5); # prints five random numbers