Проблема национального флага Маврикия

Question

Я уже решил проблему с голландским национальным флагом .

Но на этот раз я хочу попробовать что-то более сложное: проблема с национальным флагом Маврикия - 4 цвета,вместо 3. Какие-либо предложения по эффективному алгоритму?

В основном, проблема национального флага Маврикия фокусируется на том, как вы сможете отсортировать данный список пар на основе порядка цветов в национальном флаге Маврикия (Красный, синий, желтый, зеленый).И числа должны быть отсортированы в порядке возрастания.

Пример ввода схемы программирования:

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

Выход:

((R. 1) (R. 3) (B. 2)(B. 8) (Y. 1) (Y. 7) (G. 3) (G. 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--;
        }   
    }

Answer 3

В основном, сохраните следующее:

a[0-p] => '0'
a[p-q] => '1'
a[q-r] => '2'
a[r-s] => traversing! 
a[s-length] => '3'          

Код:

        int p=-1,q=-1,r=0,s=a.length-1;
        while(r<=s){
            if(a[r]==0){
                exchange(a,p+1,r);
                p++;r++;
                if(q!=-1)
                    q++;
            } else if (a[r]==1){
                if(q==-1)
                    q=p;
                exchange(a,q+1,r);
                q++;r++;
            } else if(a[r]==2) {
                r++;
            } else {
                exchange(a,r,s);
                s--;
            }

        }