algorithm - 图灵机上的荷兰国旗

Question

我有一个字符序列 xxxxxx（x^k 和 k > 0）我的目标是将这句话转换成荷兰国旗，也就是说：

xxxxx -> RRWWBB xxxx -> RWBB

R <= W <= B

我发现的所有解决方案都具有非常高的复杂性。您是否有任何提示/线索可以帮助我仅使用一个磁带和一个磁头/光标来构建图灵机？

Answer 1

如何将任务划分为子任务，例如：

1. 将最后一个 X 更改为 B。
2. 将最后一个 X 更改为 W。
3. 将第一个 X 更改为 R。
4. 将 BW 更改为 WB。

编辑：

这是另一种方法：您说您已经看到从呈现颜色开始的算法（无序）。所以你真正需要的只是一种将颜色放入（乱序）的方法......