मॉरिटस राष्ट्रीय ध्वज समस्या

Question

मैंने पहले से ही Dutch national flag problem के लिए समाधान बनाया है।

लेकिन इस बार, मैं कुछ और कठिन प्रयास करना चाहता हूं: मॉरिटस राष्ट्रीय ध्वज समस्या - 4 रंग, बजाय एक प्रभावी एल्गोरिदम के लिए कोई सुझाव?

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

योजना प्रोग्रामिंग नमूना इनपुट:।।।।।।।

((आर 3) (जी 6) (वाई 1) (बी 2) (वाई 7) (जी 3) (आर 1) (। बी 8))

आउटपुट:।।।।।।।

((आर 1) (आर 3) (बी 2) (बी 8) (वाई 1) (वाई 7) (जी 3) (जी 6))

Answer 1

यह डच राष्ट्रीय ध्वज की समस्या की तरह है, लेकिन हमारे पास चार रंग हैं। अनिवार्य रूप से एक ही रणनीति लागू होती है। मान लें कि हमारे पास है (जहां^स्कैन किए जाने वाले बिंदु का प्रतिनिधित्व करता है)।

RRRRBBB???????????YYYYGGGG 
     ^

और हम स्कैन एक

1. लाल, तो हम पहली नीली वर्तमान नोड
2. नीले के साथ स्वैप हम कुछ नहीं कर
3. पीला हम पिछले के साथ स्वैप?
4. ग्रीन हम आखिरी पीले रंग के आखिरी के साथ स्वैप करते हैं? फिर स्वैप के साथ वर्तमान नोड?

तो हमें सामान्य से ट्रैक या एक और पॉइंटर रखने की आवश्यकता है।

हम पहले नीला का ट्रैक रखने के लिए, पहले की आवश्यकता है?, पिछले? पिछले Y

सामान्य तौर पर, एक ही रणनीति रंग के किसी भी संख्या के लिए काम करता है, लेकिन अदला-बदली की एक बढ़ती हुई संख्या की जरूरत है ।

Answer 2

यहां मैं क्या आया हूं। रंगों के बजाय, मैं संख्याओं का उपयोग कर रहा हूं।

// l - index at which 0 should be inserted. 
// m1 - index at which 1 should be inserted. 
// m2 - index at which 2 should be inserted. 
// h - index at which 3 should be inserted. 
l=m1=m2=0; 
h=arr.length-1 
while(m2 <= h) { 
    if (arr[m2] == 0) { 
     swap(arr, m2, l); 
     l++; 

     // m1 should be incremented if it is less than l as 1 can come after all 
     // 0's 
     //only. 
     if (m1 < l) { 
      m1++; 
     } 
     // Now why not always incrementing m2 as we used to do in 3 flag partition 
     // while comparing with 0? Let's take an example here. Suppose arr[l]=1 
     // and arr[m2]=0. So we swap arr[l] with arr[m2] with and increment l. 
     // Now arr[m2] is equal to 1. But if arr[m1] is equal to 2 then we should 
     // swap arr[m1] with arr[m2]. That's why arr[m2] needs to be processed 
     // again for the sake of arr[m1]. In any case, it should not be less than 
     // l, so incrmenting. 
     if(m2<l) { 
      m2++; 
     }  
    } 
    // From here it is exactly same as 3 flag. 
    else if(arr[m2]==1) { 
     swap(arr, m1, m2) 
     m1++; 
     m2++;   
    } 
    else if(arr[m2] ==2){ 
     m2++; 
    } 
    else { 
     swap(arr, m2, h); 
     h--; 
    }   
} 


} 

इसी तरह हम पांच झंडे के लिए लिख सकते हैं।

l=m1=m2=m3=0; 
    h= arr.length-1; 
    while(m3 <= h) { 
     if (arr[m3] == 0) { 
      swap(arr, m3, l); 
      l++; 
      if (m1 < l) { 
       m1++; 
      } 
      if(m2<l) { 
       m2++; 
      } 
      if(m3<l) { 
       m3++; 
      } 

     } 
     else if(arr[m3]==1) { 
      swap(arr, m1, m3); 
      m1++; 
      if(m2<m1) { 
       m2++; 
      } 
      if(m3<m1) { 
       m3++; 
      } 

     } 
     else if(arr[m3] ==2){ 
      swap(arr,m2,m3); 
      m2++; 
      m3++; 
     } 
     else if(arr[m3]==3) { 
      m3++; 
     } 
     else { 
      swap(arr, m3, h); 
      h--; 
     } 
    }