Mauritus national flag problem

问题:

I've made a solution for the Dutch national flag problem already.

But this time, I want to try something more difficult: the Mauritus national flag problem - 4 colours, instead of 3. Any suggestions for an effective algorithm?

Basically, The Mauritius National Flag Problem focuses on how you would be able to sort the given list of pairs based on the order of colors in the Mauritius National Flag (Red, Blue, Yellow, Green). And the numbers must be sorted in ascending order too.

Scheme Programming Sample Input:

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

Output:

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

回答1:

This is just like the Dutch national flag problem, but we have four colors. Essentially the same strategy applies. Assume we have (where ^ represents the point being scanned).

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

and we scan a

1. red, then we swap the first blue with the current node
2. BLUE we do nothing
3. yellow we swap with the last ?
4. Green we swap the last yellow with the last ? Then the current node with the swapped ?

So we need to keep track or one more pointer than usual.

We need to keep track of the first blue, the first ?, the last ?, the last Y

In general, the same strategy works for any number of colors, but an increasing numbers of swaps are needed.

回答2:

Here is what I came up with. Instead of colors, I am using numbers.

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


}

Similarly we can write for five flags.

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

回答3:

Basically, maintain the following :

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

Code:

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

        }