तत्वों के यादृच्छिक क्रम उत्पन्न करने के लिए एल्गोरिदम

Question

सबसे जटिलता वाले लगभग 20 तत्वों के क्रम को यादृच्छिक कैसे करें? (यादृच्छिक क्रमपरिवर्तन उत्पन्न करना)

Answer 1

Knuth's shuffle algorithm एक अच्छा विकल्प है।

Answer 2

कुछ महीने पहले मैंने पूर्णांक की सूची के यादृच्छिक क्रमपरिवर्तन प्राप्त करने के बारे में ब्लॉग किया था। आप इसे अपने तत्वों वाले सेट के इंडेक्स के क्रमपरिवर्तन के रूप में उपयोग कर सकते हैं, और फिर आपके पास जो भी चाहिए वो है।

• Generating random int list in F#

• Uniformly distributed random list permutation in F#

पहले पोस्ट में मैं कुछ संभावनाओं का पता लगाने, और अंत में मैं प्राप्त "एक समारोह बेतरतीब ढंग से साथ हे (एन) जटिलता एक सामान्य सूची permutate करने के लिए" , अपरिवर्तनीय डेटा पर काम करने के लिए ठीक से encapsulated (यानी, यह दुष्प्रभाव मुक्त है)।

दूसरी पोस्ट में, मैं इसे समान रूप से वितरित करता हूं।

कोड एफ # में है, मुझे उम्मीद है कि आपको कोई फर्क नहीं पड़ता!

शुभकामनाएं।

संपादित करें: मैं एक औपचारिक प्रमाण की जरूरत नहीं है, लेकिन अंतर्ज्ञान मुझसे कहता है कि इस तरह के एक एल्गोरिथ्म की जटिलता नहीं किया जा सकता की तुलना में कम हे (एन)। मैं वास्तव में यह तेजी से करने की सराहना करता हूं!

Answer 3

आदेश को यादृच्छिक करने का एक आसान तरीका सही आकार की एक नई सूची (आपके मामले में 20) बनाना है, पहली सूची में पुनरावृत्त करना है, और प्रत्येक तत्व को दूसरी सूची में यादृच्छिक स्थिति में जोड़ना है। यदि यादृच्छिक स्थिति पहले से भर चुकी है, तो इसे अगली खाली स्थिति में रखें।

मुझे लगता है कि इस स्यूडोकोड सही है:

list newList 
foreach (element in firstList) 
    int position = Random.Int(0, firstList.Length - 1) 
    while (newList[position] != null) 
     position = (position + 1) % firstList.Length 
    newList[position] = element 

संपादित करें: तो यह पता चला है कि इस सवाल का जवाब वास्तव में यह अच्छी बात नहीं है। यह न तो विशेष रूप से तेज़ है, न ही विशेष रूप से यादृच्छिक। आपकी टिप्पणीयों के लिए धन्यवाद। एक अच्छे उत्तर के लिए, कृपया पृष्ठ के शीर्ष पर वापस स्क्रॉल करें :-)

Answer 4

शायद किसी ने आपके लिए पहले से ही शफलिंग लागू की है। उदाहरण के लिए, पायथन में आप random.shuffle का उपयोग कर सकते हैं, सी ++ random_shuffle में, और PHP shuffle में।