यह शफल एल्गोरिदम गलत क्यों है?

Question

इससे पहले कि मैं फिशर-येट्स के बारे में पढ़ा, इस एल्गोरिथ्म मैं के साथ आया है:

def sort(arr): 
    for i in range(len(arr)): 
     swap(arr, i, rand.randint(0, len(arr) - 1)) 

मेरी समझ से, यह और फिशर-येट्स के बीच फर्क सिर्फ इतना है कि बजाय:

swap(arr, i, rand.randint(0, len(arr) - 1)) 

मैं लिखना चाहिए:

swap(arr, i, rand.randint(i, len(arr) - 1)) 

कोई समझा सकते हैं कि कैसे पहले एल्गोरिथ्म सही नहीं है? (यानी एक यादृच्छिक शफल नहीं पैदा करता है)।

Answer 1

विकिपीडिया से:

इसी तरह, हर यात्रा पर मान्य सरणी सूचकांक की पूरी रेंज से हमेशा के चयन j भी एक परिणाम है जो स्पष्ट रूप से इतना पक्षपाती है, कम यद्यपि पैदा करता है। यह इस तथ्य से देखा जा सकता है कि ऐसा करने से n ⁿ स्वैप के विशिष्ट संभावित अनुक्रम उत्पन्न होते हैं, जबकि केवल n हैं! एक एन-तत्व सरणी के संभावित क्रमपरिवर्तन। चूंकि एन ^एन एन द्वारा समान रूप से विभाजित नहीं किया जा सकता है! जब n> 2 (के रूप में बाद के द्वारा n-1, जो n के साथ कोई अभाज्य गुणकों के शेयरों विभाज्य है), कुछ क्रमपरिवर्तन n के अधिक ⁿ दूसरों की तुलना में अदला-बदली के दृश्यों द्वारा उत्पादित किया जाना चाहिए। इस पूर्वाग्रह का एक ठोस उदाहरण के रूप में, तीन-तत्व सरणी [1, 2, 3] को घुमाने के संभावित परिणामों के वितरण का निरीक्षण करें। इस सरणी के 6 संभावित क्रमपरिवर्तन हैं (3! = 6), लेकिन एल्गोरिदम 27 संभावित शफल (33 = 27) उत्पन्न करता है। इस मामले में, [1, 2, 3], [3, 1, 2], और [3, 2, 1] 27 शफल में से 4 में से प्रत्येक परिणाम, जबकि शेष 3 क्रमिक क्रम 27 में से 5 में होते हैं शफ़ल।

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