एक वर्दी यादृच्छिक क्रमपरिवर्तन

Question

उत्पन्न मुझे यकीन है कि निम्नलिखित छद्म कोड उत्पन्न कर सकते हैं कि क्या नहीं कर रहा हूँ एक uniformly random permutation:

PERMUTATE(A): 
    n = A.length 
    for i = 1 to n 
     swap A[i] and A[random(1,n)] 

यह सही प्रतीत हो रहा है, लेकिन किसी को मुझे इसकी सत्यता या wrongness सत्यापित करने के लिए एक कठोर सबूत दे सकते हैं ?

Answer 1

यह समाधान पक्षपातपूर्ण है, आप गैर पक्षपातपूर्ण क्रमपरिवर्तन के लिए Fisher Yates algorithm [जो समान है] चाहते हैं। [मूल रूप से, आपको random(1,n)]

This thread चर्चा करता है कि आपका समाधान पक्षपातपूर्ण और क्यों पक्षपातपूर्ण है, इसके बजाय आपको random(i,n) के साथ स्वैप करने की आवश्यकता है।