क्रमबद्ध सूची को यादृच्छिक कैसे करें?

Question

यहां आपके लिए एक अजीब सवाल है,

मेरे पास एक अच्छी तरह से क्रमबद्ध सूची है जिसे मैं यादृच्छिक बनाना चाहता हूं। मुझसे यह कैसे होगा?

मेरे आवेदन में, मेरे पास एक ऐसा फ़ंक्शन है जो एक विघटित वस्तु की रूपरेखा का वर्णन करने वाले बिंदुओं की एक सूची देता है। जिस तरह से समस्या हल हो जाती है, वैसे ही फ़ंक्शन एक अच्छी ऑर्डर सूची देता है। मेरे पास गणित में वर्णित दूसरी सीमा है और यह निर्धारित करना है कि दोनों वस्तुएं एक-दूसरे को अलग करती हैं या नहीं। मैं बस बिंदुओं पर फिर से शुरू करता हूं और यह निर्धारित करता हूं कि कोई भी बिंदु गणितीय सीमा के अंदर है या नहीं।

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

तो, किसी भी विचार पर मैं आदेशित सूची को यादृच्छिक करने के बारे में कैसे जाऊं?

Answer 1

std::random_shuffle का उपयोग करें। यदि आप स्वयं विधि को कार्यान्वित करना चाहते हैं तो आपको Fisher-Yates shuffle पर देखना चाहिए।

Answer 2

आप random_shuffle algorithm को आजमा सकते हैं, लेकिन ध्यान दें कि यह list पर काम नहीं करेगा क्योंकि इसे यादृच्छिक एक्सेस इटरेटर्स की आवश्यकता है। आप इसे vector या deque पर उपयोग कर सकते हैं।

Answer 3

std::random_shuffle(thelist.begin(), thelist.end()); 

Answer 4

अपने "सूची" यह मानते हुए एक लिंक्ड सूची मतलब यह नहीं है, लेकिन इसके बजाय कुछ है कि रैंडम एक्सेस का समर्थन करता है (उदाहरण के लिए, एक सरणी, std :: वेक्टर, या std :: Deque), std :: random_shuffle का मतलब उपयोगी हो सकता है।

Answer 5

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

शायद आपको वास्तव में जो करना है वह वास्तव में यादृच्छिक नहीं है, बल्कि इसे आगे के पीछे के अलावा कुछ क्रम में पढ़ें। उदाहरण के लिए, यदि सूची में एन सदस्य हैं, तो शायद आपको 1, एन, 2, एन -1, 3, एन -2, आदि या 1, एन/2, 2, एन/2 + 1, 3, एन को संसाधित करना चाहिए/2 +2, आदि

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

Answer 6

 
int array[N]; 

for(int i = N - 1; i > 0; i--) { 
    int j = rand() % i; 
    int tmp = array[i]; array[i] = array[j]; array[j] = i; 
}