Minimize sequence with rules

[Peter_B]

I may be missing something but finding the "minimal" sequence seems trivial. It's just to order the items. With your example it would be,

1 1 2 2 3 3 4 4

What cuber64 actually means is that he/she wants an algorithm to find the canonical form for a given sequence, under the equivalence relation whereby permutations and circular re-orderings are equivalent.

@cuber64: I think the best you could get for this is O(n), as any algorithm will likely have to look at all the letters of the sequence to determine the canonical form. Or at least all except the last one or two letters, as these can be determined by what is left over after looking at the rest.

Not much help, I know, but sometimes having a bound on what you can likely achieve will help you know when to stop looking for a better approach