MAURITUS国旗问题 [英] Mauritus national flag problem

问题描述

我做的荷兰国旗问题了。

但是这一次，我想尝试一些更困难：在MAURITUS国旗的问题 - 4种颜色，而不是3任何建议建立一个有效的算法

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.

计划编程示例输入：

（（R 3）（G 6）（Y 1）（B。2）（Y 7）（G 3），（R 1）（B。8））

( (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））

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

推荐答案

这就像荷兰国旗的问题，但我们有四种颜色。本质上相同的策略应用。假设我们有（其中^再presents点扫描）。

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
         ^

和我们扫描

1. 在红色的，那么我们交换第一个蓝色与当前节点
2. BLUE我们做什么
3. 在黄色我们换用了最后一个？
4. 绿色，我们交换了最后一个黄中带过去的？那么当前节点对换？

因此​​，我们需要跟踪或者一个比平常更多的指针。

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.

这篇关于MAURITUS国旗问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！