值循环的最小排序

给定如下序列：

1,2,1,2,1,1,1,2,1,2,1,3,1,2,1,2,1,3

什么是高效的获得最小订购量的方法：

1,1,1,2,1,2,1,3,1,2,1,2,1,3,1,2,1,2

暴力方法是显而易见的，所以请不要推荐它——除非提供令人信服的证据证明暴力方法是唯一的方法！

更多详情

我有一个生成数字列表的算法。该算法的输出是一个列表/数组，但逻辑上数字代表一个循环，其中只有元素的相对顺序很重要。为了存储这些循环以供以后比较，我想以这样的方式存储它们：存储的一维数字列表代表循环中元素的最小顺序。图片会最有帮助：

该循环描述了围绕 T tetromino 的路径，其中 1 是向前移动，2 是右转，3 是左转。无论您从哪里开始，甚至朝哪个方向走，遵循这 18 步的顺序都会让您获得 T 四格骨牌。产生此循环的算法的输出将返回具有任意起点和方向的元素。所以返回的数组可能是：

任意初始排序：

1,2,1,2,1,1,1,2,1,2,1,3,1,2,1,2,1,3

不过，有一个最低订购量。它可以从两个不同的电路获得，反映了 T 四联骨牌是对称的事实：

最小订购量：

1,1,1,2,1,2,1,3,1,2,1,2,1,3,1,2,1,2

暴力破解

显而易见的蛮力方法是构建所有可能的排序并取最小值。我的问题是是否有更聪明、更有效的方法来做到这一点。

这是一个经过充分研究的问题，称为字典顺序最小字符串旋转 http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation.

更好的算法都在 O(n) 时间内运行，而朴素算法的运行时间为 O(n*n)。