Problema de la bandera nacional de Mauritus

Question

Ya he hecho una solución para el Dutch national flag problem.

Pero esta vez, quiero intentar algo más difícil: el problema de la bandera nacional Mauritus - 4 colores, en lugar de 3. ¿Alguna sugerencia para un algoritmo efectivo?

Básicamente, el problema de la bandera nacional de Mauricio se centra en cómo podría clasificar la lista de pares dada según el orden de colores en la bandera nacional de Mauricio (rojo, azul, amarillo y verde). Y los números deben ordenarse en orden ascendente también.

Esquema programación de muestras de entrada:.......

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

de salida:.......

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

Answer 1

Esto es como el problema de la bandera nacional holandesa, pero tenemos cuatro colores. Esencialmente se aplica la misma estrategia. Supongamos que tenemos (donde^representa el punto que se escanea).

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

y escaneamos un

1. rojo, luego intercambiamos el primer azul con el nodo actual
2. AZUL hacemos nada
3. amarilla intercambiamos con el último?
4. Verde intercambiamos el último color amarillo con el último? Entonces, ¿el nodo actual con el intercambio?

Así que tenemos que hacer un seguimiento o un puntero más de lo habitual.

tenemos que mantener un registro de la primera azul, la primera?, El último?, La última Y

En general, la misma estrategia funciona para cualquier número de colores, pero se necesitan un número cada vez mayor de permutas .

Answer 2

Esto es lo que se me ocurrió. En lugar de colores, estoy usando números.

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


} 

De manera similar, podemos escribir para cinco banderas.

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