2

给定一个序列,如:

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 tetromino。产生此循环的算法的输出将返回具有任意起点和方向的元素。所以返回的数组可能是:

任意初始排序:

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

任意顺序

但是,有一个最低订购量。它可以从两个不同的电路中获得,反映了 T tetromino 是对称的事实:

最低订购量:

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

最低订购量

蛮力

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

4

1 回答 1

4

这是一个经过充分研究的问题,称为字典最小字符串旋转

与朴素算法的 O(n*n) 相比,更好的算法都在 O(n) 时间内运行。

于 2012-08-18T16:34:18.637 回答