आलसी शफल एल्गोरिदम

Question

मेरे पास उन तत्वों की एक बड़ी सूची है जिन्हें मैं यादृच्छिक क्रम में पुन: सक्रिय करना चाहता हूं। हालांकि, मैं सूची को संशोधित नहीं कर सकता और मैं इसकी प्रतिलिपि बनाना भी नहीं चाहता, क्योंकि 1) यह बड़ा है और 2) यह उम्मीद की जा सकती है कि पुनरावृत्ति को रद्द कर दिया जाए।

List<T> data = ...; 
Iterator<T> shuffled = shuffle(data); 
while (shuffled.hasNext()) { 
    T t = shuffled.next(); 
    if (System.console().readLine("Do you want %s?", t).startsWith("y")) { 
     return t; 
    } 
} 
System.out.println("That's all"); 
return t; 

मैं एक एल्गोरिथ्म रहा हूँ थे कोड ऊपर O(n) में काम कर (और अच्छा होगा यदि केवल O(log n) स्थान की आवश्यकता), इसलिए तत्वों है कि पहले तैयार किए गए एक विकल्प नहीं है भंडारित करता है। मुझे परवाह नहीं है कि एल्गोरिदम पक्षपातपूर्ण है (जब तक यह स्पष्ट नहीं है)।

(मैं अपने सवाल में छद्म जावा का उपयोग करता है, लेकिन आप यदि आप चाहें तो अन्य भाषाओं का उपयोग कर सकते हैं)

यहाँ सबसे अच्छा मैं अब तक मिल गया है।

Iterator<T> shuffle(final List<T> data) { 
    int p = data.size(); 
    while ((data.size() % p) == 0) p = randomPrime(); 
    return new Iterator<T>() { 
     final int prime = p; 
     int n = 0, i = 0; 
     public boolean hasNext() { return i < data.size(); } 
     public T next() { 
      i++; n += prime; 
      return data.get(n); 
     } 
    } 
} 

पुनरावृत्ति O(n) के सभी तत्वों, निरंतर अंतरिक्ष, लेकिन स्पष्ट रूप से पक्षपाती के रूप में यह केवल data.size() क्रमपरिवर्तन उत्पादन कर सकते हैं।

Answer 1

सबसे आसान शफल दृष्टिकोण मुझे सूचकांक के साथ काम के बारे में पता है। यदि ListArrayList नहीं है, तो आप नीचे से किसी एक का उपयोग करने का प्रयास करते हैं, तो आप एक बहुत ही अक्षम एल्गोरिदम के साथ समाप्त हो सकते हैं (LinkedList में आईडी द्वारा get है, लेकिन यह ओ (एन) है, तो आप समाप्त हो जाएंगे ओ (एन^2) समय)।

यदि ओ (एन) स्थान ठीक है, जो मुझे लगता है कि यह नहीं है, तो मैं Fisher-Yates/Knuth shuffle की अनुशंसा करता हूं, यह ओ (एन) समय है और इसे कार्यान्वित करना आसान है। आप इसे अनुकूलित कर सकते हैं ताकि आपको पहले तत्व प्राप्त करने में सक्षम होने से पहले केवल एक ही ऑपरेशन करने की आवश्यकता हो, लेकिन आपको जितनी बार संशोधित सूची में संशोधित सूची का ट्रैक रखना होगा।

मेरे समाधान:

ठीक है, तो यह सब पर बहुत यादृच्छिक नहीं है, लेकिन अगर आप हे (एन) अंतरिक्ष से भी कम समय चाहते हैं मैं एक बेहतर तरीका नहीं देख सकता।

यह ओ (1) स्पेस और ओ (एन) समय लेता है।

अंतरिक्ष उपयोग को थोड़ा सा धक्का देने और अधिक यादृच्छिक परिणाम प्राप्त करने का एक तरीका हो सकता है, लेकिन मुझे अभी तक यह पता नहीं लगा है।

इसे relative primes के साथ करना है। विचार यह है कि, 2 रिश्तेदार अभाज्य संख्या a (जनरेटर) और b दिया, जब लूप के माध्यम से आप है a % b, 2a % b, 3a % b, 4a % b, ..., आप हर पूर्णांक देखेंगे 0, 1, 2, ..., बी -2, बी -1, और यह दो बार पूर्णांक देखने से पहले भी होगा। दुर्भाग्य से मेरे पास एक सबूत का लिंक नहीं है (विकिपीडिया लिंक इसका उल्लेख कर सकता है या इसका मतलब है, मैंने बहुत अधिक विस्तार से जांच नहीं की है)।

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

मैं सभी मूल्यों के माध्यम से पुनरावृत्ति कर रहा हूं और प्रिंट कर रहा हूं, लेकिन वर्तमान में दिए गए किसी को उत्पन्न करने के लिए इसे संशोधित करना आसान होना चाहिए।

नोट मैं 1 और len-1 लंघन कर रहा हूँ मेरी nextInt साथ, क्योंकि ये 1,2,3,... और ...,3,2,1 क्रमशः उत्पादन होगा, लेकिन आप इन में शामिल कर सकते हैं, लेकिन शायद नहीं करता है, तो लंबाई एक निश्चित सीमा से नीचे है।

आप जनरेटर को (लंबाई लंबाई) से गुणा करने के लिए यादृच्छिक संख्या भी उत्पन्न करना चाहते हैं।

जावा कोड:

static Random gen = new Random(); 

static void printShuffle(int len) 
{ 
    // get first prime >= len 
    int newLen = len-1; 
    boolean prime; 
    do 
    { 
    newLen++; 
    // prime check 
    prime = true; 
    for (int i = 2; prime && i < len; i++) 
     prime &= (newLen % i != 0); 
    } 
    while (!prime); 

    long val = gen.nextInt(len-3) + 2; 
    long oldVal = val; 
    do 
    { 
    if (val < len) 
     System.out.println(val); 
    val = (val + oldVal) % newLen; 
    } 
    while (oldVal != val); 
} 

Answer 2

आप ऐसा करने के लिए एक बफर का उपयोग करने का प्रयास कर सकते हैं। डेटा के सीमित सेट के माध्यम से Iterate और इसे एक बफर में डाल दिया। उस बफर से यादृच्छिक मान निकालें और इसे आउटपुट पर भेजें (या जहां भी आपको इसकी आवश्यकता हो)। अगले सेट के माध्यम से Iterate और इस बफर ओवरराइटिंग रखें। इस चरण को दोहराएं।

आप एन + एन ऑपरेशंस के साथ समाप्त हो जाएंगे, जो अभी भी ओ (एन) है। दुर्भाग्यवश, परिणाम वास्तव में यादृच्छिक नहीं होगा। यदि आप अपना बफर आकार सही तरीके से चुनते हैं तो यह यादृच्छिक के करीब होगा। Python - run through a loop in non linear fashion, random iteration in Python

शायद वहाँ इस बेहतर करने के लिए एक और अधिक सुरुचिपूर्ण एल्गोरिथ्म है:

एक अलग टिप्पणी पर, इन दोनों की जाँच करें। मुझे यकीन नहीं है हालांकि। इस धागे में अन्य उत्तरों के लिए तत्पर हैं।

Answer 3

यह अपने प्रश्न का एक आदर्श जवाब नहीं है, लेकिन शायद यह उपयोगी है। i 'वें फेरबदल आइटम प्राप्त करने के लिए, साथ a[i] स्वैप और एक अनियमित रूप से चुने a[j] जहां j[i..n-1] में है, तो वापसी:

विचार एक प्रतिवर्ती यादृच्छिक संख्या जनरेटर और हमेशा की तरह सरणी-आधारित पुथल lazily किया एल्गोरिथ्म का उपयोग करना है a[i]। यह इटरेटर में किया जा सकता है।

आपके द्वारा पुनरावृत्त किए जाने के बाद, आरएनजी की विपरीत दिशा का उपयोग करके सरणी को मूल क्रम में रीसेट करें।

असफल रीसेट मूल पुनरावृत्ति से अधिक समय नहीं लेगा, इसलिए यह एसिम्प्टोटिक लागत को नहीं बदलता है। इटरेशन अभी भी पुनरावृत्तियों की संख्या में रैखिक है।

एक उलटा आरएनजी कैसे बनाया जाए? बस एक एन्क्रिप्शन एल्गोरिदम का उपयोग करें। आगे बढ़ने के लिए पहले जेनरेट किए गए छद्म-यादृच्छिक मान को एन्क्रिप्ट करें, और पीछे जाने के लिए डिक्रिप्ट करें। यदि आपके पास एक सममित एन्क्रिप्शन एल्गोरिदम है, तो आप दो चरणों के चक्र को रोकने के लिए प्रत्येक चरण पर "नमक" मान जोड़ सकते हैं और प्रत्येक चरण के लिए इसे घटा सकते हैं। मैं इसका जिक्र करता हूं क्योंकि आरसी 4 सरल और तेज़ और सममित है। मैंने इसे इस तरह के कार्यों के लिए पहले इस्तेमाल किया है। 4-बाइट मानों को एन्क्रिप्ट करना, फिर वांछित सीमा में उन्हें प्राप्त करने के लिए मॉड कंप्यूटिंग करना वास्तव में जल्दी होगा।

रीसेट की अनुमति देने के लिए आप Iterator को बढ़ाकर जावा इटरेटर पैटर्न में इसे दबा सकते हैं। निचे देखो। उपयोग इस तरह दिखेगा:

ShuffledList<Integer> lst = new SuffledList<>(); 

... build the list with the usual operations 

ResetableInterator<Integer> i = lst.iterator(); 
while (i.hasNext()) { 
    int val = i.next(); 

    ... use the randomly selected value 

    if (anyConditinoAtAll) break; 
} 
i.reset(); // Unshuffle the array 

मुझे पता है कि यह सही नहीं है, लेकिन यह तेज़ होगा और एक अच्छा शफल देगा। ध्यान दें कि यदि आप reset नहीं हैं, तो अगला पुनरावर्तक अभी भी एक नया यादृच्छिक शफल होगा, लेकिन मूल ऑर्डर हमेशा के लिए खो जाएगा। यदि लूप बॉडी अपवाद उत्पन्न कर सकती है, तो आप finally ब्लॉक में रीसेट करना चाहते हैं। : http: // stackoverflow

class ShuffledList<T> extends ArrayList<T> implements Iterable<T> { 

    @Override 
    public Iterator<T> iterator() { 
     return null; 
    } 

    public interface ResetableInterator<T> extends Iterator<T> { 
     public void reset(); 
    } 

    class ShufflingIterator<T> implements ResetableInterator<T> { 

     int mark = 0; 

     @Override 
     public boolean hasNext() { 
      return true; 
     } 

     @Override 
     public T next() { 
      return null; 
     } 

     @Override 
     public void remove() { 
      throw new UnsupportedOperationException("Not supported."); 
     } 

     @Override 
     public void reset() { 
      throw new UnsupportedOperationException("Not supported yet."); 
     } 
    } 
}