Mauritus national flag problem

Question

Ho già creato una soluzione per il Dutch national flag problem.

Ma questa volta, voglio provare qualcosa di più difficile: il problema della bandiera nazionale Mauritus - 4 colori, invece di 3. Qualche suggerimento per un algoritmo efficace?

Fondamentalmente, il problema della Bandiera Nazionale di Mauritius si concentra su come si sarebbe in grado di ordinare l'elenco di coppie dato in base all'ordine dei colori nella bandiera nazionale Mauritius (rosso, blu, giallo, verde). E i numeri devono essere ordinati in ordine crescente.

Schema Programmazione Ingresso di esempio:.......

((R 3) (G 6) (Y 1) (B 2) (Y 7) (G 3) (R 1) (. B 8))

uscita:.......

((R 1) (R 3) (B 2) (B 8) (Y 1) (Y 7) (G 3 (G.6))

Answer 1

Questo è proprio come il problema della bandiera nazionale olandese, ma abbiamo quattro colori. In sostanza si applica la stessa strategia. Supponiamo di avere (dove^rappresenta il punto che viene scansionato).

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

e noi la scansione di un

1. rosso, poi ci scambiamo il primo blu con il nodo corrente
2. BLU non facciamo niente
3. giallo ci scambiamo con l'ultimo?
4. Verde scambiamo l'ultimo giallo con l'ultimo? Quindi il nodo corrente con lo swap?

Quindi dobbiamo tenere traccia o un puntatore in più del solito.

Abbiamo bisogno di tenere traccia del primo blu, il primo?, L'ultima?, L'ultimo Y

In generale, la stessa strategia funziona per qualsiasi numero di colori, ma sono necessari un numero crescente di swap .

Answer 2

Ecco cosa mi è venuto in mente. Invece dei colori, sto usando i numeri.

// 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--; 
    }   
} 


} 

Analogamente, possiamo scrivere per cinque bandiere.

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--; 
     } 
    }