क्या यह सी फिशर-येट्स का कार्यान्वयन सही है?

Question

यहाँ फिशर-येट्स के एक सी कार्यान्वयन है कि मैं एक डेक फेरबदल दिनचर्या में उपयोग करने के लिए चाहते हैं। क्या मैं इसे सही ढंग से कर रहा हूं (एन = सरणी की लंबाई)?

नोट: do-जबकि पाश सापेक्ष पूर्वाग्रह के लिए सही करने के लिए प्रयास करता है (here देखें)। यह प्रक्रिया के लिए थोड़ा अधिक ओवरहेड जोड़ता है और यदि आप निम्न-बिट पूर्वाग्रहों की परवाह नहीं करते हैं तो इसे समाप्त किया जा सकता है।

void shuffle(int *array, int n) { 

    int i, j, tmp, upper_bound; 

    srand(time(NULL)); 

    for (i = n - 1; i > 0; i--) { 

    upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1); 

    do { 
     j = rand() % (i + 1); 
    } while (j > upper_bound); 

    tmp = array[j]; 
    array[j] = array[i]; 
    array[i] = tmp; 
    } 
} 

Answer 1

सबसे पहले, आप एक यादृच्छिक संख्या कि समान रूप से एक अलग कार्य करने के लिए के बीच 0 (सम्मिलित) और n (अनन्य) वितरित पैदा करने के लिए कोड निकालने चाहिए। यह काम का एक अच्छा काम है जिसे आपको कहीं और चाहिए।

दूसरा, मैं को shuffle फ़ंक्शन के अंदर कॉल नहीं करता लेकिन यादृच्छिक संख्या जेनरेटर प्रारंभ करने पर कॉलर पर निर्भर करता हूं। इस तरह आप एक सेकंड में एक से अधिक बार एक डेक shuffle कर सकते हैं।

तीसरा, आपको i + 1 द्वारा विभाजित करने से पहले j > upper_bound के लिए परीक्षण करना चाहिए। यह संभावना नहीं है कि i कभी RAND_MAX के पास होगा।

static int rand_int(int n) { 
    int limit = RAND_MAX - RAND_MAX % n; 
    int rnd; 

    do { 
    rnd = rand(); 
    } while (rnd >= limit); 
    return rnd % n; 
} 

void shuffle(int *array, int n) { 
    int i, j, tmp; 

    for (i = n - 1; i > 0; i--) { 
    j = rand_int(i + 1); 
    tmp = array[j]; 
    array[j] = array[i]; 
    array[i] = tmp; 
    } 
} 

जांच करने के लिए इस कार्यान्वयन सही हो सकता है, आप सुनिश्चित करें कि आप अनियमितता की log2(n!) बिट्स के लिए यादृच्छिक संख्या जनरेटर पूछा की जरूरत है। दूसरे शब्दों में, सभी nrand_int समारोह को दी एस के उत्पाद n! होना चाहिए।