毛里求斯国旗问题

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