值的循环的最低排序 [英] Minimum ordering of a loop of values
问题描述
给定一个样序列：
1,2,1,2,1,1,1,2,1,2,1,3,1,2,1,2,1,3
什么是有效的方式来获得最小订货：
What is an efficient way to obtain the minimum ordering:
1,1,1,2,1,2,1,3,1,2,1,2,1,3,1,2,1,2
的蛮力的方法是显而易见的，所以请不要推荐 - 除非提供了令人信服的证据证明暴力的方法是做到这一点的唯一方法
The brute force approach is obvious so please don't recommend it -- unless to provide a convincing proof that the brute force approach is the only way to do it!
更多细节
我有一种算法，号码列表。该算法的输出是一个列表/阵列，但在逻辑上的数字重新present一个循环，的元素事项其中只有相对顺序。为了存储这些循环购买比较我想把它们存储在这样一种方式，数字的一维列表存储重新presents循环中的元件的最小顺序。一张照片是最有帮助的：
I have an algorithm that generates a list of numbers. The output of the algorithm is a list / array, but logically the numbers represent a loop, where only the relative order of the elements matters. In order to store these loops for later comparison I want to put store them in such a way that the one-dimensional list of numbers stored represents the minimum ordering of the elements in the loop. A picture would be most helpful:
这个循环描述的路径周围的T四格骨牌，其中1是向前迈进;二是右转，而3左转。不要紧，你从哪里开始，甚至你往哪个方向走，下面的这个序列18的动作将让你一件T四格骨牌。该算法的产生此环路的输出将返回一个任意起始点和方向的元件。所以返回的数组可能是：
This loop describes the path around the T tetromino, where 1 is move forward, 2 is turn right, and 3 is turn left. It doesn't matter where you start or even which direction you go, following this sequence of 18 moves will get you a T tetromino. The output of the algorithm which produces this loop will return the elements with an arbitrary starting point and direction. So the returned array could be:
任意初始顺序：
1,2,1,2,1,1,1,2,1,2,1,3,1,2,1,2,1,3
有一个最低订货，虽然。它可以从两个不同的电路来获得，反映了一个事实的T四格骨牌是对称的：
There is one minimum ordering, though. It can be obtained from two different circuits, reflecting the fact that the T tetromino is symmetrical:
最少起订：
1,1,1,2,1,2,1,3,1,2,1,2,1,3,1,2,1,2
蛮力
最明显的蛮力的方法是构建所有可能的顺序，并采取最低限度。我的问题是是否有这样做的更加聪明和有效的方式。
The obvious brute force method is to construct all possible orderings and take the minimum. My question is whether there is a more clever and efficient way of doing this.
推荐答案
这是一个良好的学习问题称为的词典顺序最小的字符串旋转。
This is a well-studied problem called the lexicographically minimal string rotation.
更好的算法在O（n）时间都跑，而不是O（N * N）的天真算法。
The better algorithms all run in O(n) time as opposed to O(n*n) for the naive algorithm.
这篇关于值的循环的最低排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
