Quote Originally Posted by nuzzle View Post
Or rather how do you define it in this case?
two sequences are equivalent if one can be obtained from the other by rotations or permutation of the labels ( note that both form a proper subgroup of the group of permutation of order 2n; but given a sequence its sorting permutations may not belong to it, in general ).

to the OP, if no more info is given ( like some statistical regularity of the input data ) I bet you can hardly do better: consider a sequence for big n with uniformly distributed labels: it's ordered canonical form will start with 123...k-1k... with high probability with k growing with n ( presumably linearly ); if this is the case, then any algorithm scanning the wanted form incrementally ( like the one you suggested ) will be n^2.

anyway, I think you can boost the algorithm runtime by finding invariants. For example, the histogram of distances between each label on the circle ( and more generally, any rotationally invariant statistics on such ordered list of distances, like higher order moments ) clearly is such an invariant . Now, I conjecture that given sensible distributions of the input data the probabilty that two inequivalent sequences have the same such invariant goes to 0 for big n. So, combining your o(n^2) algorithm with a prelimary check of a sub-O(n^2) invariant may give an overall sub-O(n^2) algorithm on avarage.

BTW, given that your sequences are bounded in the range 20-30, trying to reduce that algorithm complexity could be ineffective. I would rather focus on the global problem ( the millions of sequences ) instead. One obvious thing to do would be parallelizing it ...