किसी सरणी का यादृच्छिक क्रमपरिवर्तन कैसे बनाएं?

Question

मैंने इस समारोह को सी में लिखा है और मैं इसे यादृच्छिक क्रमपरिवर्तन या संख्याओं की सूची 1 से एन तक बनाना चाहता हूं। मुझे दोहराने वाली संख्याएं प्राप्त करने में परेशानी हो रही है। तो अगर आप एन = 4 है, मुझे यह पसंद है एक यादृच्छिक सरणी केवल एक बार 1-4 से युक्त वापस जाने के लिए, उदाहरण के लिए होगा: {1,3,4,2}

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    // initial range of numbers 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    // shuffle 
    for (int i = 1; i <= n; ++i){ 
     int j = rand() % i; 
     r[i] = r[j]; 
     r[j] = i; 
    } 
    return r; 
} 

Answer 1

अपने दूसरे for पाश बदलें :

for (int i = n-1; i >= 0; --i){ 
    //generate a random number [0, n-1] 
    int j = rand() % (i+1); 

    //swap the last element with element at random index 
    int temp = r[i]; 
    r[i] = r[j]; 
    r[j] = temp; 
} 

यह एक फिशर-येट्स शफलिंग एल्गोरिदम है। मैंने rand() % n का उपयोग करके सुना है समान रूप से वितरित नहीं करता है, आपको चेतावनी दी गई है।

और यदि आप हर बार अद्वितीय क्रमपरिवर्तन उत्पन्न करना चाहते हैं, तो आप उत्पन्न किए गए क्रमपरिवर्तनों को संग्रहीत कर सकते हैं, शायद Dictionary या Hashmap में, और फिर जब भी आप वापस आएं तो लुकअप करें। मुझे नहीं लगता कि C एक में बनाया गया है लेकिन पुस्तकालय उपलब्ध होना चाहिए।

Answer 2

यह सबसे प्रभावी तरीका नहीं हो सकता है, लेकिन चूंकि आप शुरुआत में सरणी को पहले ही पॉप्युलेट कर रहे हैं, तो आप तत्वों के माध्यम से केवल लूप कर सकते हैं और प्रत्येक के लिए, 1 से n की श्रेणी में एक यादृच्छिक अनुक्रमणिका चुनें , और उस आइटम के साथ स्वैप करें:

int* random(int n) 
{ 
    int* r = malloc(n * sizeof(int)); 
    for(int i=0;i<n;++i){ 
     r[i]=i+1; 
    } 
    for(int i=0; i<n; ++i){ 
     int randIdx = rand() % n; 
     // swap r[i] with r[randIdx] 
     int t = r[i]; 
     r[i] = r[randIdx]; 
     r[randIdx] = t; 
    } 
    return r; 
} 

मुझे नहीं पता कि यह सबसे कुशल है या भले ही यह सर्वोत्तम वितरण प्रदान करता हो। लेकिन यह बहुत आसान है :-)