Problem flagi narodowej Mauritus

Question

Zrobiłem już rozwiązanie dla Dutch national flag problem.

Ale tym razem chcę spróbować czegoś trudniejszego: problem flagi narodowej Mauritus - 4 kolory, zamiast 3. Jakieś sugestie dotyczące skutecznego algorytmu?

Zasadniczo, problem flagi narodowej Mauritiusa koncentruje się na sposobie sortowania podanej listy par zgodnie z kolejnością kolorów na Fladze Narodowej Mauritiusa (czerwony, niebieski, żółty, zielony). Numery należy również sortować w kolejności rosnącej.

Schemat wejścia programowania próbki.......

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

wyjściowy.......

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

Answer 1

Jest to podobne do problemu holenderskiej flagi narodowej, ale mamy cztery kolory. Zasadniczo obowiązuje ta sama strategia. Załóżmy, że mamy (gdzie^oznacza skanowany punkt).

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

i skanowanie

1. czerwony, potem zamienić pierwszy niebieski z bieżącego węzła
2. NIEBIESKI nic nie zrobimy
3. żółty możemy zamienić z ostatniego?
4. Zielony zamieniamy ostatni żółty z ostatnim? Następnie obecny węzeł z zamienionym?

Musimy więc zachować ścieżkę lub jeszcze jedną wskazówkę niż zwykle.

Musimy śledzić pierwszego niebieskiego, pierwsza? Ostatnia? Ostatnia Y

Na ogół taka sama strategia działa dla dowolnej liczby kolorów, konieczne są jednak coraz większa liczba swapów .

Answer 2

Oto, co wymyśliłem. Zamiast kolorów używam liczb.

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


} 

Podobnie możemy napisać dla pięciu flag.

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