पायथन random.shuffle के साथ शफल करने के लिए सूची की अधिकतम लंबाई?

Question

मैं एक सूची है जो मुझे फेरबदल समारोह में बनाया (random.shuffle)

हालांकि, पायथन संदर्भ राज्यों अजगर के साथ शफ़ल है:

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

अब, मुझे आश्चर्य है कि यह "बल्कि छोटा लेन (एक्स)" का अर्थ है। 100, 1000, 10000, ...

Answer 1

टी एल; डॉ: यह 2080 से अधिक तत्वों के साथ सूची में "ब्रेक" है, लेकिन बहुत ज्यादा चिंता नहीं है :)

पूरा जवाब:

सबसे पहले, आप देखते हैं कि "फेरबदल" एक सूची सूचियों के तत्वों के सभी संभावित क्रमपरिवर्तन उत्पन्न करने और यादृच्छिक रूप से इन क्रमिक क्रमों में से एक को चुनने के रूप में समझा जा सकता है।

फिर, आपको याद रखना चाहिए कि सभी स्वयं निहित कम्प्यूटरीकृत यादृच्छिक संख्या जेनरेटर वास्तव में "छद्म" यादृच्छिक हैं। यही है, वे वास्तव में यादृच्छिक नहीं हैं, लेकिन उन कारकों की एक श्रृंखला पर भरोसा करते हैं जो किसी ऐसे नंबर को चलाने और उत्पन्न करने के लिए उन्नत होते हैं, जिसे उन्नत, या उद्देश्य से पुन: उत्पादित किया जाना कठिन होता है। इन कारकों में से आमतौर पर पिछली जेनरेट की गई संख्या होती है। तो, व्यावहारिक रूप से, यदि आप निरंतर एक निश्चित संख्या में यादृच्छिक जनरेटर का उपयोग करते हैं, तो आप अंततः एक ही अनुक्रम को फिर से शुरू करना शुरू कर देंगे (यह वह "अवधि" है जो दस्तावेज़ीकरण को संदर्भित करता है)।

अंत में, लिब/random.py (यादृच्छिक मॉड्यूल) पर डॉकस्ट्रिंग का कहना है कि "यादृच्छिक संख्या जेनरेटर की अवधि] 2**19937-1 है।"

तो, यह सब कुछ दिया गया है, यदि आपकी सूची ऐसी है कि 2**19937 या अधिक क्रमिक क्रम हैं, तो इनमें से कुछ सूची को शफ़ल करके कभी प्राप्त नहीं किया जाएगा। आप सूची के सभी क्रमपरिवर्तन उत्पन्न करेंगे (फिर, अवधारणात्मक रूप से), फिर एक यादृच्छिक संख्या x उत्पन्न करें, और xth क्रमपरिवर्तन चुनें। अगली बार, आप एक और यादृच्छिक संख्या वाई उत्पन्न करते हैं, और yth क्रमपरिवर्तन चुनें। और इसी तरह। लेकिन, चूंकि आपको अधिक क्रमिकताएं मिलती हैं, इसलिए आपको यादृच्छिक संख्याएं मिलेंगी (क्योंकि, 2**19937-1 जेनरेट किए गए नंबरों के बाद, आप एक ही बार फिर से शुरू करना शुरू कर देंगे), आप फिर से वही क्रमपरिवर्तन चुनना शुरू कर देंगे।

तो, आप देखते हैं, यह बिल्कुल सही नहीं है कि आपकी सूची कितनी देर तक है (हालांकि यह समीकरण में प्रवेश करती है)। इसके अलावा, 2**19937-1 काफी लंबी संख्या है। लेकिन, फिर भी, आपकी शफल आवश्यकताओं के आधार पर, आपको यह सब कुछ ध्यान में रखना चाहिए। एक सरल मामले (और त्वरित गणना के साथ), दोहराए गए तत्वों के बिना सूची के लिए, 2081 तत्व 2081! क्रमपरिवर्तन उत्पन्न करेंगे, जो 2**19937 से अधिक है।

Answer 2

उनका क्या मतलब है कि एन ऑब्जेक्ट्स (नोटेड एन!) पर क्रमपरिवर्तन बेहद तेज़ हो जाता है।

मूल रूप से एन! = एन एक्स एन -1 एक्स ... एक्स 1; उदाहरण के लिए, 5! = 5 x 4 x 3 x 2 x 1 = 120 जिसका अर्थ है कि 5-आइटम सूची को घुमाने के 120 संभावित तरीके हैं।

उसी पायथन पेज प्रलेखन पर वे अवधि के रूप में 2^19937-1 देते हैं, जो 4. कुछ × 10^6001 या कुछ है। फैक्ट्रोरियल पर विकिपीडिया पेज के आधार पर, मुझे लगता है 2000! उसके आसपास होना चाहिए। (क्षमा करें, मुझे सटीक आंकड़ा नहीं मिला।)

तो मूल रूप से इतने सारे संभावित क्रमपरिवर्तन हैं कि शफल ले जाएगा कि संभवतः उन लोगों के बारे में चिंता करने का कोई वास्तविक कारण नहीं है।

लेकिन अगर यह वास्तव में एक मुद्दा है (अजीब ग्राहक शायद यादृच्छिकता की गारंटी मांग रहे हो?), तो आप कार्य को किसी तीसरे पक्ष को भी ऑफ़लोड कर सकते हैं; उदाहरण के लिए http://www.random.org/ देखें।

Answer 3

मैं अजगर स्रोत में है कि टिप्पणी लिखी मूल रूप से है, तो शायद मैं ;-)

स्पष्ट कर सकते हैं जब टिप्पणी पेश किया गया था, पायथन के Wichmann-हिल जनरेटर एक बहुत छोटी अवधि के लिए किया था, और हम भी उत्पन्न नहीं कर सका कार्ड के एक डेक के सभी क्रमपरिवर्तन।

अवधि अब खगोलीय रूप से बड़ी है, और 2080 वर्तमान ऊपरी सीमा के लिए सही है। डॉक्स को इसके बारे में अधिक कहने के लिए बढ़ाया जा सकता है - लेकिन वे बहुत ही थकाऊ हो जाएंगे।

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

>>> math.factorial(2080) > 2**19937 - 1 
False 
>>> math.factorial(2081) > 2**19937 - 1 
True